fuzzy-aho-corasick

A high-performance, Unicode-aware, safe-Rust implementation of the Aho–Corasick automaton extended with fuzzy matching — insertions, deletions, substitutions, and transpositions — over grapheme clusters, with optional case-insensitive folding.

It answers the question “where in this text do any of my patterns appear, allowing for a few typos?” — the kind of problem that shows up in entity/name matching (e.g. AML screening), OCR cleanup, search-as-you-type, and log/stream scanning.

What it does

• Exact and fuzzy multi-pattern matching in one pass over a shared trie, with Levenshtein-style edits plus transposition.
• Unicode correctness: it matches over grapheme clusters, not bytes or code points, and folds case in a Unicode-aware way.
• Tunable scoring: per-edit-type penalties, a character similarity table, per-pattern weights, and a similarity threshold decide what counts as a match and how matches rank.
• Rich output control: raw matches, several ranking strategies, non-overlapping selection, segmentation, splitting, and find-and-replace.
• Scales to streams: search or replace over any Read/Write in constant memory, single- or multi-threaded.
• Optional fast lane: an opt-in bit-parallel pre-filter skips regions that provably cannot match, for a large speedup on big, sparse inputs — with identical results.

How to read this book

• Getting Started gets you matching in a couple of minutes.
• Core Concepts explains the edit model and how scores are computed — read this once and the rest of the API makes sense.
• Building an Engine, Searching, and Similarity cover the configuration surface.
• Streaming and Performance are for larger or latency-sensitive workloads.
• Reference describes how the engine works internally and credits the underlying research.

The crate’s API documentation on docs.rs is the authoritative reference for every type and method; this book is the narrative guide.

Installation

Add the crate to your Cargo.toml:

[dependencies]
fuzzy-aho-corasick = "0.4"

Or with cargo add:

cargo add fuzzy-aho-corasick

The crate has a single runtime dependency (unicode-segmentation) and builds on stable Rust (edition 2024).

Then bring the common types into scope:

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits};

The most useful items are re-exported at the crate root:

Everything else (the similarity table type, streaming match type, and so on) lives under the same crate root or the structs module.

Quick Start

Build an engine once, then query it as many times as you like. The engine is immutable and cheap to share (&FuzzyAhoCorasick) across threads.

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, SearchOptions};

fn main() {
    // Allow up to 1 edit per match, case-insensitive.
    let engine = FuzzyAhoCorasickBuilder::new()
        .fuzzy(FuzzyLimits::new().edits(1))
        .case_insensitive(true)
        .build(["hello", "world"]);

    // "helllo wolrd" has two typos: an extra 'l' (insertion) and swapped 'lr' (transposition).
    let opts = SearchOptions::new().threshold(0.8).sorted().non_overlapping();
    for m in engine.search("helllo wolrd", &opts).unwrap().iter() {
        println!("matched '{}' as '{}' (score {:.2})", m.pattern, m.text, m.similarity);
    }
    // matched 'hello' as 'helllo' (score 0.90)
    // matched 'world' as 'wolrd' (score 0.90)
}

Three things are happening here:

1. fuzzy(FuzzyLimits::new().edits(1)) — without this the engine only matches exactly. edits(1) lets each match differ from its pattern by at most one edit operation.
2. .threshold(0.8) — the similarity threshold. A candidate is only returned if its score is at least this high. See Scoring & Thresholds.
3. .sorted().non_overlapping() — asks for a ranked set of matches whose spans don’t overlap. SearchOptions bundles the order and overlap strategy for the single search entry point.

Inspecting a match

Each FuzzyMatch tells you what was found and how:

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, SearchOptions};
let engine = FuzzyAhoCorasickBuilder::new().fuzzy(FuzzyLimits::new().edits(1)).build(["needle"]);
for m in engine.search("find the neeedle", &SearchOptions::new().threshold(0.8)).unwrap().iter() {
    println!(
        "pattern #{} ({}) matched bytes {}..{} = {:?}",
        m.pattern_index, m.pattern, m.start, m.end, m.text,
    );
    println!(
        "  score {:.2}, edits {} (ins {}, del {}, sub {}, swap {})",
        m.similarity, m.edits, m.insertions, m.deletions, m.substitutions, m.swaps,
    );
}

start/end are byte offsets into the haystack, and text is the matched slice.

Next steps

• Understand the edit model and scoring.
• Learn the builder options.
• For find-and-replace, jump to Replacement.

The Fuzzy Matching Model

The engine looks for each pattern starting at every position in the haystack, exploring the edit operations you allow and keeping the best-scoring way to match each span. Understanding the four edit operations and the unit of matching (grapheme clusters) explains most of the engine’s behavior.

Edit operations

A candidate match is the pattern transformed into a haystack substring by a sequence of edits:

Substitution, insertion, and deletion are the classic Levenshtein edits; transposition is the extra Damerau operation, which matters because swapped letters are one of the most common human typos.

Each operation adds a penalty to the candidate; substitutions add a penalty scaled by how similar the two symbols are (see Similarity), and a swap is a single operation rather than two substitutions. How much each costs is configurable — see Penalties.

Symbols are grapheme clusters

The engine operates over grapheme clusters, not bytes or chars. A grapheme cluster is what a reader perceives as a single character: a, é, 😀, or a base letter plus combining marks (e + ◌́). This is the right unit for human-facing text:

• "café" is four symbols whether the é is one code point or e + a combining accent.
• An emoji with a skin-tone modifier is one symbol, so a single edit can’t tear it in half.

Pattern length N, which drives scoring, is measured in grapheme clusters, and edits act on whole grapheme clusters.

Case folding

With case_insensitive(true) the engine folds case in a Unicode-aware way (str::to_lowercase per grapheme), so Straße, STRASSE-style and Greek/Cyrillic case differences match as you’d expect. Folding is applied identically to the patterns at build time and to the haystack at search time.

Where matching starts and stops

Because the search restarts at every grapheme position, a pattern can be found anywhere — there is no notion of word boundaries built in. If you only want whole-token matches, filter the results by the surrounding characters, or use the segmentation API to reason about the gaps between matches.

The search is exact by default: with no fuzzy(..) limits, only zero-edit matches are produced, and the engine behaves like a classic Unicode Aho–Corasick automaton.

Scoring & Thresholds

Every candidate match earns a similarity score, and only candidates scoring at or above the threshold you pass to a search are returned. The score also decides how matches rank against each other.

The formula

For a candidate matched against a pattern of N grapheme clusters, having accumulated total edit penalties:

similarity = (N - penalties) / N * weight

• N is the pattern length in graphemes. Longer patterns dilute a fixed penalty, so one typo in a long word costs proportionally less than one in a short word.
• penalties is the sum of the per-edit costs (see Penalties). A substitution’s cost is scaled by symbol similarity, so a near-miss like o↔0 costs less than a wholly unrelated substitution.
• weight is the pattern’s weight (default 1.0). See Patterns & Weights.

With the default weight of 1.0, a perfect match scores 1.0 and the score falls toward 0.0 as penalties accumulate. Weights above 1.0 can push an important pattern’s score above 1.0 to prioritize it.

The threshold

Every search takes a threshold in 0.0..=1.0:

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, SearchOptions};
let engine = FuzzyAhoCorasickBuilder::new().fuzzy(FuzzyLimits::new().edits(2)).build(["needle"]);
let strict  = engine.search("neeedle", &SearchOptions::new().threshold(0.9)).unwrap();  // fewer, higher-quality matches
let lenient = engine.search("neeedle", &SearchOptions::new().threshold(0.6)).unwrap();  // more matches, more noise

The threshold is your primary quality knob. It is also a performance knob: a higher threshold lets the engine prune weak partial matches earlier, so it does less work.

Worked example

Take the pattern hello (N = 5) and the text helllo (one extra l, i.e. one insertion). With the default insertion penalty (~0.52):

similarity = (5 - 0.52) / 5 ≈ 0.90

So helllo matches hello at ~0.90 — comfortably above a 0.8 threshold, but it would be rejected at 0.95.

Additive scoring and its trade-off

The score is additive: each edit contributes independently. This is robust and predictable, but it means a single very-bad substitution can be hidden inside an otherwise-excellent long match — one sim = 0 substitution in a 20-grapheme pattern still scores ~0.93. If you need to forbid that, the weakest-link floor rejects any substitution below a per-symbol similarity, independent of the overall score.

Limits vs. threshold

There are two independent gates a match must pass:

1. Edit limits — a hard cap on the number of each edit type (and the total). A candidate exceeding any limit is discarded outright.
2. Threshold — a floor on the score.

Limits bound the search space (and worst-case cost); the threshold selects quality within it. You usually set both: limits to say “no more than 2 edits”, and a threshold to say “and it must still look at least 80% like the pattern”.

Builder & Edit Limits

You configure everything through FuzzyAhoCorasickBuilder, then call build(patterns) to get an immutable FuzzyAhoCorasick.

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, FuzzyPenalties};

let engine = FuzzyAhoCorasickBuilder::new()
    .fuzzy(FuzzyLimits::new().edits(2))          // global edit limits
    .penalties(FuzzyPenalties::default().substitution(0.7))
    .case_insensitive(true)
    .build(["pattern1", "pattern2"]);

Builder options

build accepts anything convertible into a Pattern — &str, String, (&str, weight), (&str, weight, max_edits), or a fully built Pattern. See Patterns & Weights.

Edit limits with FuzzyLimits

FuzzyLimits caps how many edits a match may contain. You can cap the total and/or each type individually:

use fuzzy_aho_corasick::FuzzyLimits;

FuzzyLimits::new().edits(2);                       // at most 2 edits, any mix
FuzzyLimits::new().substitutions(1).deletions(1);  // 1 substitution AND 1 deletion, no others
FuzzyLimits::new().edits(3).swaps(1);              // up to 3 edits total, at most 1 of them a swap

The semantics:

• edits(n) caps the total number of edits. When set alone, each individual edit type is left unbounded (bounded only by the total).
• insertions(n) / deletions(n) / substitutions(n) / swaps(n) cap that specific type.
• If you set only per-type limits (no edits), the unset types default to 0 — i.e. they are forbidden. This lets you say “substitutions only” with FuzzyLimits::new().substitutions(2).
• With no fuzzy(..) at all, the engine is exact: zero edits of every kind.

Limits are a hard filter applied before the threshold, and they bound the worst-case search space — tighter limits explore fewer states. A candidate that would exceed any applicable limit is never produced.

Global vs. per-pattern limits

fuzzy(..) on the builder sets the global default. Individual patterns can override it with their own limits (see Patterns & Weights); a pattern’s own limits take precedence over the global default for that pattern.

Penalties

FuzzyPenalties sets the cost each edit operation adds to a candidate’s total penalty, which in turn drives the score. Shaping these costs lets you express what kinds of error are likely in your domain.

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, FuzzyPenalties};

let engine = FuzzyAhoCorasickBuilder::new()
    .fuzzy(FuzzyLimits::new().edits(2))
    .penalties(
        FuzzyPenalties::default()
            .substitution(0.7)
            .insertion(0.9)
            .deletion(0.9)
            .swap(1.0),
    )
    .build(["pattern"]);

The four costs

Defaults

The defaults are tuned so that a substitution is the most expensive edit, insertions the cheapest, with deletions and swaps in between (roughly substitution ≈ 1.43, deletion ≈ 0.91, insertion ≈ 0.52, swap ≈ 0.52). This reflects that an inserted or transposed character usually preserves more of the intended word than an outright wrong character does.

You rarely need to change these, but doing so is the right tool when you know your errors: for OCR, substitutions between look-alike glyphs should be cheap (do that via the similarity table rather than the flat substitution cost); for speech-to-text, insertions/deletions of small words might dominate.

How penalties become a score

The costs accumulate over the edits in a candidate, then feed the score:

similarity = (N - Σ penalties) / N * weight

Because the substitution cost is multiplied by (1 - sim), two symbols the similarity table rates as 0.7-similar incur only 30% of the full substitution penalty. That interplay — flat costs for insert/delete/swap, similarity-scaled cost for substitution — is what lets the engine treat 0↔o as a near-match while treating an unrelated substitution as a real error.

Tip: penalties and the threshold work together. If you find yourself pushing a penalty very high just to exclude a certain match, consider whether an edit limit or the weakest-link floor expresses your intent more directly.

Patterns & Weights

build(..) accepts anything convertible into a Pattern. For simple cases you pass strings; for finer control you construct Pattern values with per-pattern weight, limits, and identity.

Convenient conversions

use fuzzy_aho_corasick::FuzzyAhoCorasickBuilder;

// &str / String
let e1 = FuzzyAhoCorasickBuilder::new().build(["alpha", "beta"]);

// (pattern, weight)
let e2 = FuzzyAhoCorasickBuilder::new().build([("alpha", 2.0), ("beta", 1.0)]);

// (pattern, weight, max_edits)
let e3 = FuzzyAhoCorasickBuilder::new().build([("alpha", 1.0, 2u8), ("beta", 1.0, 1u8)]);

Weights

A pattern’s weight scales its score:

similarity = (N - penalties) / N * weight

Default weight is 1.0. Raising it above 1.0 boosts a pattern so it ranks ahead of others (and can even score above 1.0); lowering it demotes a pattern. Weights are how you say “if two patterns both match here, prefer this one” without changing thresholds.

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, Pattern};

let important = Pattern::from("error")
    .weight(2.0)                          // boost this pattern's score
    .fuzzy(FuzzyLimits::new().edits(1))   // per-pattern limits override the global default
    .custom_unique_id(42);                // stable identity for uniqueness-aware selection

let normal = Pattern::from("warning").fuzzy(FuzzyLimits::new().edits(2));

let engine = FuzzyAhoCorasickBuilder::new()
    .case_insensitive(true)
    .build([important, normal]);

Pattern builder methods

Unique ids

custom_unique_id matters for the .non_overlapping_unique() SearchOptions: patterns sharing an id (or, absent an id, the same pattern index) count as “the same thing”, so only one match per id is kept. This is useful when you register several spellings/aliases of one entity and want at most one hit for it.

Display

Pattern implements Display, so m.pattern formats as the underlying pattern string in println! and friends — handy when reporting matches.

Search & Selection

A search returns Result<FuzzyMatches, SearchError> — the matches found at or above the threshold, or an error if the haystack is too large to index (see Fallibility). A single entry point, search, covers every case; how the results are ordered and whether overlaps are resolved is chosen through SearchOptions.

search(haystack, &SearchOptions)

There is one search method. SearchOptions bundles the similarity threshold with an order and an overlap resolver, built with chainable setters:

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, SearchOptions};

let engine = FuzzyAhoCorasickBuilder::new()
    .fuzzy(FuzzyLimits::new().edits(1))
    .case_insensitive(true)
    .build(["hello", "world"]);

let opts = SearchOptions::new()
    .threshold(0.8)      // minimum similarity (default 0.0 — keep everything)
    .sorted()            // Order::Default: similarity, then longer patterns, then position
    .non_overlapping();  // Overlap::NonOverlapping: greedily drop overlaps in the chosen order
let matches = engine.search("helllo wolrd", &opts).unwrap();

SearchOptions::default() (or SearchOptions::new()) is the primitive: it returns the single best-scoring match for each distinct (start, end, pattern) span, unordered and with overlaps kept — the fastest result to build. Everything else is that primitive plus an order and/or an overlap resolver, which compose independently.

Order (SearchOptions::order, an Order)

Overlap (SearchOptions::overlap, an Overlap)

Overlap resolution is greedy in the current order, so choose an order whenever you resolve overlaps — e.g. .sorted().non_overlapping() yields a default-ranked non-overlapping set, and .coverage_weighted().non_overlapping_unique() yields a coverage-ranked set with at most one match per pattern id.

Fallibility

Every entry point returns Result<_, SearchError>. The only failure is a haystack with more than u32::MAX grapheme clusters (~4 GiB ASCII): the engine indexes positions with u32, so a larger haystack returns Err(SearchError::HaystackTooLarge { graphemes }) instead of silently truncating to wrong offsets. Reach for the streaming API for inputs that large. The examples here .unwrap() for brevity; in real code propagate with ? or handle the error.

Ordering strategies

The orderings are methods on the returned FuzzyMatches; the convenience entry points above just call them for you:

• default_sort() — higher similarity first, then longer patterns, then earlier position. A good general default.
• greedy_sort() — longer patterns first, then similarity. Prefers covering more text with larger patterns.
• coverage_weighted_sort() — ranks by similarity × covered_length, so a slightly-lower-scoring long match can beat a short perfect one. Useful when short high-similarity fragments would otherwise win over the longer pattern you actually care about.

Non-overlapping selection

Raw results can overlap (several patterns, or several spellings, matching the same region). non_overlapping() greedily keeps matches in the current sort order, dropping any that overlap one already kept — so sort first, then resolve. non_overlapping_unique() additionally enforces one match per pattern identity (see unique ids).

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, SearchOptions};

let engine = FuzzyAhoCorasickBuilder::new()
    .fuzzy(FuzzyLimits::new().edits(1))
    .case_insensitive(true)
    .build(["hello", "world"]);

let matches = engine
    .search("helllo wolrd", &SearchOptions::new().threshold(0.8).sorted().non_overlapping())
    .unwrap();
let found: Vec<&str> = matches.iter().map(|m| m.pattern.as_str()).collect();
assert!(found.contains(&"hello") && found.contains(&"world"));

Working with the results

FuzzyMatches derefs to &[FuzzyMatch] and supports iter(), iter_mut(), len(), is_empty(), and IntoIterator. It also offers post-processing helpers:

• filter(pred) / retain(pred) — keep matches satisfying a predicate.
• matched_spans() / matched_strings() — the (start, end) byte ranges / matched substrings.
• replace(callback) — see Replacement.
• segment_iter(), split(), strip_prefix(), strip_suffix() — see Segmentation & Splitting.

Each FuzzyMatch carries pattern_index, pattern, start/end (byte offsets), text, similarity, and the per-type edit counts (insertions, deletions, substitutions, swaps, edits).

Segmentation & Splitting

Beyond “where are the matches”, the engine can slice a string into matched and unmatched pieces and reassemble it — useful for tokenization, cleanup, and redaction-style tasks. These build on a sorted, non-overlapping search.

Segments

A Segment is either a Matched span or the Unmatched gap between matches. segment_iter yields them in order:

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, Segment, SearchOptions};

let engine = FuzzyAhoCorasickBuilder::new()
    .fuzzy(FuzzyLimits::new().edits(1))
    .build(["input", "more"]);

for seg in engine.segment_iter("someinptandm0re", &SearchOptions::new().threshold(0.75)).unwrap() {
    match seg {
        Segment::Matched(m)   => println!("match: {:?} (as {})", m.text, m.pattern),
        Segment::Unmatched(u) => println!("gap:   {:?}", u.text),
    }
}

Reconstruction with spacing

segment_text reassembles the input, inserting spacing so that matched tokens are separated from the surrounding text — a quick way to “tokenize” run-together text:

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, SearchOptions};
let engine = FuzzyAhoCorasickBuilder::new()
    .fuzzy(FuzzyLimits::new().edits(1))
    .build(["input", "more"]);
let matches = engine.search("someinptandm0re", &SearchOptions::new().threshold(0.75).sorted().non_overlapping()).unwrap();
assert_eq!(matches.segment_text(), "some inpt and m0re");

Splitting on matches

Treat each fuzzy match as a delimiter and collect the pieces in between:

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, SearchOptions};

let engine = FuzzyAhoCorasickBuilder::new()
    .fuzzy(FuzzyLimits::new().edits(1))
    .case_insensitive(true)
    .build(["FOO", "BAR"]);

let parts: Vec<&str> = engine.split("xxFo0yyBAARzz", &SearchOptions::new().threshold(0.8)).unwrap().collect();
assert_eq!(parts, vec!["xx", "yy", "zz"]);

FuzzyMatches::split() does the same on an already-computed result set (including empty pieces when matches touch the ends).

Stripping affixes

strip_prefix and strip_suffix remove leading/trailing fuzzy-matched (and whitespace-only) segments and return the remainder — handy for peeling boilerplate off a field:

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, SearchOptions};

let f = FuzzyAhoCorasickBuilder::new()
    .fuzzy(FuzzyLimits::new().edits(1))
    .case_insensitive(true)
    .build(["LOREM", "IPSUM"]);

// "LrEM ISuM" fuzzily matches "LOREM IPSUM"; it and the leading space are stripped.
assert_eq!(f.strip_prefix("LrEM ISuM Lorm ZZZ", &SearchOptions::new().threshold(0.8)).unwrap(), "ZZZ");
assert_eq!(f.strip_suffix("ZZZ LrEM ISuM", &SearchOptions::new().threshold(0.8)).unwrap(), "ZZZ");

All of these are convenience wrappers over a sorted, non-overlapping search followed by a method on the FuzzyMatches result, so you can mix and match with your own filtering.

Replacement

Fuzzy find-and-replace substitutes matched spans with text you choose, copying everything else through unchanged. A non-overlapping match set is selected automatically (a sorted search with overlaps resolved) and applied left-to-right.

replace with a callback

The most flexible form is FuzzyAhoCorasick::replace, which calls your closure for each match. Return Some(replacement) to substitute, or None to keep the original text:

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, SearchOptions};

let engine = FuzzyAhoCorasickBuilder::new().build(["FOO", "BAR", "BAZ"]);
let result = engine.replace("FOO BAR BAZ", &SearchOptions::new().threshold(0.8), |m| {
    (m.pattern.pattern == "BAR").then_some("###")
}).unwrap();
assert_eq!(result, "FOO ### BAZ");

The closure receives the full FuzzyMatch, so the replacement can depend on which pattern matched, the matched text, the score, or the edit counts. The return type is Into<Cow<str>>, so you can return a &str, a String, or a borrowed slice of the haystack.

FuzzyReplacer for table-driven replacement

When you just have a (pattern → replacement) table, build a FuzzyReplacer:

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, SearchOptions};

let replacer = FuzzyAhoCorasickBuilder::new()
    .case_insensitive(true)
    .fuzzy(FuzzyLimits::new().edits(1))
    .build_replacer([("hello", "hi"), ("world", "earth")]);

// '0'↔'o' is a near-match in the default table, so both fuzzy tokens are replaced.
assert_eq!(replacer.replace("hell0 w0rld!", &SearchOptions::new().threshold(0.8)).unwrap(), "hi earth!");

build_replacer takes (pattern, replacement) pairs; the pattern side accepts the same conversions as build, so you can attach weights and per-pattern limits. Reach the underlying engine with replacer.engine().

Which non-overlapping match wins?

Replacement uses the default sort before resolving overlaps, so where several matches compete for a region the higher-similarity (then longer, then earlier) one is applied. If that isn’t the behavior you want, run a search yourself with a different ordering, then call FuzzyMatches::replace(callback) on the result.

Streaming replacement

For inputs too large to hold in memory, or arriving incrementally, use the streaming variants replace_stream and replace_stream_parallel, which write the transformed output to any Write sink in constant memory. See Streaming Replace.

Custom Similarity Tables

Substitutions are scored by a similarity table: for each ordered pair of symbols it gives a similarity in 0.0..=1.0, and the substitution penalty is substitution_cost * (1 - sim). Identical symbols are 1.0 (no penalty); unrelated symbols default to 0.0 (full penalty).

The default table

Out of the box the engine ships a general-purpose table that gives a reduced penalty to substitutions between related symbols:

• vowel ↔ vowel (e.g. a↔e) — moderately similar,
• consonant ↔ consonant — mildly similar,
• common OCR/typo confusions such as 0↔o, 1↔l, 1↔i, 5↔s.

This is why, with the default configuration, hell0 fuzzily matches hello and w0rld matches world.

Providing your own

Supply a &'static Similarity built from a map of (char, char) → similarity. A LazyLock is the usual way to get a 'static:

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, structs::Similarity};
use std::sync::LazyLock;

static SIMILARITY: LazyLock<Similarity> = LazyLock::new(|| {
    Similarity::from_map([
        (('@', 'a'), 0.9),
        (('a', '@'), 0.9),
    ])
});

let engine = FuzzyAhoCorasickBuilder::new()
    .similarity(&SIMILARITY)
    .build(["cat"]);

Similarity::from_map sets the diagonal (identical pairs) to 1.0 for you and precomputes a fast lookup table for ASCII pairs, falling back to the map for non-ASCII.

Notes

• Directionality. Entries are ordered pairs. If you want @↔a to behave symmetrically, insert both ('@','a') and ('a','@'), as above.
• Replacing vs. extending. Providing a table replaces the default entirely — you get exactly the pairs you insert (plus the identity diagonal). If you want the default confusions too, reproduce them in your map.
• Single symbols only. The table maps one symbol to one symbol. For equivalences spanning several graphemes (ligatures, transliterations), use multi-character mappings.
• Interaction with the floor. A high similarity makes a substitution cheap; the weakest-link floor can still reject substitutions whose similarity is below a threshold regardless of how the overall score comes out.

The Weakest-Link Floor

The default scoring is additive: each edit contributes independently, so a single very-dissimilar substitution can be diluted by an otherwise-excellent long match. One sim = 0 substitution in a 20-grapheme pattern still scores ~0.93 and would pass a 0.8 threshold.

Sometimes that’s wrong: you want to say no individual substitution may be too weak, no matter how good the rest of the match is. That is the “weakest link” bound from the underlying research, exposed as min_symbol_similarity.

Setting a floor

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, SearchOptions};

let engine = FuzzyAhoCorasickBuilder::new()
    .fuzzy(FuzzyLimits::new().edits(1))
    .case_insensitive(true)
    .min_symbol_similarity(0.3) // reject any substitution below 0.3 similarity
    .build(["vestibulum"]);

// e↔x has similarity 0 -> the substitution is rejected outright.
assert!(engine.search("vxstibulum", &SearchOptions::new().threshold(0.8)).unwrap().is_empty());

// u↔o has similarity 0.6 -> allowed.
assert_eq!(engine.search("vestibulom", &SearchOptions::new().threshold(0.8)).unwrap().len(), 1);

Any character-level substitution whose similarity is below the floor is discarded immediately, before it can contribute to a score. A candidate that would need such a substitution simply isn’t produced.

What it applies to

• Only character-level substitutions. Exact matches are unaffected (similarity 1.0), and explicit mappings carry their own scores and bypass the floor.
• Independent of the threshold. The floor is a per-symbol gate; the threshold is a whole-match gate. A match must pass both.

When to use it

Reach for the floor when a wrong-but-diluted character would be a semantic error, not just a lower score — for instance in name/entity matching, where turning Petr into Pxtr should not count as a near-match no matter how long the surrounding name is. The default is 0.0 (no floor), preserving the purely additive behavior.

Multi-Character Mappings

The similarity table maps single graphemes to single graphemes. For equivalences that span several graphemes — ligatures and transliterations like æ↔ae, ß↔ss, ks↔x — register a mapping.

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, SearchOptions};

let engine = FuzzyAhoCorasickBuilder::new()
    .case_insensitive(true)
    .fuzzy(FuzzyLimits::new().edits(1))
    .mapping("æ", "ae")               // exact equivalence (score 1.0, penalty-free)
    .mapping("ks", "x")
    .mapping_scored("ph", "f", 0.9)   // near-equivalence carrying a small penalty
    .build(["encyclopaedia", "alexander"]);

// 'æ' in the haystack matches "ae" in the pattern (and vice versa):
assert_eq!(engine.search("encyclopædia", &SearchOptions::new().threshold(0.95)).unwrap().len(), 1);
// 'x' in the pattern matches "ks" in the haystack:
assert_eq!(engine.search("aleksander", &SearchOptions::new().threshold(0.95)).unwrap().len(), 1);

Semantics

• Bidirectional. mapping("æ", "ae") lets either side stand in for the other, in the pattern or the haystack.
• Counts as one substitution. A mapping is a single substitution against the edit limits, regardless of how many graphemes each side has. With edits(0) even a free mapping like æ↔ae is rejected, exactly like an ordinary substitution.
• Scored. mapping(a, b) is an exact equivalence (score 1.0, no penalty). mapping_scored(a, b, s) is a near-equivalence; the applied penalty is substitution * (1 - s), just like a similarity-scaled substitution.
• Case-folded like patterns. Both sides are grapheme-split and case-folded the same way as patterns, so they line up with the folded haystack at search time.

Cost and when to use it

Mappings are precomputed at build time and stored out-of-line, so configuring none leaves the search hot path completely unchanged — you pay nothing for the feature unless you use it.

Use mappings for script- and orthography-level equivalences that a single-symbol table can’t express: German ß↔ss, Nordic æ/ø/å transliterations, Cyrillic↔Latin name variants, or domain shorthands. For plain look-alike single characters (0↔o), the similarity table is the lighter-weight tool.

Note: mappings are one of the features the bit-parallel pre-filter cannot model, so an engine configured with mappings falls back to the full search when pre-filtered. Correctness is unaffected; only the pre-filter speedup is forgone.

Streaming Search

A single search call loads the whole haystack into memory and is limited to inputs under ~4 GiB (grapheme positions are u32 internally). The streaming API instead consumes a Read source incrementally in bounded, overlapping windows, so it runs in constant memory regardless of input size — files, sockets, pipes, decompressors — and reports matches at absolute u64 byte offsets.

Windows overlap by the longest possible match (computed automatically from the patterns and edit limits), so a match spanning a window boundary is never split, and each window “owns” the matches whose start falls in its non-overlap prefix — every match is emitted exactly once, with no deduplication on your side.

Three entry points

All yield StreamMatch, which owns its matched text (so it is Send and outlives the transient window):

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits};
use std::fs::File;

let engine = FuzzyAhoCorasickBuilder::new()
    .fuzzy(FuzzyLimits::new().edits(1))
    .case_insensitive(true)
    .build(["needle"]);

// 1) Callback (single-threaded)
engine.search_stream(File::open("huge.txt")?, 0.8, |m| {
    println!("{}..{}: pattern #{} ({:.2})", m.start, m.end, m.pattern_index, m.similarity);
})?;

// 2) Iterator — lazy; windows are read and searched on demand
for m in engine.stream_matches(File::open("huge.txt")?, 0.8) {
    let m = m?; // io::Result<StreamMatch>
    println!("{}..{}", m.start, m.end);
}

// 3) Parallel — fans windows across a thread pool (dependency-free std::thread)
let threads = std::thread::available_parallelism().map_or(1, |n| n.get());
engine.search_stream_parallel(File::open("huge.txt")?, 0.8, threads, |m| { /* ... */ })?;
Ok::<(), std::io::Error>(())

Going fast

The search is CPU-bound — a BFS from every position, roughly independent of window size — so the parallel form is how you get throughput: windows are independent and share the immutable engine, scaling close to linearly with cores. In search_stream_parallel, on_match is invoked on the calling thread as results arrive (in arbitrary order), so it needs no synchronization.

max_match_graphemes() exposes the auto-computed overlap if you’d rather window the input yourself. See examples/streaming.rs for a full multi-GiB demo with a progress bar.

Errors

The callback forms return io::Result<u64> (the total bytes read), propagating any reader error. The iterator yields one Err if the reader fails, after which iteration ends.

Streaming Replace

replace_stream is the streaming counterpart of replace: it reads from a Read, writes the transformed stream to a Write in constant memory, substituting matches as they are found and copying everything else through verbatim. It returns the number of bytes written.

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits};

let engine = FuzzyAhoCorasickBuilder::new()
    .fuzzy(FuzzyLimits::new().edits(1))
    .case_insensitive(true)
    .build(["needle"]);

let mut out = Vec::new();
// "neeedle" has one extra 'e' (an insertion); it is replaced, the rest copied through.
engine.replace_stream("a neeedle b".as_bytes(), &mut out, 0.8, |_m| Some("X")).unwrap();
assert_eq!(String::from_utf8(out).unwrap(), "a X b");

The FuzzyReplacer turnkey form uses its configured (pattern → replacement) table:

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits};
let replacer = FuzzyAhoCorasickBuilder::new()
    .case_insensitive(true)
    .fuzzy(FuzzyLimits::new().edits(1))
    .build_replacer([("hello", "hi"), ("world", "earth")]);

let mut out = Vec::new();
replacer.replace_stream("hell0 w0rld!".as_bytes(), &mut out, 0.8).unwrap();
assert_eq!(String::from_utf8(out).unwrap(), "hi earth!");

Semantics and limitations

• Per-window selection. Matches are chosen per window (as in the streaming search), so at a window boundary overlaps are resolved left-to-right — the earlier-starting match wins — rather than by the global ranking a whole-input replace uses. For inputs where matches are separated by non-matching text, the two agree exactly.
• Replacement can’t borrow the match. The replacement type is independent of the match, so it may borrow external data (e.g. a replacement table) but not the transient matched text. Return an owned String if you need to derive the replacement from m.text.
• Buffer the writer. Wrap the writer in a BufWriter for throughput.

Parallel replace

replace_stream_parallel(reader, writer, threads, threshold, callback) fans the CPU-bound search across a thread pool while reassembling the output in stream order on the calling thread. Because output is inherently ordered, only the search is parallelized — the callback and writer stay on the calling thread (no Send/Sync bounds), and the result is byte-identical to replace_stream.

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits};
let engine = FuzzyAhoCorasickBuilder::new().fuzzy(FuzzyLimits::new().edits(1)).build(["needle"]);
let mut out = Vec::new();
let threads = std::thread::available_parallelism().map_or(1, |n| n.get());
engine.replace_stream_parallel("a needle b".as_bytes(), &mut out, threads, 0.8, |_m| Some("X")).unwrap();
assert_eq!(String::from_utf8(out).unwrap(), "a X b");

On a 10-core machine this scales roughly 1.9× / 3.7× / 6.3× at 2 / 4 / 8 threads on a 32 MiB input — near-linear until the serial output reassembly and memory bandwidth take over. At one thread it matches the single-threaded form exactly, so there’s no penalty for using it when the input turns out small. See examples/replace_bench.rs.

Bounding Worst-Case Work

The core search is exact: it explores every viable edit path and returns the best match for each span. Built-in pruning (edit limits, the threshold, and per-node ceilings) keeps this fast for typical inputs. But combining a high edit budget with a low threshold can explode the state space — a lot of insertion/deletion paths become viable while yielding few if any extra matches. Two knobs bound that.

Beam search — beam_width(K)

Whenever a search window’s active frontier exceeds 2·K states, it is sorted by penalty and truncated to the K lowest-penalty candidates. This trades exactness for bounded time and memory; a larger K is more accurate but slower.

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits};

let engine = FuzzyAhoCorasickBuilder::new()
    .fuzzy(FuzzyLimits::new().edits(4))
    .case_insensitive(true)
    .beam_width(100) // keep the 100 best candidates when the frontier grows
    .build(["saddam", "hussein", "vestibulum"]);

Automatic beam — auto_beam(budget, width)

auto_beam is a safety valve rather than an always-on approximation. The search runs the exact unlimited exploration until it has expanded more than budget states (counted across all start positions); only then does it beam the frontier to width for the remainder. Ordinary searches never approach budget, so they stay exact and unaffected — only genuine blow-ups get capped.

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits};

let engine = FuzzyAhoCorasickBuilder::new()
    .fuzzy(FuzzyLimits::new().edits(6))
    .case_insensitive(true)
    .auto_beam(200_000, 100) // exact under 200k states, then beam to width 100
    .build(["saddam", "hussein", "vestibulum"]);

An explicit beam_width always takes precedence over auto_beam.

Which to choose

• Neither — the default. Correct and fast for reasonable limits/thresholds. Start here.
• auto_beam — the recommended safety net for untrusted or highly variable input: exact in the common case, bounded in the pathological one. Set budget generously (hundreds of thousands) so real searches never trip it.
• beam_width — when you always run with aggressive limits and want a hard, predictable bound every time, accepting that some low-ranked fuzzy matches may be missed.

If a search is unexpectedly slow, you are almost always combining a high edit budget with a low threshold. Raising the threshold or tightening limits is the first fix; auto_beam is the belt-and-braces one.

The Bit-Parallel Pre-Filter

The core search is thorough but pays a per-position cost. When you search large inputs that are mostly non-matching text, with_prefilter() adds an opt-in fast lane: a bit-parallel (Bitap / Wu–Manber) approximate scan runs first, at hundreds of MB/s, to locate candidate regions, and the full weighted engine then re-searches only those regions.

Results are identical to a plain search with the same SearchOptions — the filter is a conservative over-approximation (a necessary condition), so it never drops a real match; it only spares the engine from scanning text that cannot contain one.

use fuzzy_aho_corasick::{FuzzyAhoCorasickBuilder, FuzzyLimits, SearchOptions};

let engine = FuzzyAhoCorasickBuilder::new()
    .fuzzy(FuzzyLimits::new().edits(1))
    .build(["vestibulum", "consectetur"]);

let pf = engine.with_prefilter(); // build once, reuse across searches
let hits = pf.search("… lorem vestibulm ipsum …", &SearchOptions::new().threshold(0.85)).unwrap();
// Same matches as engine.search(…).unwrap(), just faster on large, sparse inputs.

Why it’s sound

A match the engine accepts has a bounded number of edits: the threshold caps the total penalty a kept match may carry (P_max = N·(1 − θ/weight)), and each edit costs at least some minimum penalty. That bound becomes the bit-parallel scan’s Levenshtein budget k (a transposition counts as two unit edits), so every match the full engine could accept is guaranteed to survive the filter.

Graceful fallback

When the configuration can’t be reduced to the bit model, the wrapper transparently runs the full search instead — always correct, merely without the speedup. That happens when:

• multi-character mappings are configured (block edits don’t map to unit Levenshtein),
• a pattern is longer than 63 graphemes,
• a penalty is so low that an edit is effectively free (the budget becomes unbounded), or
• the derived budget is too large to stay selective.

pf.is_active() reports whether a usable filter was built.

When it helps

The win scales inversely with match density: on sparse inputs the engine sees only a small fraction of the text (an ~13× end-to-end speedup on a 16 MiB sample after transcode optimizations), while match-saturated inputs gain little — a wasted scan, then roughly baseline. It degrades gracefully rather than ever going wrong.

See examples/bitap_prototype.rs for the standalone algorithm, a brute-force correctness verifier, and a throughput comparison.

Tuning & Tips

The engine is built once and cheap to query repeatedly. A few habits keep searches fast and results clean.

Filter early

• Raise the threshold. A higher similarity threshold prunes weak partial matches before they expand — it improves both quality and speed. It is the single most effective knob.
• Tighten edit limits. FuzzyLimits per pattern, when you know the expected error characteristics, cuts the explored state space directly.

Shape the cost model to your domain

• Use the similarity table for look-alike single characters (OCR glyphs, homoglyphs) so those substitutions are cheap and everything else stays expensive.
• Use FuzzyPenalties to make whole edit types cheaper or pricier.
• Use the weakest-link floor when a single bad character should disqualify a match regardless of length.

Pick the right entry point

• Prefer a .non_overlapping() / .non_overlapping_unique() SearchOptions over resolving overlaps yourself.
• Use SearchOptions::default() (unordered, overlaps kept) as the fastest primitive when you want to build a custom ranking/selection pipeline.

Guard against pathological input

Combining a high edit budget with a low threshold is the classic slow case. Add auto_beam (keeps common cases exact) or an explicit beam_width when limits are high and thresholds low, especially for untrusted input.

Reach for the specialized paths when they fit

• Streaming for large or incremental inputs (constant memory), and its parallel forms to use all cores on CPU-bound scans.
• The pre-filter for large, sparse inputs where most of the text can’t match — a big speedup with identical results, and a safe fallback when it doesn’t apply.

Memory footprint

The compiled automaton is immutable and shared by reference (&FuzzyAhoCorasick) — build it once and query it from as many threads as you like without copying it. Each search allocates only bounded, transient per-call state (the BFS frontier, a visited-set for state dedup, and a best-match-per-span map). That state scales with the haystack length and match density, not with the automaton’s pattern count, so per-query memory stays flat even for automata with millions of patterns. This makes the engine cheap to fan out across many concurrent queries: the resident footprint is the one shared automaton plus a small, bounded slice per in-flight search.

Size expectations

A single search call keeps grapheme positions as u32, so one haystack must contain at most u32::MAX grapheme clusters (roughly a 4 GiB ASCII input). A larger haystack returns Err(SearchError::HaystackTooLarge) rather than silently truncating positions to wrong offsets — for inputs that big (or unbounded streams), use the streaming API, which windows the input and reports absolute u64 offsets.

Measuring

Benchmark with your real patterns and representative text — throughput depends heavily on pattern count/length, edit budget, threshold, and match density. The repository ships Criterion benchmarks (cargo bench) and the bitap_prototype / replace_bench examples as starting points.

Migrating from 0.4.x to 0.5.0

Version 0.5.0 is a breaking release. Two themes drive the changes:

1. One search entry point. The seven search_* methods (and the threshold-taking segmentation/replace helpers) collapse into a single search(haystack, &SearchOptions), where a SearchOptions bundles the threshold with a ranking Order and an Overlap resolver.
2. Fallible instead of panicking. Searching a haystack larger than u32::MAX grapheme clusters (~4 GiB of ASCII) used to panic; it now returns Err(SearchError::HaystackTooLarge). search and the helpers built on it return Result<_, SearchError>.

Everything below is a mechanical change — no behavior changed for in-range inputs.

At a glance

1. search is now search(haystack, &SearchOptions) and fallible

SearchOptions carries three things: the threshold, an Order (how matches are ranked), and an Overlap (how overlaps are resolved). Build it with chainable setters. Map each old method to the options that reproduce it:

// 0.4.x
let matches = engine.search_non_overlapping("helllo wolrd", 0.8);

// 0.5.0
use fuzzy_aho_corasick::SearchOptions;
let matches = engine
    .search("helllo wolrd", &SearchOptions::new().threshold(0.8).sorted().non_overlapping())
    .unwrap();

The default SearchOptions::new() is Order::Unsorted + Overlap::Keep — i.e. the old search_unsorted, the fast raw-best-per-span result. .sorted() is the old default search.

Handling the Result

search (and split / strip_prefix / strip_suffix / segment_iter / segment_text / replace) now return Result<_, SearchError>. If you were relying on the old panic, .unwrap() reproduces it; otherwise propagate with ?. The only error is SearchError::HaystackTooLarge (haystack over u32::MAX graphemes) — for inputs beyond that, use the streaming API.

Reuse options as a const

The builder methods are const fn, so a fixed configuration can be defined once:

use fuzzy_aho_corasick::SearchOptions;
const OPTS: SearchOptions = SearchOptions::new().threshold(0.8).non_overlapping();
let matches = engine.search("helllo wolrd", &OPTS).unwrap();

2. Segmentation helpers take &SearchOptions; strip_postfix → strip_suffix

split, strip_prefix, strip_suffix, segment_iter, and segment_text now take a &SearchOptions instead of a bare threshold, and are fallible. And strip_postfix was renamed to strip_suffix to match std vocabulary.

// 0.4.x
let rest  = engine.strip_prefix("LrEM ISuM ZZZ", 0.8);
let start = engine.strip_postfix("ZZZ LrEM ISuM", 0.8);

// 0.5.0
use fuzzy_aho_corasick::SearchOptions;
let rest  = engine.strip_prefix("LrEM ISuM ZZZ", &SearchOptions::new().threshold(0.8)).unwrap();
let start = engine.strip_suffix("ZZZ LrEM ISuM", &SearchOptions::new().threshold(0.8)).unwrap();

3. replace: options before the callback

The callback now comes last, with the options in the middle (so the closure reads cleanly at the call site), and it’s fallible.

// 0.4.x — (text, callback, threshold)
let out = engine.replace("FOO BAR", |m| /* … */ Some("###"), 0.8);

// 0.5.0 — (text, &SearchOptions, callback)
use fuzzy_aho_corasick::SearchOptions;
let out = engine
    .replace("FOO BAR", &SearchOptions::new().threshold(0.8), |m| /* … */ Some("###"))
    .unwrap();

4. Streaming replace: threshold before the callback

replace_stream and replace_stream_parallel moved the threshold ahead of the callback (matching the closure-last convention). These still take a bare f32 threshold (not SearchOptions).

// 0.4.x
engine.replace_stream(reader, writer, |m| Some("X"), 0.8)?;
engine.replace_stream_parallel(reader, writer, threads, |m| Some("X"), 0.8)?;

// 0.5.0
engine.replace_stream(reader, writer, 0.8, |m| Some("X"))?;
engine.replace_stream_parallel(reader, writer, threads, 0.8, |m| Some("X"))?;

FuzzyReplacer::replace also takes &SearchOptions now:

// 0.4.x
replacer.replace("hell0 w0rld", 0.8)?;
// 0.5.0
replacer.replace("hell0 w0rld", &SearchOptions::new().threshold(0.8))?;

5. Similarity::from_map takes an iterator; FxHashMap is no longer public

from_map now accepts any IntoIterator<Item = ((char, char), f32)>, so you no longer construct (and can no longer import) the crate’s FxHashMap — pass an array, Vec, or any map directly.

// 0.4.x
use fuzzy_aho_corasick::structs::{Similarity, FxHashMap};
let mut map = FxHashMap::default();
map.insert(('@', 'a'), 0.9);
map.insert(('a', '@'), 0.9);
let sim = Similarity::from_map(map);

// 0.5.0
use fuzzy_aho_corasick::structs::Similarity;
let sim = Similarity::from_map([
    (('@', 'a'), 0.9),
    (('a', '@'), 0.9),
]);

6. FuzzyMatch::notes was removed

The debug-only notes field on FuzzyMatch (present only in debug builds) is gone. It was a footgun — code that read it wouldn’t compile in release. If you were using it for diagnostics, enable the crate’s tracing during development instead.

Not breaking, but new

• SearchError — the new public error type returned by the fallible methods.
• SearchOptions / Order / Overlap — the new options types, re-exported at the crate root.
• const fn builders on SearchOptions, so options can be const/static.

If something isn’t covered here, the compiler is your guide: every removed/renamed method is a hard error pointing at the call site, and the mappings above cover each one.

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.

The fuzzy search

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.

Acknowledgements

The fuzzy automaton is based on the research paper Fuzzified Aho–Corasick Search Automata by Zdeněk Horák, Václav Snášel, Ajith Abraham, and Aboul Ella Hassanien (IAS 2010).

The crate adapts the paper’s core idea — a fuzzified Aho–Corasick automaton with a similarity-aware transition model — into an additive, length-normalized scoring scheme with per-edit-type penalties and limits, and extends it with transpositions, multi-character mappings, the weakest-link floor, streaming, and a bit-parallel pre-filter. The How It Works chapter describes the resulting engine.

Project links

• Repository: https://github.com/kakserpom/fuzzy-aho-corasick-rs
• crates.io: https://crates.io/crates/fuzzy-aho-corasick
• API docs: https://docs.rs/fuzzy-aho-corasick

License

The crate is distributed under the MIT License. See the LICENSE file for details.

Contributing

Issues and pull requests are welcome on GitHub. The test suite (cargo test), Clippy (cargo clippy --all-targets -- -D warnings), and formatting (cargo fmt --all -- --check) all run in CI; running them locally before opening a PR keeps the loop fast.