Represent large sets and maps compactly with finite state transducers.
Rust Other
Clone or download
Permalink
Failed to load latest commit information.
benches rustup May 22, 2016
data Improve microbenchmarks. Nov 12, 2015
fst-bin 0.3.0 Nov 28, 2017
fst-levenshtein 0.3.0 Nov 28, 2017
fst-regex 0.3.0 Nov 28, 2017
scripts progress Sep 14, 2015
src Implement `Default` for Set and Map Jun 27, 2018
tests Implement `Default` for Set and Map Jun 27, 2018
.gitignore Adding unsorted construction. Oct 31, 2015
.travis.yml 0.3.0 Nov 28, 2017
COPYING initial commit Sep 5, 2015
Cargo.toml 0.3.0 Nov 28, 2017
LICENSE-MIT initial commit Sep 5, 2015
Makefile remove pushes from Makefile Aug 16, 2016
README.md Updates README Cargo.toml example to say 0.3.0 Apr 19, 2018
UNLICENSE initial commit Sep 5, 2015
appveyor.yml fix Nov 12, 2015
ctags.rust initial commit Sep 5, 2015
session.vim progress Sep 13, 2015

README.md

fst

This crate provides a fast implementation of ordered sets and maps using finite state machines. In particular, it makes use of finite state transducers to map keys to values as the machine is executed. Using finite state machines as data structures enables us to store keys in a compact format that is also easily searchable. For example, this crate leverages memory maps to make range queries very fast.

Check out my blog post Index 1,600,000,000 Keys with Automata and Rust for extensive background, examples and experiments.

Linux build status Windows build status

Dual-licensed under MIT or the UNLICENSE.

Documentation

Full API documentation and examples.

The fst-regex and fst-levenshtein crates provide regular expression matching and fuzzy searching on FSTs, respectively.

Installation

Simply add a corresponding entry to your Cargo.toml dependency list:

[dependencies]
fst = "0.3"

And add this to your crate root:

extern crate fst;

Example

This example demonstrates building a set in memory and executing a fuzzy query against it. You'll need fst = "0.3" and fst-levenshtein = "0.2" in your Cargo.toml.

extern crate fst;
extern crate fst_levenshtein;

use std::error::Error;
use std::process;

use fst::{IntoStreamer, Set};
use fst_levenshtein::Levenshtein;

fn try_main() -> Result<(), Box<Error>> {
  // A convenient way to create sets in memory.
  let keys = vec!["fa", "fo", "fob", "focus", "foo", "food", "foul"];
  let set = Set::from_iter(keys)?;

  // Build our fuzzy query.
  let lev = Levenshtein::new("foo", 1)?;

  // Apply our fuzzy query to the set we built.
  let stream = set.search(lev).into_stream();

  let keys = stream.into_strs()?;
  assert_eq!(keys, vec!["fo", "fob", "foo", "food"]);
  Ok(())
}

fn main() {
  if let Err(err) = try_main() {
    eprintln!("{}", err);
    process::exit(1);
  }
}

Check out the documentation for a lot more examples!