fst

fst is a Rust library by Andrew Gallant (BurntSushi) that represents ordered sets and maps of strings as finite state transducers (FSTs) — a data structure that stores keys in a highly compact, shared-prefix/suffix form while still supporting fast lookups, range queries, and streaming iteration. Because an FST can be built once and then memory-mapped from disk, it’s possible to query sets containing over a billion keys with a small memory footprint and no full deserialization step.

Beyond basic membership and map lookups, the crate exposes an Automaton trait that lets any state machine — including Levenshtein/fuzzy-match automata (via the optional levenshtein feature) or regex-derived DFAs (via the companion regex-automata crate’s transducer feature) — be intersected against a built FST to perform fast approximate or pattern-based search directly over the compact representation. With over 23 million total crates.io downloads, it underpins search and indexing infrastructure across the Rust ecosystem, including autocomplete and full-text search engines.

What You Get

• Set and Map types for building ordered collections of strings (or string-to-u64 mappings) as finite state transducers
• Memory-mapped loading, so multi-gigabyte FSTs can be queried without fully deserializing into RAM
• Streaming iteration and range queries (.range()) over the FST’s sorted key space
• An Automaton trait allowing any state machine — including fuzzy Levenshtein search or regex-derived DFAs from regex-automata — to be intersected against a built FST
• An optional levenshtein feature adding a ready-to-use fuzzy-matching automaton for typo-tolerant search

Common Use Cases

• Building autocomplete or typeahead search over very large dictionaries with low memory overhead
• Implementing typo-tolerant (fuzzy) search using the Levenshtein automaton against a compact on-disk index
• Powering full-text search engines’ term dictionaries, where FSTs compactly store and quickly look up indexed terms
• Storing and querying large sorted key sets (e.g. deduplication indexes, IP range lookups) with memory-mapped access instead of loading everything into memory

Under The Hood

Architecture: The crate builds FSTs incrementally from sorted input (raw/ module handles the low-level builder and node representation), exposing Set (set.rs) and Map (map.rs) as the primary user-facing types, both backed by the same underlying transducer representation in raw/. The automaton/ module defines the Automaton trait used for intersecting arbitrary state machines (fuzzy matchers, regex DFAs) against the FST during traversal, and stream.rs implements the streaming iterator abstraction used for range and prefix queries without materializing full result sets in memory.

Tech Stack: Rust 2018 edition, dual-licensed Unlicense/MIT. The core library has zero required dependencies — utf8-ranges is pulled in only behind the optional levenshtein feature flag. The repository is a Cargo workspace containing the core fst crate plus fst-bin (a CLI tool) and bench, with the related fst-levenshtein and fst-regex crates kept as separate, excluded workspace members.

Code Quality: The project includes quickcheck-based property testing and memmap2-backed integration tests validating memory-mapped access paths, reflecting the correctness bar needed for a data structure meant to safely handle multi-gigabyte, disk-backed indexes. The author has published extensive background (a widely-cited blog post, “Index 1,600,000,000 Keys with Automata and Rust”) documenting the design tradeoffs. The project has had no commits since September 2024, which is common for BurntSushi’s foundational, feature-complete crates but is worth noting for teams evaluating active-maintenance risk.

API Design: The IntoStreamer/Streamer traits give a consistent, iterator-like interface across sets, maps, and query results (including automaton-based fuzzy/regex searches), so the same code pattern works whether you’re doing an exact lookup, a range scan, or a Levenshtein search. This uniformity is the crate’s main ergonomic strength, though the FST/automaton mental model itself (state machines intersected against transducers) has a steeper conceptual learning curve than a plain hash-set API.