// the find
BurntSushi/fst
Represent large sets and maps compactly with finite state transducers.
fst gives you ordered sets and maps backed by finite state transducers, so you can store millions of keys in a compact, memory-mappable structure and still do fast range queries, fuzzy search, and automaton-based matching. It's for people building search indexes, autocomplete, or any system that needs a huge sorted key space without loading it all into RAM.
The memory-map support means you can query a multi-gigabyte key set with near-zero startup cost and low resident memory, which is the actual selling point over a HashMap or BTreeMap. The Automaton trait is genuinely composable — you can intersect a Levenshtein automaton with a compiled regex-automata DFA and run both against the same transducer in one pass. BurntSushi's blog post walks through the construction algorithm and benchmarks in enough depth that you can understand the tradeoffs instead of just trusting the crate.
Last push was over a year ago and the crate is still on 0.4.x — there's no indication of active maintenance, so don't expect fixes for new edge cases or Rust edition churn. Keys must be inserted in lexicographic order during construction, which is a hard constraint that trips people up and forces a sort step for unsorted input. The workspace is split into fst, fst-regex, fst-levenshtein, and fst-bin with inconsistent documentation depth outside the main crate, so the regex and levenshtein pieces feel like an afterthought compared to the core transducer code.