--- title: A Deep (and Fuzzy) Dive Into Search | daily.dev description: A deep technical walkthrough of the two fuzzy-matching algorithms behind SereneDB's search engine (formerly IResearch, now accessible via SQL). It covers... canonical: https://daily.dev/posts/a-deep-and-fuzzy-dive-into-search-jxxbasv0v twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: A Deep (and Fuzzy) Dive Into Search | daily.dev og:description: A deep technical walkthrough of the two fuzzy-matching algorithms behind SereneDB's search engine (formerly IResearch, now accessible via SQL). It covers... og:url: https://daily.dev/posts/a-deep-and-fuzzy-dive-into-search-jxxbasv0v og:image: https://api.daily.dev/og/posts/JxXbaSV0v.png og:image:alt: A Deep (and Fuzzy) Dive Into Search og:image:width: 1200 og:image:height: 630 og:locale: 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 · 1 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 ### How does a Levenshtein automaton make fuzzy string matching fast at scale instead of comparing against every dictionary term? Schulz and Mihov showed that for a fixed edit distance n and word of length N, you can build a deterministic finite automaton in linear time and space that accepts every string within distance n of the word. Intersecting this automaton with a trie or FST-based dictionary lets the search prune entire subtrees that can't lead to an accepting state, touching only a handful of nodes instead of scoring the whole dictionary. _Engineers optimizing search relevance can track deep dives like this on daily.dev's coverage of database internals._ ### What is the practical difference between Levenshtein-distance fuzzy matching and n-gram similarity for search? Levenshtein automata give a precise, bounded notion of matches 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 on an ordinary inverted index with no per-query automaton construction, and works better for longer strings and partial phrase overlap. _Developers deciding between edit-distance and n-gram approaches can follow comparisons like this on daily.dev._ ### Why does increasing the maximum edit distance in a Levenshtein automaton get expensive so quickly? The transition table size equals the number of parametric states times 2^(2n+1), and both factors grow fast with n: distance 1 needs 40 transitions, distance 2 needs 960, distance 3 needs 25,088, and distance 4 needs 692,736. Because of this explosion, SereneDB caps edit distance at 4 for plain Levenshtein and 3 for Damerau-Levenshtein, since larger distances stop being useful anyway. _Teams tuning fuzzy search performance limits can dig into implementation trade-offs like these on daily.dev._ ## Community discussion Top comments from developers on daily.dev. **@screenwhite** · 0 upvotes > Excellent technical breakdown of how Levenshtein automata and n-gram similarity solve different fuzzy-search problems. > > The Schulz–Mihov explanation is particularly useful because it shows why intersecting an edit-distance automaton with a trie or FST can avoid comparing the query against every indexed term. > > Three implementation details are worth exploring further. > > **1. Levenshtein versus Damerau–Levenshtein semantics** > > It would be useful to clarify whether transpositions implement unrestricted Damerau–Levenshtein distance or the restricted Optimal String Alignment (OSA) variant. > > These... ## Similar posts on daily.dev - [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 - [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 - [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 - [Avoiding Entity Key Drift in a Data Lake: Step 2, When Fuzzy Matching Stops Working](https://daily.dev/posts/avoiding-entity-key-drift-in-a-data-lake-step-2-when-fuzzy-matching-stops-working-nltpxwxtv) · Towards Data Science · 0 upvotes · 0 comments - [Postgres Full-Text Search Instead of Elasticsearch](https://daily.dev/posts/postgres-full-text-search-instead-of-elasticsearch-85slaibvz) · Prisma Blog · 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) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"A Deep (and Fuzzy) Dive Into Search","url":"https://daily.dev/posts/a-deep-and-fuzzy-dive-into-search-jxxbasv0v","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/a-deep-and-fuzzy-dive-into-search-jxxbasv0v"},"datePublished":"2026-08-17T10:04:17.415Z","dateModified":"2026-09-14T08:33:14.067Z","description":"A deep technical walkthrough of the two fuzzy-matching algorithms behind SereneDB's search engine (formerly IResearch, now accessible via SQL). It covers...","image":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/efe9a4763688b12e3c9b1ccc5acd0987?_a=AQAEuop","thumbnailUrl":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/efe9a4763688b12e3c9b1ccc5acd0987?_a=AQAEuop","isAccessibleForFree":true,"articleSection":"Programming Digest","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Programming Digest","logo":"https://media.daily.dev/image/upload/t_logo,f_auto/v1/logos/4637f2287b44420aa9a44f432116043d","url":"https://daily.dev/sources/programmingdigest"},"commentCount":1,"discussionUrl":"https://daily.dev/posts/a-deep-and-fuzzy-dive-into-search-jxxbasv0v","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":0},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":1}],"keywords":"sql,full-text-search","timeRequired":"PT15M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Programming Digest","item":"https://daily.dev/sources/programmingdigest"},{"@type":"ListItem","position":3,"name":"A Deep (and Fuzzy) Dive Into Search"}]} {"@context":"https://schema.org","@type":"WebPage","@id":"https://daily.dev/posts/a-deep-and-fuzzy-dive-into-search-jxxbasv0v","comment":[{"@type":"Comment","text":"Excellent technical breakdown of how Levenshtein automata and n-gram similarity solve different fuzzy-search problems.\nThe Schulz–Mihov explanation is particularly useful because it shows why intersecting an edit-distance automaton with a trie or FST can avoid comparing the query against every indexed term.\nThree implementation details are worth exploring further.\n1. Levenshtein versus Damerau–Levenshtein semantics\nIt would be useful to clarify whether transpositions implement unrestricted Damerau–Levenshtein distance or the restricted Optimal String Alignment (OSA) variant.\nThese metrics are not always equivalent. For example, transforming “CA” into “ABC” has unrestricted Damerau–Levenshtein distance 2, but OSA distance 3.\nThis distinction matters when validating automaton results against a dynamic programming reference implementation.\n2. Candidate filtering and exactness guarantees\nThe two-phase n-gram execution model is an important optimization: posting lists generate candidates, and positional verification evaluates their similarity.\nHowever, the candidate-generation stage must be consistent with the final similarity definition. Otherwise, an overly restrictive filter could exclude valid matches before positional verification.\nBecause the article describes query-normalized n-gram similarity, it is also worth emphasizing that this score is asymmetric: similarity(query, document) need not equal similarity(document, query).\nThat asymmetry is useful for partial phrase search, but it changes the semantics compared with a symmetric string-distance metric.\n3. Unicode and normalization boundaries\nIn multilingual search, an edit should be defined over a consistent sequence representation.\nUTF-8 bytes, Unicode code points, and grapheme clusters can produce different edit distances. Normalization and tokenization policies must therefore be consistent between queries, indexed terms, and reference implementations.\nA useful validation strategy would compare automaton acceptance against independent Wagner–Fischer calculations across randomly generated strings, repeated characters, boundary-length inputs, and different edit thresholds.\nFor additional technical context on automaton construction and exact bounded-distance matching, see Levenshtein automata and fuzzy dictionary search.\nDisclosure: I am affiliated with Levenshtein.net.\nThe broader engineering lesson is that fuzzy-search correctness depends not only on fast automaton traversal, but also on metric semantics, candidate generation, and consistent text representation.","datePublished":"2026-10-14T04:12:56.309Z","url":"https://daily.dev/posts/JxXbaSV0v#c-aax9uMSIy","author":{"@type":"Person","name":"Screen White","url":"https://daily.dev/screenwhite","image":"https://lh3.googleusercontent.com/a/ACg8ocKboNVvfBJm18zU6hzAzuCHQlEu4_2vCMeXKbat1Cj3l-S-psE=s96-c"}}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/a-deep-and-fuzzy-dive-into-search-jxxbasv0v#faq","mainEntity":[{"@type":"Question","name":"How does a Levenshtein automaton make fuzzy string matching fast at scale instead of comparing against every dictionary term?","acceptedAnswer":{"@type":"Answer","text":"Schulz and Mihov showed that for a fixed edit distance n and word of length N, you can build a deterministic finite automaton in linear time and space that accepts every string within distance n of the word. Intersecting this automaton with a trie or FST-based dictionary lets the search prune entire subtrees that can't lead to an accepting state, touching only a handful of nodes instead of scoring the whole dictionary. Engineers optimizing search relevance can track deep dives like this on daily.dev's coverage of database internals."}},{"@type":"Question","name":"What is the practical difference between Levenshtein-distance fuzzy matching and n-gram similarity for search?","acceptedAnswer":{"@type":"Answer","text":"Levenshtein automata give a precise, bounded notion of matches 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 on an ordinary inverted index with no per-query automaton construction, and works better for longer strings and partial phrase overlap. Developers deciding between edit-distance and n-gram approaches can follow comparisons like this on daily.dev."}},{"@type":"Question","name":"Why does increasing the maximum edit distance in a Levenshtein automaton get expensive so quickly?","acceptedAnswer":{"@type":"Answer","text":"The transition table size equals the number of parametric states times 2^(2n+1), and both factors grow fast with n: distance 1 needs 40 transitions, distance 2 needs 960, distance 3 needs 25,088, and distance 4 needs 692,736. Because of this explosion, SereneDB caps edit distance at 4 for plain Levenshtein and 3 for Damerau-Levenshtein, since larger distances stop being useful anyway. Teams tuning fuzzy search performance limits can dig into implementation trade-offs like these on daily.dev."}}]} ```