tantivy-fst

tantivy-fst represents very large sets and maps compactly using finite state transducers (FSTs). Keys are stored in a single, deduplicated, memory-mappable automaton, so a dictionary of millions of strings occupies a fraction of the space of a conventional hash map while still supporting fast ordered lookups.

It is a Tantivy-specific fork of Andrew Gallant’s well-known fst crate, maintained to fit the needs of the Tantivy search engine. Beyond point lookups, it supports powerful streaming queries — range scans, regular-expression automata, and Levenshtein (fuzzy) matching — that operate directly over the compressed structure. Note: for general use, the upstream fst crate is recommended; this fork exists primarily as a Tantivy dependency.

What You Get

• Ordered Set and Map types backed by a compact FST automaton
• Memory-mappable, on-disk representation for very large dictionaries
• Streaming range queries over sorted keys
• Regular-expression automaton search across the whole set
• Levenshtein (fuzzy) automaton matching for approximate lookups

Common Use Cases

• Storing a search engine’s term dictionary compactly on disk
• Fuzzy and regex matching over millions of keys
• Range scanning ordered string keys without full deserialization
• Deduplicating and compressing large sorted key sets

Under The Hood

Architecture — The crate layers a friendly API over a low-level automaton engine. src/raw/ implements the core FST — the node encoding, builder, and byte-level format — while src/map.rs and the set type wrap it as ordered Map/Set collections. src/automaton/ defines the Automaton trait and combinators that let any state machine drive a search, src/regex/ compiles regular expressions into such automata, and src/stream.rs provides the lazy streaming iterators that all queries return.

Tech Stack — Rust (edition 2021) with a deliberately small dependency set: byteorder for the binary format, utf8-ranges for Unicode range handling, and an optional regex-syntax behind the default regex feature. Benchmarks under benches/ and property tests keep the byte format honest.

Code Quality — As a fork of BurntSushi’s battle-tested fst, it inherits a mature codebase with property-based tests (proptest, with checked-in regression seeds), benchmark suites, and CI configuration. The README is explicit that this fork exists for Tantivy and that general users should prefer upstream, which is a point of clarity rather than a defect.

API Design — The public surface is ergonomic for its domain: build with a streaming Builder, then query via Stream, Regex, or a Levenshtein automaton. The main friction is conceptual — keys must be inserted in sorted order and the FST is immutable once built — which reflects the underlying data structure rather than API awkwardness, and accounts for the steeper learning curve.