Sachin Gupta

← AI

WritingSearch series

Fuzzy & Prefix Search

Exact match fails two ways users hit every day, typos and half-typed queries. Here is the machinery that forgives both.

By Sachin Gupta8 min read
Portrait of Sachin Gupta rendered in binary

Part three of the search series. The inverted index only matches literal keys, so a typo or a half-finished word returns nothing. Fuzzy search fixes typos with edit distance (Levenshtein), computed by a small dynamic-programming grid and run at scale with automata or n-grams. Prefix search fixes as-you-type with tries and FSTs. Worked examples throughout, plus an interactive edit-distance grid.

The inverted index is a dictionary of exact keys. Type a key that is one letter off, or only half typed, and it finds nothing. Users do both constantly. Fuzzy search forgives the typo; prefix search forgives the half-typed word. This is how.

Think of a sharp librarian. Ask for a book on "photosynthasis" and they know exactly what you meant; start to say "pay…" at the desk and they finish it with payments, payroll, PayPal before you do. Exact-match search can do neither. Fuzzy and prefix search give the index that librarian's tolerance for typos and half-finished words.

Two ways to be forgiving. Fuzzy match forgives typos by allowing a small edit distance, so paymnet still finds payment within two edits. Prefix match forgives half-typed queries, so the prefix pay completes to payment, payout, and paypal

Measuring a typo: edit distance

Type paymnet and the inverted index has no such key, so exact match returns nothing, even though payment is obviously what you meant. To act on "obviously what you meant" a search engine needs to measure how far off the typo is. The standard measure is Levenshtein edit distance: the minimum number of single-character edits, an insertion, a deletion, or a substitution, to turn one string into the other.

A few worked examples:

  • cat → cats: insert one letter. Distance 1.
  • paymnet → payment: the n and e are swapped, which plain Levenshtein counts as two substitutions (e→n and n→e). Distance 2. (A variant, Damerau-Levenshtein, counts a two-letter transposition as a single edit, giving 1.)
  • kitten → sitting: substitute k→s, substitute e→i, then insert g. Distance 3.

"Did you mean" suggestions and fuzzy matching both rest on this number: find the index terms within a small edit distance, usually 1 or 2, of what the user actually typed.

Computing it: the grid

Edit distance is computed with a small dynamic-programming grid, one row per letter of the first word, one column per letter of the second. Each cell holds the cheapest number of edits to match the two prefixes up to that point, and it is filled from three neighbors:

  • the cell above plus 1 (a deletion),
  • the cell to the left plus 1 (an insertion),
  • the cell diagonally up-left, plus 0 if the two letters match or plus 1 if they differ (a substitution, free when the letters are already equal).

Fill it left to right, top to bottom, and the bottom-right cell is the answer. For two words of length m and n it takes m times n steps, which is nothing for a single pair. That cheapness for one pair is the whole story of the section after this one.

Now watch it happen. Type any two words and the grid fills in; the lit path is one cheapest sequence of edits, and the corner cell is the distance (it starts on kitten → sitting, which is 3):

Interactive · Edit-distance gridOpen in Visualizers →
Edit distance
3
ε
s
i
t
t
i
n
g
ε
0
1
2
3
4
5
6
7
k
1
1
2
3
4
5
6
7
i
2
2
1
2
3
4
5
6
t
3
3
2
1
2
3
4
5
t
4
4
3
2
1
2
3
4
e
5
5
4
3
2
2
3
4
n
6
6
5
4
3
3
2
3
Each cell = cheapest edits to match the two prefixes. Down = delete, right = insert, diagonal = substitute (free when the letters match). The lit path is one cheapest way; the bottom-right cell is the answer.

Fuzzy search at scale

Computing the grid for one pair is cheap. Computing it against every one of a million index terms, on every query, is not. So engines never do that. They generate a short list of plausible candidates first, then run the exact grid only on those.

A Levenshtein automaton. Lucene builds a small state machine that accepts exactly the strings within edit distance k of the query, then walks the sorted term index with it, skipping whole ranges of terms that cannot possibly match. This is how Elasticsearch and OpenSearch fuzzy queries run, and it is why they cap the edit distance at 2 (the fuzziness parameter); the AUTO setting spends 0 edits on very short terms and up to 2 on longer ones, because one wrong letter in a three-letter word is a bigger deal than one in a twelve-letter word.

N-grams. Break every term into overlapping chunks, so payment becomes pay, aym, yme, men, ent, and index those. A misspelling shares most of its trigrams with the correct word, so trigram overlap surfaces good candidates without any edit math up front. Postgres pg_trgm works on this idea (it also pads each word's boundaries with spaces before splitting, so word edges match too).

Either approach narrows a million terms to a handful, and only the handful gets the exact edit-distance check.

Prefix search: matching as you type

The other everyday failure is not a mistake at all. When someone has typed pay, they have not misspelled anything; they simply are not finished. Autocomplete matches a prefix against the collection and offers completions: pay → payment, payout, paypal, updated on every keystroke.

The natural structure is a trie, a prefix tree, where each path from the root spells a prefix, so every completion of pay hangs off a single node and is found in a few steps. Production engines use compressed cousins of it. Elasticsearch's completion suggester keeps terms in an in-memory finite state transducer (FST) for very fast prefix lookup, and a simpler alternative indexes edge n-grams (p, pa, pay, paym, ...) as ordinary inverted-index terms, which turns a prefix query back into a plain term lookup on the index you already have.

What it still cannot do

Fuzzy and prefix search stretch lexical matching a long way: they forgive the slipped key and the half-typed one. But they are still matching characters. Neither one can tell that car and automobile are the same idea, because as strings they share almost nothing. To match on meaning you have to leave characters behind entirely and turn text into geometry. The next part: vector search.

Related

Tagged