fst

Summary Spell the returned lifetime as . Current stable Rust warns that the existing signature hides a lifetime that is elided elsewhere (). This is a diagnostic-only change with no API, behavior, or format effect. Validation — 149 passed, 3 ignored

Summary store unfinished builder nodes with zero or one transition inline, allocating a only when a node branches; add a small value and constructors for raw, map, and set builders; preserve the existing 10,000-row, 2-way registry as the default. The first commit is entirely internal. The second is additive and lets callers with tight construction-memory budgets trade some state deduplication for a smaller bounded registry. Neither commit changes the FST format or read-side APIs. Motivation Sorted FST construction produces many unary nodes, but the current builder allocates a for every node that receives a transition. In one deterministic large dictionary construction profile, 2,132,365 compiled nodes broke down as: The inline representation removes the per-node transition allocation for the dominant one-transition case. The configurable registry addresses the other fixed construction-memory owner while keeping the established default unchanged. Compatibility Existing constructors still use exactly registry entries. Explicit defaults and existing constructors serialize identical bytes. A pristine-upstream/candidate comparison over 16,384 deterministic entries produced byte-identical map, set, and raw FSTs; each implementation opened the other's output successfully. No dependencies or code are added. The series builds with Rust 1.60. Validation — 157 passed, 3 ignored — 100 passed The two commits are intentionally separable: internal transition storage first, then the additive registry configuration API.

Hi, I'm working on autocompletion, and I'd like to find, given a known completion C, what is the longest suffix of the input that is a prefix of C. Example: C = "banana" input: "my name is alibaba" output (overlap between the two): "ba" (or equivalently just the length 2 would be enough). Intuitively, it seems like it would be possible to build such a transducer: feed the input and at every step it tells you what is the longest matching suffix, every state being accepting. I'm just not sure how to build it with this library, the interface to get an output from an evaluation is not clear, could you give me a hand there? Essentially you would have a map of all the prefixes of C to their length, make that a repeating FST, and on evaluation take the max of the outputs (longest sequence).