README.md
1fst
2===
3This crate provides a fast implementation of ordered sets and maps using finite
4state machines. In particular, it makes use of finite state transducers to map
5keys to values as the machine is executed. Using finite state machines as data
6structures enables us to store keys in a compact format that is also easily
7searchable. For example, this crate leverages memory maps to make range queries
8very fast.
9
10Check out my blog post
11[Index 1,600,000,000 Keys with Automata and
12Rust](http://blog.burntsushi.net/transducers/)
13for extensive background, examples and experiments.
14
15[](https://github.com/BurntSushi/fst/actions)
16[](https://crates.io/crates/fst)
17
18Dual-licensed under MIT or the [UNLICENSE](http://unlicense.org).
19
20
21### Documentation
22
23https://docs.rs/fst
24
25The
26[`regex-automata`](https://docs.rs/regex-automata)
27crate provides implementations of the `fst::Automata` trait when its
28`transducer` feature is enabled. This permits using DFAs compiled by
29`regex-automata` to search finite state transducers produced by this crate.
30
31
32### Installation
33
34Simply add a corresponding entry to your `Cargo.toml` dependency list:
35
36```toml,ignore
37[dependencies]
38fst = "0.4"
39```
40
41
42### Example
43
44This example demonstrates building a set in memory and executing a fuzzy query
45against it. You'll need `fst = "0.4"` with the `levenshtein` feature enabled in
46your `Cargo.toml`.
47
48```rust
49use fst::{IntoStreamer, Set};
50use fst::automaton::Levenshtein;
51
52fn main() -> Result<(), Box<dyn std::error::Error>> {
53 // A convenient way to create sets in memory.
54 let keys = vec!["fa", "fo", "fob", "focus", "foo", "food", "foul"];
55 let set = Set::from_iter(keys)?;
56
57 // Build our fuzzy query.
58 let lev = Levenshtein::new("foo", 1)?;
59
60 // Apply our fuzzy query to the set we built.
61 let stream = set.search(lev).into_stream();
62
63 let keys = stream.into_strs()?;
64 assert_eq!(keys, vec!["fo", "fob", "foo", "food"]);
65 Ok(())
66}
67```
68
69Check out the documentation for a lot more examples!
70
71
72### Cargo features
73
74* `levenshtein` - **Disabled** by default. This adds the `Levenshtein`
75 automaton to the `automaton` sub-module. This includes an additional
76 dependency on `utf8-ranges`.
77
){kind=link}