Skip to content
/ fst Public
forked from BurntSushi/fst

Represents large sets and maps compactly with finite state transducers.

License

Unlicense and 2 other licenses found

Licenses found

Unlicense
UNLICENSE
Unknown
COPYING
MIT
LICENSE-MIT
Notifications You must be signed in to change notification settings

crabhi/fst

 
 

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 levages memory maps to make range queries, regular expression queries and Levenshtein (edit) distance 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.

Installation

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

[dependencies]
fst = "0.1"

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. Check out the documentation for a lot more examples!

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

// A convenient way to create sets in memory.
let keys = vec!["fa", "fo", "fob", "focus", "foo", "food", "foul"];
let set = try!(Set::from_iter(keys));

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

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

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

About

Represents large sets and maps compactly with finite state transducers.

Resources

License

Unlicense and 2 other licenses found

Licenses found

Unlicense
UNLICENSE
Unknown
COPYING
MIT
LICENSE-MIT

Stars

Watchers

Forks

Packages

No packages published

Languages

  • Rust 99.5%
  • Other 0.5%