A deep technical walkthrough of the two fuzzy-matching algorithms behind SereneDB's search engine (formerly IResearch, now accessible via SQL). It covers Levenshtein automata: building them from an NFA, the Schulz-Mihov optimizations (locality, subsumption, parametrization) that make automaton construction linear in word length, and Damerau-Levenshtein extensions for transpositions. It then covers n-gram similarity (Kondrak's LCS-over-n-grams approach), explaining why it avoids length bias and handles missing/extra words better than edit distance, and how SereneDB implements it via a two-phase posting-list-plus-positional-check execution model. Practical SQL examples show ts_levenshtein (with auto mode and prefix anchoring) and ts_ngram usage, plus caveats on how transition table size explodes with edit distance (capping at 4/3) and a trick using reversed dictionaries to gain one extra distance unit cheaply.
Table of contents
Why fuzzy search at all? Approximate matching based on Levenshtein distance Why another kind of fuzziness? Approximate matching based on n-gram similarity Summary Questions this post answers
What is the maximum edit distance supported for fuzzy search in SereneDB's ts_levenshtein function?
SereneDB caps the edit distance at 4 for plain Levenshtein matching and 3 for Damerau-Levenshtein (which also counts transpositions as a single edit). The cap exists because the parametric transition table Delta grows explosively with distance n: 40 transitions at n=1, 960 at n=2, 25,088 at n=3, and 692,736 at n=4, making larger distances impractical. Developers tuning fuzzy search limits can track database engine internals like this on daily.dev.
How does SereneDB's ts_levenshtein auto mode pick the edit distance based on query length?
Auto mode selects distance 0 for queries of two characters or fewer, distance 1 for three to five characters, and distance 2 for six or more characters, avoiding manual branching on string length in SQL. This suits search-as-you-type boxes where a fixed distance would be too loose for short tokens and too strict for long ones. Anyone designing typo-tolerant search boxes can follow database search techniques like this on daily.dev.
What is the difference between Levenshtein automata and n-gram similarity for fuzzy text search?
Levenshtein automata give a precise, bounded notion of matching within k typos, built in linear time and pruned against a term dictionary, best for autocorrect-style matching on short terms. N-gram similarity produces a normalized score that tolerates extra or missing characters and words, runs over an ordinary inverted index with no per-query automaton construction, and suits longer strings and partial overlap; many systems combine both. Engineers choosing a fuzzy-matching strategy for search can compare approaches like these on daily.dev.