Six years ago, when we first shipped fuzzy search (yes, without agents!), we wrote up the two algorithms that sit underneath it. The search engine has the same name but a new home since then. IResearch is now the search core of SereneDB and you reach it through SQL instead of a bespoke query language but the theory behind the implementation has not aged a day. This is that article, rewritten for where the code actually lives today.

"Fuzzy search" is an umbrella term for a family of approximate-matching algorithms. Each one defines some similarity measure between a query term and the terms in a dictionary, so the engine can decide which results are close enough to show and in what order. In this post I'll walk through the two that matter most, because they are genuinely different tools for different jobs:

• Approximate matching based on Levenshtein distance
• Approximate matching based on n-gram similarity

I'll go deep on each, flag the problems you hit when implementing them at scale and show how both are exposed in SereneDB today.

Why fuzzy search at all?​

We deal with unstructured, imperfect text everywhere. Web search taught a whole generation that being inexact is normal: you fat-finger a query on a phone and expect the typo to be fixed for you. But it goes well beyond autocorrect:

• Linguistics. Identifying cognates across dictionaries is central to historical linguistics and cognates are, by definition, not identical.
• Bioinformatics. A DNA sequence is an absurdly long string over a four-letter alphabet (ACGT); quantifying variation between sequences is approximate string matching.
• Records and search. Deduplicating people, products or addresses means matching "Jon Smith" to "John Smith" and "priorty_queue" to "priority_queue".

All of these need a way to say how close two strings are. Let's start with the most famous answer.

Approximate matching based on Levenshtein distance​

The Levenshtein distance between two words is the minimum number of insertions, deletions or substitutions needed to turn one into the other.

For example, the distance between foo and bar is 3, because every letter has to be substituted:

foo -> boo -> bao -> bar

Formally, the distance between strings $a$ and $b$ (of lengths $|a|$ and $|b|$) is $\operatorname{lev}_{a,b}(|a|, |b|)$, where:

Treat Levenshtein distance as our relevance measure and the goal becomes: for a given input, find the closest terms in the dictionary.

The classic Wagner–Fischer algorithm computes this with dynamic programming in $O(|a| \cdot |b|)$ time, with memory linear in the shorter string if you keep one row at a time. That's fine for comparing two words and hopeless at "web scale", where a real dictionary holds hundreds of thousands of terms and you'd have to run it against every single one.

The automaton trick​

In 2002, Klaus U. Schulz and Stoyan Mihov published a beautiful result: for any fixed distance $n$ and input word $W$ of length $N$, you can build a deterministic automaton $A(W)$ that accepts every string within Levenshtein distance $n$ of $W$ and you can build it in time and space linear in $N$.

Once you have $A(W)$, you intersect it with the term dictionary. If the dictionary is a trie (or an FST), the automaton walks the tree and prunes entire subtrees the moment they can no longer lead to an accepting state. Say the dictionary holds avocado, avalon, avalanche and cargo:

Searching for terms within distance 1 of kargo, the automaton never descends into the av- subtree: aligning the query's k with the dictionary's a already costs one edit and the next character (a against v) forces a second, which exceeds the limit of 1. The whole left branch is pruned and only cargo survives. We touch a handful of nodes instead of scoring the entire dictionary.

So the real task is:

Given an input word $W$ of length $N$ and a maximum edit distance $n$, build a deterministic finite automaton (DFA) that accepts a word $V$ iff $\operatorname{lev}(W, V) \le n$.

Building it up from an NFA​

It's easier to first draw a non-deterministic finite automaton (NFA) and worry about determinizing later. Here is the NFA for foobar at distance 1:

Read it as a grid. The bottom lane (e=0) is "no edits spent yet"; the top lane (e=1) is "one edit spent". Each state is an (index, edits) pair. Four families of transitions leave a state $I^{J}$ (index $I$, $J$ edits):

• Match: $I^{J} \to (I{+}1)^{J}$, consuming the correct next character of $W$. These are the horizontal edges.
• Insertion: $I^{J} \to I^{J+1}$. An extra character in the candidate, so spend one edit and stay at the same position.
• Substitution: $I^{J} \to (I{+}1)^{J+1}$. Wrong character, so spend one edit and advance.
• Deletion: $I^{J} \to (I{+}2)^{J+1}$. A character of $W$ is missing from the candidate, so skip it. (Deleting $K$ consecutive characters reaches $(I{+}K{+}1)^{J+K}$.)

The moment you spend an edit you move up a lane and at distance 1 the top lane only has match edges left, because you're out of budget. That's why we say the flow "transfers to the upper lane" as soon as an edit happens.

Raising the budget to 2 just adds a third lane and the deletion edges that skip two characters at once (an $I^{J} \to (I{+}3)^{J+2}$ family). Each state gains $O(n)$ outgoing edges. This is the pattern we now need to bound.

Making it linear​

The naive powerset construction for the DFA gives $O(2^{(n+1)N})$ states. It's clearly far too loose given how regular the NFA is. Schulz and Mihov tightened it in three steps:

1. Locality. From position $i$ you can never reach past $i+n$ by inserting, nor before $i-n$ by deleting. So at most $2n+1$ NFA states are ever "live" at a given position and the powerset over them has $2^{2n+1}$ members. That alone drops us to $O(2^{2n+1} N)$ states.
2. Subsumption. State $I^{J}$ subsumes any $(I{\pm}K)^{J+K}$ with $K \le n - J$: the other state sits up to $K$ positions away and paid $K$ extra edits to get there, so everything it can still accept the cheaper state accepts too. Keeping it around is pointless. This removes the exponential factor entirely: $O(n^2 N)$ states.
3. Parametrization. The transitions depend only on the distribution of the current character relative to position $I$, not on $I$ itself. That kills the dependency on $N$, the last thing standing between us and linear time.

The key object in step 3 is the characteristic vector. For a character $c$, $\chi(c, W, I)$ is a bit set of length $\min(2n+1,\ |W|-I)$ whose bit $k$, counting from 0, is 1 iff $W_{I+k} = c$. Index $I$ means $I$ characters consumed, so $W_{I}$ is the character up next and bit 0 tells you whether the match transition is available at all. It answers "where, in the next few characters of $W$, does $c$ appear?" For foo:

The last one is a single bit because only one character of foo is left to look at.

Because only $2n+1$ states matter at any position, we can enumerate all $2^{2n+1}$ possible character distributions and, for each, list which states become reachable. Doing that for distance 1 turns up just five distinct reachable state sets, the parametric states:

Now the DFA transition function $\Delta$ is a small lookup keyed by (parametric state, characteristic vector). For distance 1 it fits in one table:

Schulz and Mihov generalized $\Delta$ for arbitrary $n$. Build it once and you can then instantiate the DFA $A(W)$ for any word $W$ in a single linear pass over its characters. We went from $O(n^2 N)$ down to $O(N)$ and that is what makes Levenshtein search practical. In IResearch $\Delta$ is ParametricDescription and DefaultPDP hands out one lazily built instance per (distance, transpositions) pair, nine slots in total. The per-term DFA comes out of MakeLevenshteinAutomaton, wrapped by the ByEditDistance filter.

They also showed that a tiny addition to $\Delta$ buys you Damerau–Levenshtein distance, which treats a transposition of adjacent characters as a single edit. foobar → foobra is distance 2 under plain Levenshtein but distance 1 under Damerau–Levenshtein, much closer to how humans actually mistype.

How a fuzzy query runs​

Putting it together, a ts_levenshtein query in SereneDB flows like this:

The dictionary walk hands back more than a list of terms. Each accepted term carries the distance it was accepted at and the filter turns that into a per-term boost of $1 - d / \min(|V|, |W|)$. An exact hit therefore scores above a term accepted at the maximum distance, so the accepted terms rank against each other instead of all arriving with the same score.

Caveats​

$\Delta$ stores one transition per (parametric state, characteristic vector) pair, so its size is the number of parametric states times $2^{2n+1}$. The state count is what explodes with $n$:

• $n=1$: $5 \cdot 2^{3} = 40$ transitions
• $n=2$: $30 \cdot 2^{5} = 960$
• $n=3$: $196 \cdot 2^{7} = 25{,}088$
• $n=4$: $1{,}353 \cdot 2^{9} = 692{,}736$

That growth makes very large distances impractical, so SereneDB caps the edit distance at 4 for Levenshtein and 3 for Damerau–Levenshtein. Beyond that "fuzzy" stops meaning anything useful anyway.

There's also a lovely trick for squeezing one more unit of distance out of a smaller automaton. The edit distance is invariant under reversal: $\operatorname{lev}(W, V) = \operatorname{lev}(W', V')$ for the reversed strings. So by keeping two term dictionaries, one forward and one reversed (a so-called FB-trie), you can answer distance-$(n{+}1)$ queries using two distance-$n$ automata. Given how fast the DFA grows with $n$, that's a very good trade.

Trying it in SereneDB​

All of the above is behind a single SQL function, ts_levenshtein. First, a text dictionary and an inverted index over some product names:

CREATE TEXT SEARCH DICTIONARY fuzzy_dict (
    template = 'text',
    locale = 'en_US.UTF-8',
    case = 'lower',
    stemming = false,
    accent = false
);

CREATE TABLE products (id INTEGER PRIMARY KEY, name VARCHAR);

CREATE INDEX idx_products ON products
    USING inverted (id, name fuzzy_dict);

INSERT INTO products VALUES
    (1, 'cat'), (2, 'bat'), (3, 'car'),
    (4, 'dog'), (5, 'cats'), (6, 'act');

VACUUM (REFRESH_TABLE) products;

Fuzzy matching is just the @@ operator against a ts_levenshtein acceptor:

-- Distance 1: everything one edit from 'cat'
SELECT id, name FROM idx_products
WHERE name @@ ts_levenshtein('cat', 1)
ORDER BY id;
--  1 cat | 2 bat | 3 car | 5 cats | 6 act

If you drop the distance argument you get auto mode then. It picks the distance from the query length: 0 for two characters or fewer, 1 for three to five, 2 from six up.

-- No distance: 'cat' is 3 characters, so distance 1
SELECT id, name FROM idx_products
WHERE name @@ ts_levenshtein('cat')
ORDER BY id;
--  1 cat | 2 bat | 3 car | 5 cats | 6 act

This is the form you want behind a search box, where the query grows one keystroke at a time. A fixed distance of 2 is fine for catalogue and useless for ct, since at two characters almost every short token in the dictionary is within two edits. Auto mode gives ct distance 0 and catalogue distance 2 without you branching on length() in SQL.

act matches because a transposition counts as one edit. Transpositions are on by default (Damerau–Levenshtein). Turn them off and act drops out:

-- Strict Levenshtein: 'act' is now distance 2 from 'cat'
SELECT id, name FROM idx_products
WHERE name @@ ts_levenshtein('cat', 1, false)
ORDER BY id;
--  1 cat | 2 bat | 3 car | 5 cats

You can also anchor a literal prefix and only fuzz the tail. That's cheap, because the prefix walks the trie directly and the automaton only kicks in afterward:

-- Must start with 'ca', fuzzy-match the rest within distance 1
SELECT id, name FROM idx_products
WHERE name @@ ts_levenshtein('t', 1, true, 'ca')
ORDER BY id;
--  1 cat | 3 car | 5 cats

Because it's an ordinary acceptor, it composes with the rest of SQL.

SELECT id, name FROM idx_products
WHERE name @@ ts_levenshtein('cat', 1) AND id < 4
ORDER BY id;
--  1 cat | 2 bat | 3 car

Spell correction​

Being ordinary SQL also allows you to get the matched terms themselves. Point ts_levenshtein at a query log and read the accepted dictionary entries back with the ts_dict aggregates:

SELECT unnest(ts_dict_agg(term))   AS suggestion,
       unnest(ts_dict_score(term)) AS similarity,
       unnest(ts_dict_count(term)) AS searches
FROM query_log_idx
WHERE term @@ ts_levenshtein('jaket', 2)
ORDER BY similarity DESC, searches DESC;
--  jacket | 0.8 | 5
--  basket | 0.6 | 1
--  racket | 0.6 | 1

ts_dict_agg returns the terms the automaton accepted, ts_dict_score is the $1 - d / \min(|V|, |W|)$ similarity from the dictionary walk and ts_dict_count is the indexed frequency. Sorting by similarity first and frequency second is what turns three candidates at distance 2 into one correction: jacket was searched 5 times, the other two once each. Add LIMIT 1 and you have a "did you mean".

Why another kind of fuzziness?​

Raw edit distance isn't always the right lens. Two problems show up quickly.

First, length bias. A distance of 2 means something very different for a 4-letter word than for a 20-letter one. The obvious fix is to divide the distance by the length and flip it into a similarity:

$\max$ is what keeps the result inside $[0,1]$. Divide by $\min$ and the ratio can exceed 1 (a against xyz gives $3/1$), which is useless as a score. Even with $\max$ you don't get much: the maximum edit distance we can afford is small, so every long string that clears the cap lands a couple of percent below similarity 1 and the score has nothing left to discriminate with.

Second, phrases. Allowing one edit per word lets quck brwn fx match quick brown fox. But it will never match quick-witted brown fox, because per-word edit distance has no notion of extra or missing words. For that we want a measure that tolerates extra and missing material in the indexed value.

Approximate matching based on n-gram similarity​

A different way to compare two strings is by their longest common subsequence (LCS) of characters: the longer the LCS, the more similar. On its own, character LCS is too context-free: connection and fonetica share a 5-character subsequence (oneti) despite meaning nothing alike.

Grzegorz Kondrak's fix is to run the LCS over n-grams instead of single characters, so each unit carries a little local context. Compare the same pair as 3-grams:

connection -> con onn nne nec ect cti tio ion
fonetica   -> fon one net eti tic ica

Now they share zero trigrams and the spurious similarity is gone.

Formally, let $X = \langle x_1 \dots x_k\rangle$ and $Y = \langle y_1 \dots y_l\rangle$ be sequences over a finite alphabet. Write $\Gamma_{i,j}$ for a pair of prefixes, $\Gamma^{*}_{i,j}$ for a pair of suffixes and $\Gamma^{n}_{i,j}$ for a pair of n-grams starting just after positions $i$ and $j$. The base case, comparing two single n-grams, is binary:

The similarity of the full sequences is then an LCS-style recurrence over n-grams:

Normalize by the longer string to land in $[0, 1]$ and shed the length bias:

The practical beauty of this approach is that it needs no per-query automaton. You split each indexed term into n-grams, store those n-grams as terms in the dictionary and record their positions within each document. At query time you split the input the same way, look up the posting list for each n-gram and for every matched document use the recorded positions to compute the n-gram LCS and finally $s_N(X, Y)$.

That two-step shape, a cheap posting-list lookup to gather candidates followed by an exact positional check, is exactly the two-phase execution model IResearch uses across phrase, geo and nested queries. Phase 1 requires at least k of the query's n-grams to be present, which is a MinMatchDisjunction wrapped as NGramApprox in ngram_similarity_query.cpp. Phase 2 decodes positions to confirm they actually line up and it only runs for documents phase 1 already accepted.

That k is where the implementation differs from Kondrak's $s_N$. MinMatchCount derives it as $k = \lceil |X| \cdot t \rceil$ for threshold $t$ and query n-gram count $|X|$, so the score is normalized by the query alone and $|Y|$ never enters the picture. Extra material in the indexed value is free. ts_ngram('hello', 0.7) matches a title helloworld because all four query bigrams line up in order, while $s_N$ scores that pair $4/9$ and rejects it. That asymmetry is what lets a short query find a long field. It also gets you the phrase case from earlier: over a character-bigram dictionary ts_ngram('brwn fox') matches quick-witted brown fox at the default threshold, the leading extra word costing nothing. What you still pay for is typos, since each one takes out the bigrams that straddle it. quck brwn fx keeps 7 of its 11 bigrams against that title, so it needs the threshold down at 0.6.

A sharper score​

Kondrak also proposed a refinement: instead of the strictly-binary base case, count how many individual characters line up inside a matched n-gram window:

Depending on the corpus this bought Kondrak 10–20% better accuracy. The catch is that it's harder to evaluate. Here the two algorithms in this post meet: split the query into n-gram tokens, build a Levenshtein automaton for each, union them into one big automaton and use that to pull all the near-miss n-grams out of the dictionary in one sweep. For each matched n-gram you then measure the per-character similarity. Fuzzy matching all the way down.

Trying it in SereneDB​

N-gram similarity needs an ngram dictionary that records both frequency and positions:

CREATE TEXT SEARCH DICTIONARY bigram_dict (
    template = 'ngram',
    mingram = 2,
    maxgram = 2,
    frequency = true,
    position = true
);

CREATE TABLE articles (id INTEGER PRIMARY KEY, title VARCHAR);

CREATE INDEX idx_articles ON articles
    USING inverted (id, title bigram_dict);

INSERT INTO articles VALUES
    (1, 'hello'), (2, 'help'), (3, 'world'), (4, 'held'), (5, 'hero');

VACUUM (REFRESH_TABLE) articles;

Then ts_ngram takes a similarity threshold in $[0, 1]$ (default 0.7), measured against the number of n-grams in the query:

-- Strict: only near-identical titles
SELECT id, title FROM idx_articles
WHERE title @@ ts_ngram('hello')
ORDER BY id;
--  1 hello

-- Loosen the threshold and neighbours appear
SELECT id, title FROM idx_articles
WHERE title @@ ts_ngram('hello', 0.3)
ORDER BY id;
--  1 hello | 2 help | 4 held

Summary​

Neither algorithm wins outright. Levenshtein automata give you a precise, bounded notion of "within k typos", built in linear time and pruned against the term dictionary, which is perfect for autocorrect-style matching and short terms. N-gram similarity gives you a normalized score that survives extra and missing characters and rides the ordinary inverted index with no per-query construction, which is better for longer strings and partial overlap. Most real systems reach for both and sometimes combine them.

References​

• Wagner–Fischer algorithm
• Schulz & Mihov, Fast string correction with Levenshtein automata, IJDAR 5(1):67–85, 2002
• Trie | NFA | DFA
• Damerau–Levenshtein distance
• N-gram | Longest common subsequence
• Kondrak, N-gram similarity and distance, SPIRE 2005, LNCS 3772:115–126 (doi)
• IResearch source: levenshtein_utils | levenshtein_default_pdp | levenshtein_filter | ngram_similarity_filter | ngram_similarity_query | disjunction

IResearch is open source (Apache 2.0) and available as part of SereneDB. If you find this work interesting, starring us on GitHub goes a long way for an early-stage project.