Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

How It Works

A high-level tour of the engine’s internals, for the curious and for anyone tuning or contributing.

The automaton

At build time the patterns are compiled into a trie (an Aho–Corasick automaton) over grapheme clusters: each node is a pattern prefix, edges are grapheme transitions, and terminal nodes carry the indices of the patterns that end there. Failure links and per-node metadata are precomputed so the search never needs to mutate the automaton.

The engine is fully immutable after build, which is why it is cheap to share across threads (&FuzzyAhoCorasick) and why every search allocates only transient per-call state — and that state is bounded by the haystack and match density, not by the pattern count (the best-match-per-span map is reserved conservatively), so per-query memory stays flat on very large automata.

Fuzzy matching is a breadth-first exploration. Conceptually, a state is “we are at automaton node n, having consumed up to haystack position j, with these accumulated edit counts and penalty”. From each state the search branches:

  • exact transition — consume the matching grapheme, no penalty (an O(1) map lookup),
  • substitution — consume a different grapheme, penalty scaled by similarity,
  • insertion — skip a haystack grapheme,
  • deletion — advance in the pattern without consuming input,
  • transposition — consume two adjacent graphemes swapped.

The search restarts from every grapheme position, which is what makes it a multi-pattern, match- anywhere fuzzy search rather than a single alignment.

Why it stays fast

Several mechanisms keep the exponential-looking exploration in check:

  • State deduplication. Insertions and deletions can reach the same automaton position by exponentially many paths; a visited-set collapses states that agree on position, span, and per-type edit counts down to the lowest-penalty representative.
  • Pruning ceilings. Each node stores coefficients for the best score still reachable through it, so a state whose penalty already exceeds what any reachable pattern could tolerate — at the current threshold — is dropped along with its entire subtree.
  • Push-time guards. Cheap penalty checks reject an edit before a state is even enqueued. At the last edit level, a dead-end filter additionally skips pushes whose child node can neither emit a match nor advance — a linear scan of that node’s (few) edges, chosen over a stored bitmap to keep each node small.
  • Edit-limit specialization. Common whole-edit budgets (1–6, and unlimited) are compiled to specialized code paths at build time, so limit checks fold into comparisons the branch predictor learns immediately. A 1-edit search further skips most start windows outright via a two-character reachability test.
  • Zero-allocation ASCII fast path. All-ASCII haystacks and patterns are matched byte-by-byte without grapheme segmentation or case-folded copies, and exact transitions resolve to a linear scan of a compact per-node edge array rather than a hash lookup.
  • Compact state. Node indices and grapheme positions are u32 and the four edit counts pack into a single word, keeping the per-state footprint small and cache-dense. A haystack with more than u32::MAX graphemes can’t be indexed this way, so search rejects it with Err(SearchError::HaystackTooLarge) (rather than truncating to wrong offsets); such inputs belong on the streaming path.
  • Compact automaton. Each Edge is 8 bytes — first_char plus a target node index whose spare high bit doubles as the single-ASCII-byte marker (a separate u8 would cost 4 bytes of padding under char’s alignment) — and each Node is 112 bytes, so large automata (tens of millions of nodes) stay in the hundreds of MB rather than gigabytes.
  • Beam / auto-beam. Optional caps bound the frontier for pathological inputs.

Scoring

When the search reaches a terminal node within the edit limits, it computes similarity = (N − penalties) / N × weight and keeps the candidate if it clears the threshold, retaining the best score per (start, end, pattern) span. The various search entry points then sort and resolve overlaps.

Streaming and the pre-filter

  • Streaming cuts the input into bounded, overlapping windows. The overlap equals the longest possible match (max_match_graphemes()), so no match is split, and each window owns the matches starting in its non-overlap prefix — giving exactly-once emission with no cross-window deduplication.
  • The pre-filter is a separate bit-parallel automaton (one machine word of NFA states advanced per input symbol) used only to locate candidate regions; the real engine described above still produces the results.

The API documentation covers the concrete types; the source is extensively commented if you want the exact recurrences.