Fuzzy Search

Also Known As

TL;DR

Explanation

Fuzzy search uses edit distance (Levenshtein distance): the minimum number of single-character edits to transform one string to another. Distance 1 matches one typo; distance 2 matches two. Elasticsearch's fuzzy query and Meilisearch/Typesense's built-in typo tolerance handle this automatically. For PHP, similar_text() and levenshtein() compute distances. Trigram indexes (PostgreSQL pg_trgm) enable fuzzy matching with database indexes.

Diagram

flowchart LR
    QUERY[User types phyton] --> FUZZY{Fuzzy matching}
    FUZZY -->|Levenshtein distance| EDIT[Edit distance = 1<br/>1 char different]
    EDIT --> MATCH[Matches: python]
    subgraph Trigram Similarity
        TRI[Split into trigrams<br/>php = _ph ph_ php]
        OVER[Overlap score<br/>phyton vs python = 0.71]
        TRI --> OVER --> RESULT[Ranked matches]
    end
    subgraph Phonetic
        SOUND[Soundex Metaphone<br/>similar sounding words]
    end
    subgraph Tools
        MEIL[Meilisearch - built-in typo tolerance]
        PG[PostgreSQL pg_trgm extension]
        ES[Elasticsearch fuzzy query]
    end
style MATCH fill:#238636,color:#fff
style RESULT fill:#238636,color:#fff
style MEIL fill:#1f6feb,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Fuzzy distance too high — distance 3+ matches too many unrelated terms, reducing relevance.
• Fuzzy matching on every field — apply fuzzy only to text fields, not IDs or structured data.
• Not using AUTO fuzziness — Elasticsearch's AUTO:3,6 applies no fuzziness for short terms, distance 1 for 3-5 chars, distance 2 for 6+ chars.
• Levenshtein in PHP application code on every row — O(n) for n documents; use indexed fuzzy search.

Code Examples

// PHP Levenshtein on all rows — O(n), unusable at scale:
$query = 'seach';
$results = $db->query('SELECT * FROM products')->fetchAll();
$fuzzyResults = array_filter($results, function($product) use ($query) {
    return levenshtein($query, strtolower($product['name'])) <= 2;
});
// Scans all products in PHP — not viable for large datasets

// Elasticsearch fuzzy query — indexed, fast:
$query = [
    'query' => [
        'match' => [
            'name' => [
                'query' => $searchTerm,
                'fuzziness' => 'AUTO',     // AUTO:3,6 — sensible defaults
                'prefix_length' => 2,       // First 2 chars must match exactly
            ]
        ]
    ]
];

// PostgreSQL pg_trgm for simpler setups:
// CREATE INDEX idx_products_name_trgm ON products USING gin(name gin_trgm_ops);
// SELECT * FROM products WHERE name % 'seach' ORDER BY name <-> 'seach' LIMIT 10;

References

• ↗ https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-fuzzy-query.html

Tags

Related Terms