DOCSEARCHbyAlgolia
Submit Docs

FuzzyMatch

repository·main·Indexed 40 days ago

https://github.com/ordo-one/fuzzymatch

A high-performance fuzzy string matching library for Swift optimized for low-latency searching in large datasets. It features a three-stage prefiltering pipeline, support for Edit Distance and Smith-Waterman algorithms, and a zero-allocation High-Performance API for production environments. Includes tools for highlighting matched characters and a `fuzzygrep` CLI example.

Tokens
22.3K
Snippets
48
Records
86
Agent score
50%

What's inside FuzzyMatch

  1. The Match Strategy sequence

    main

    The fuzzy matching engine follows a specific sequence of checks to determine the best score for a candidate:

    1. Exact match: Returns score 1.0 immediately.
    2. Prefix edit distance: Computes distance from the start of the string.
    3. Substring edit distance: Computed only if the prefix score is < 0.7 and prefix distance != 0.
    4. Position bonuses: Applies bonuses for matches at word boundaries.
    5. Subsequence matching: If no edit distance match is found, attempts subsequence matching with bonuses.
    6. Acronym matching: For short queries (2-8 chars), attempts matching against word initials.
    7. Threshold check: Returns the best score found, provided it is above the minScore threshold.

  2. Understand Fuzz Testing invariants

    main

    The fuzz target validates five core invariants to ensure the scoring engine is reliable:

    1. No crash: The score() method must never panic, trap, or access out-of-bounds memory.
    2. Score range: If a result is returned, the score must satisfy 0.0 <= score <= 1.0 and score >= minScore.
    3. Self-match: Any non-empty string scored against itself must return score == 1.0 with kind == .exact.
    4. Empty query: An empty query must always match any candidate with score == 1.0.
    5. Buffer reuse: Scoring the same (candidate, query) pair twice with the same buffer must produce identical results (ensuring no state corruption).

  3. Understand FuzzyMatch performance vs Swift String.contains()

    main

    FuzzyMatch is designed to be significantly faster than naive substring searching on large corpora due to its multi-stage prefiltering pipeline.

    In benchmarks against a corpus of 272K candidates, the lowercased().contains() approach was 11.5x slower than FuzzyMatch (ED). Furthermore, while contains() only performs literal substring matching, FuzzyMatch provides support for typos, abbreviations, and multi-word queries which contains() cannot handle.

  4. Understand Unicode and Normalization behavior

    main

    FuzzyMatch performs all string processing on raw UTF-8 bytes using custom byte-level case folding to avoid the allocations associated with String.lowercased().

    Supported Scripts

    • ASCII
    • Latin-1 Supplement (e.g., Ä→ä, Ö→ö)
    • Greek (e.g., Α→α, Σ→σ)
    • Basic Cyrillic (e.g., А→а, Я→я)

    Normalization Types

    1. Diacritic normalization: Folds Latin-1 diacritics to ASCII base letters (e.g., café → cafe) and strips combining marks (U+0300–U+036F).
    2. Confusable-character normalization: Collapses visually similar punctuation and whitespace to canonical ASCII forms (e.g., curly quotes → ', en-dash → -, NBSP → space).

  5. Understand the FuzzyMatcher prefiltering pipeline

    main

    To maintain high performance, FuzzyMatcher uses a three-stage prefiltering pipeline to reject non-matching candidates before performing the expensive $O(nm)$ edit distance calculation.

    Pipeline Flow

    Candidate $\rightarrow$ Length Filter $\rightarrow$ Bitmask Filter $\rightarrow$ Trigram Filter $\rightarrow$ Edit Distance $\rightarrow$ Scoring/Fallback

    1. Length Bounds

    Rejects candidates whose length makes it mathematically impossible to stay within the effectiveMaxEditDistance budget.

    • Constraint: minLength = queryLength - effectiveMaxEditDistance.
    • Note: For short queries, the effectiveMaxEditDistance is tightened to prevent excessive false positives.

    2. Character Bitmask

    Uses a 64-bit bitmask to track the presence of characters (a-z, 0-9, underscores, and certain UTF-8 characters). A candidate is rejected if it is missing too many character types required by the query.

    • Adaptive Tolerance:
      • For queries $\le 3$ characters: Tolerance is 0 (strict). Substitution typos might not be detected, but transpositions still work.
      • For queries $\ge 4$ characters: Tolerance equals effectiveMaxEditDistance.

    3. Trigram Filtering

    For queries of 4+ characters, the system counts shared 3-character sequences (trigrams).

    • Pass Condition: sharedCount >= queryTrigrams.count - 3 * effectiveMaxEditDistance.
    • The factor of 3 accounts for the fact that a single edit (including transposition) can destroy up to 3 trigrams.

  6. Zero-allocation design and buffer management

    main

    The scoring hot path is designed to achieve zero heap allocations using a ScoringBuffer. This buffer holds pre-allocated arrays that are reused across calls:

    • DP rows: 3 rolling rows for edit distance.
    • Candidate bytes: A lowercased copy of the candidate.
    • Match positions: Array for tracking matches.
    • Word initials: Buffer for acronym matching.
    • Alignment state matrices: matchScore, gapScore, and traceback matrices used for DP-optimal alignment.

    Capacity Management: Buffers grow via ensureCapacity only when needed. To prevent memory bloat, buffers periodically shrink if capacity exceeds 4x the high-water mark of recent usage, reallocating to 2x the high-water mark.

  7. How Smith-Waterman mode works

    main

    Smith-Waterman mode uses bonus-driven local alignment (similar to nucleo or fzf). Instead of counting errors, it awards points for matched characters and alignment properties.

    Scoring Pipeline

    A single Dynamic Programming (DP) pass scores the best local alignment:

    1. Bitmask prefilter: Strict tolerance 0 (all query characters must appear in the candidate).
    2. Lowercase + bonus precomputation: Merged pass for boundary bonuses.
    3. Smith-Waterman DP: Three-state recurrence (match, gap, consecutive bonus).
    4. Score normalization: Maps raw integer score to 0.0-1.0.
    5. Acronym fallback: Word-initial matching competes with the SW score for short queries.

    Key Characteristics

    • Multi-word queries: Uses atom splitting with AND semantics; each word is scored independently and all must match.
    • High Throughput: Approximately ~66M candidates/sec (roughly 2x faster than Edit Distance).
    • Limitations: No transposition support (swapped characters result in no match) and no explicit prefix concept (treats all substrings equally).

  8. Use FuzzyMatcher concurrently across threads

    main

    Both FuzzyMatcher and FuzzyQuery are immutable and Sendable, making them safe to share across threads. However, each thread must use its own ScoringBuffer to avoid data races and maintain performance.

    let matcher = FuzzyMatcher()
let query = matcher.prepare("getData")
let candidates = loadLargeCandidateList()

await withTaskGroup(of: [ScoredMatch].self) { group in
    for chunk in candidates.chunks(ofSize: 100) { // conceptual chunking
        group.addTask {
            var buffer = matcher.makeBuffer() // unique buffer per task
            return chunk.compactMap { candidate in
                matcher.score(candidate, against: query, buffer: &buffer)
            }
        }
    }
}

  9. How FuzzyMatch matching modes work

    main

    FuzzyMatch supports two distinct matching modes, which can be configured via MatchConfig:

    1. Damerau-Levenshtein edit distance (Default): A penalty-driven mode that handles typos including insertions, deletions, substitutions, and transpositions. It is ideal for general typo tolerance.
    2. Smith-Waterman local alignment: A bonus-driven mode designed for finding local alignments. It is particularly useful for finding substrings or acronyms within larger strings.

    Both modes utilize multi-stage prefiltering and support zero-allocation hot paths for high performance.

  10. How Edit Distance mode works

    main

    The default mode uses Damerau-Levenshtein edit distance with a multi-phase scoring pipeline. It is designed for interactive search where users type imprecisely (misspellings, partial prefixes, abbreviations).

    Scoring Pipeline

    The pipeline runs five phases in order, taking the best score:

    1. Exact match: Case-insensitive equality (score 1.0).
    2. Prefix: Edit distance against the start of the candidate, with a prefix weight bonus.
    3. Substring: Edit distance against any substring.
    4. Subsequence: Gap-based alignment fallback for scattered matches.
    5. Acronym: Word-initial character matching (e.g., "bms" matches "Bristol-Myers Squibb").

    Key Characteristics

    • Typo tolerance: Supports transpositions (e.g., "Berkhsire" matches "Berkshire").
    • Prefix awareness: Explicit prefix phase ensures "AA" finds "AA Alcoa Corporation" rather than random substrings.
    • Performance: Slower throughput (~33M candidates/sec) due to the multi-phase pipeline and prefilters.

  11. Compare FuzzyMatch modes: Edit Distance (ED) vs Smith-Waterman (SW)

    main

    FuzzyMatch provides two distinct algorithmic modes that cater to different search requirements:

    • FuzzyMatch (ED) — Edit Distance mode: Uses Damerau-Levenshtein edit distance with multi-stage prefiltering (length bounds, character bitmask, trigrams) and DP-optimal alignment scoring. It is highly optimized for typo handling, achieving 100% accuracy in benchmark tests for typos, transpositions, and misspellings.
    • FuzzyMatch (SW) — Smith-Waterman mode: Uses MatchConfig.smithWaterman. This mode uses bonus-driven local alignment (similar to fzf or nucleo) with tiered word-boundary bonuses, affine gap penalties, and multi-word AND semantics. It is particularly effective for abbreviation/acronym matching.

    Both modes share the same prefilter pipeline and zero-allocation architecture.

    // Use Smith-Waterman mode via MatchConfig
let config = MatchConfig.smithWaterman
// (Implementation details for calling these modes would be in the API documentation)

  12. Choosing between FuzzyMatch (ED) and FuzzyMatch (SW) modes

    main

    FuzzyMatch provides two distinct matching modes based on different algorithmic foundations. Choosing the right one depends on whether you prioritize typo tolerance or throughput.

    FuzzyMatch (ED) — Edit Distance Mode

    Use this mode when accuracy and typo tolerance are the highest priority. It is based on the Damerau-Levenshtein distance and is designed to handle:

    • Adjacent-key typos (e.g., "Voeing" for "Boeing")
    • Transpositions (e.g., "Goldamn" for "Goldman")
    • Dropped characters (e.g., "blakstone" for "blackstone")
    • Doubled characters (e.g., "Gooldman" for "Goldman")

    It achieves the highest ground truth accuracy (98%) and is the strongest at handling typos (100% success rate in testing).

    FuzzyMatch (SW) — Smith-Waterman Mode

    Use this mode when maximum throughput is required. It is based on the Smith-Waterman algorithm family.

    • Performance: Offers significantly higher throughput (approx. 66M candidates/sec) compared to ED mode (approx. 33M candidates/sec).
    • Strengths: Excellent at handling abbreviations (100% success rate in testing).
    • Weaknesses: Lower typo tolerance (56% success rate) compared to ED mode, as it lacks edit-distance capabilities. It may also fail to return results for certain queries where the ED fallback would succeed.