--- title: "A Deep (and Fuzzy) Dive Into Search" url: https://daily.dev/posts/a-deep-and-fuzzy-dive-into-search-jxxbasv0v source_url: https://blog.serenedb.com/fuzzy-search-deep-dive type: article source: "Programming Digest" published: 2026-08-17T10:04:17.415Z updated: 2026-08-17T10:04:50.895Z tags: ["sql", "full-text-search"] reading_time: 15 upvotes: 0 comments: 0 language: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # A Deep (and Fuzzy) Dive Into Search **[Programming Digest](https://daily.dev/sources/programmingdigest)** · 15 min read · 0 upvotes · 0 comments ## Summary 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. ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: ## 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._ ## Similar posts on daily.dev - [Fuzzy String Matching in Django and PostgreSQL](https://daily.dev/posts/fuzzy-string-matching-in-django-and-postgresql-dulfdgbr5) · Planet Python · 1 upvotes · 0 comments - [Lexical, Fuzzy, and Semantic Search Compared with DynamoDB and Amazon Bedrock](https://daily.dev/posts/lexical-fuzzy-and-semantic-search-compared-with-dynamodb-and-amazon-bedrock-ev1yry241) · Medium · 0 upvotes · 0 comments - [Fast and Easy Levenshtein distance using a Trie](https://daily.dev/posts/fast-and-easy-levenshtein-distance-using-a-trie-pwlrstj2x) · Hacker News · 0 upvotes · 0 comments --- Tags: [#sql](https://daily.dev/tags/sql), [#full-text-search](https://daily.dev/tags/full-text-search) [View this post on daily.dev](https://daily.dev/posts/a-deep-and-fuzzy-dive-into-search-jxxbasv0v)