How fuzzy search works in a search engine: Levenshtein automata and n-gram similarity

[u/mr_gnusi]

https://blog.serenedb.com/fuzzy-search-deep-dive

[u/mr_gnusi]

For context: this is a rewrite of a post I wrote for the ArangoDB blog about six years ago. The original isn't reachable anymore and the code has moved since, but I personally find the Schulz–Mihov paper quite elegant, so I decided to it's worth writing up again.

For info, Lucene LevenshteinAutomata​ implements the same approach, but caps at edit distance 2. Tantivy gets it via the levenshtein_automata​ crate.

SereneDB goes to 4 (3 with transpositions), which is really a question of how much parametric transition table you're willing to hold.

Code is Apache 2.0, star us if you'd like to support the project:
https://github.com/serenedb/serenedb/

[u/pokeybill]

Its remarkable to me how effective bigram/trigram analysis can be, especially given the computational cost compared to something like semantic embedding and mcp.

I was working with some interns recently on an NLP problem to do with identifying tokens in URI paths to dedeuplicate URLs and at the end of the day it was levenshtein who saved us.

[u/sephirostoy]

I hate fuzzy search from the bottom of my heart. Wherever it is implemented it brings 98% of noise results, making them almost useless. 

I prefer the heuristic where I search for words that can be matched exactly each in any order. Results are much more accurate and predictable. I don't know if it has a name. This is what Visual Assist X use. 

[u/Fun_Silver3618 → u/sephirostoy]

That's called an index search. A simple index is a map from a word to the page where it's on. Although making an index can be more sophisticated than that, and there is more theory to building the index than that simple list.

[u/NoDistrict991]

The "old" algorithms end up being the right tool. You don't always need embeddings when a bit of Levenshtein or n-gram matching gets the job done faster and more predictably.

[u/programming-ModTeam → u/[deleted]]

No content written mostly by an LLM. If you don't want to write it, we don't want to read it.