trie-rs

trie-rs is a Rust crate for building memory-efficient tries (prefix trees) using LOUDS (Level-Order Unary Degree Sequence) succinct encoding, a bit-packed representation that keeps the compiled structure compact even for large word sets. Entries are accumulated in a TrieBuilder and compiled into an immutable, read-optimized trie via build(), which supports exact_match, predictive_search, and common_prefix_search — all implemented as lazy iterators rather than eagerly allocated vectors.

The crate is generic over any Ord label type, not just strings, so the same API works over UTF-8 text, sequences of words, or arbitrary byte/label arrays. A companion map::Trie variant associates a value with each entry, and an IncSearch cursor supports incremental, one-label-at-a-time querying for interactive use cases like autocomplete.

What You Get

• A TrieBuilder/Trie pair: accumulate entries with push()/insert(), then compile into a read-only, LOUDS-encoded trie with build()
• Exact-match, predictive-search, and common-prefix-search query methods that return lazy iterators instead of pre-allocated collections
• Generic label support (Label: Ord) so the trie works over &str/UTF-8 bytes, Vec<&str> word sequences, or fixed-size [u8; N] arrays with no per-type reimplementation
• A map::Trie module that mirrors the whole API while attaching a Value to each entry
• An IncSearch cursor for incremental, one-label-at-a-time querying suited to interactive/streaming use like autocomplete
• Optional Cargo features — serde for (de)serialization, mem_dbg for measuring in-memory structure size, and rayon for data-parallel operations

Common Use Cases

• Autocomplete and predictive-text UIs that need fast prefix lookups over large dictionaries
• Tokenizers and dictionary-backed parsers (e.g. Japanese/CJK segmentation) that match against a fixed vocabulary
• Spell-checkers and fuzzy-lookup tools built on exact-match and common-prefix search
• Memory-constrained services that need a large word/key set resident without the overhead of a pointer-heavy trie or a hash set

Under The Hood

Architecture The crate is organized around a two-layer design: a map::Trie<Label, Value> (src/map/trie.rs) that is the actual storage/search engine, and a thin Trie<Label> wrapper (src/trie/trie_impl.rs — pub struct Trie<Label>(pub map::Trie<Label, ()>)) that specializes the map to unit values for word-only lookups. Construction goes through TrieBuilder types (src/trie/trie_builder.rs, src/map/trie_builder.rs) that accumulate pushed entries into an intermediate NaiveTrie (src/internal_data_structure/naive_trie.rs) — a conventional pointer-based trie — and build() then compiles that into a compact LOUDS succinct representation via the external louds-rs crate, trading a one-time build cost for a bit-packed, cache-friendly final structure. Search operations are implemented as lazy iterators (src/iter/{search_iter,prefix_iter,postfix_iter,keys}.rs) that walk the LOUDS structure incrementally, and a separate IncSearch cursor (src/inc_search.rs) supports online querying one label at a time. Mutation only happens pre-build; the compiled trie is read-only and space-optimized.

Tech Stack A pure Rust crate (edition 2021, MSRV 1.67 with no features / 1.75 with all features) with a minimal dependency footprint: the only non-optional runtime dependency is louds-rs (^0.7), the succinct bit-vector library backing the LOUDS encoding, while mem_dbg (0.1.4), serde (1.0, derive), and rayon (via louds-rs) are all opt-in Cargo features rather than defaults. Dev-dependencies are criterion (0.2) for benchmarking (benches/bench.rs, results published to GitHub Pages), rand (0.6) and lazy_static (1.3) for fixtures, and version-sync (0.9), which powers tests/test_versions.rs to keep the README version string in sync with Cargo.toml. Distribution is via crates.io with docs.rs-generated API docs and GitHub Actions CI — no runtime framework, database, or deployment tooling involved.

Code Quality Inline #[cfg(test)] mod tests blocks are colocated with implementation across inc_search.rs, naive_trie_b_f_iter.rs, map/trie.rs, and trie/trie_impl.rs, plus an integration test (tests/test_versions.rs) enforcing README/Cargo.toml version parity. Documentation is unusually strict: #![forbid(missing_docs)] at the crate root hard-fails the build if any public item lacks a doc comment, and most public methods carry runnable doctest examples that double as tests via cargo test --doc. Error handling favors typed Option/Result returns (IncSearch::query returns Option<Answer>, query_until returns Result<Answer, usize>) over panics. CI runs clippy (including a no-default-features pass), builds and tests against both the MSRV and latest stable toolchains, and builds docs. No unsafe blocks were found in src/.

API Design The public API is deliberately small: TrieBuilder::push/insert → build() → a handful of query methods (exact_match, predictive_search, common_prefix_search) returning iterators so callers pay only for what they consume. The generic design (Trie<Label: Ord> with Arr: AsRef<[Label]>) lets one API serve UTF-8 text, word-sequence, and byte-array use cases without separate types per case — demonstrated in the README with Japanese-phrase, English-phrase, and digits-of-pi examples. IncSearch adds a stateful cursor returning a Match/Prefix/PrefixAndMatch Answer enum instead of an ambiguous boolean, and the map module mirrors the full API with an associated value rather than diverging into a second API. LOUDS-based tries are a well-established structure, so this isn’t a novel data structure, but the ergonomic generic API and incremental-search addition go beyond a bare textbook implementation.