Levenshtein Automata (2010)

http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata

by beau • 11 years ago

61 34 11 years ago

blog.notdot.net

lorenzhs11• 11 years ago

Levenshtein automata seem to pop up on here every once in a while. They are quite interesting from a theory perspective, but (like many things devised by the theory community) incredibly complex in practice. Lucene 4.0 uses them for fuzzy queries, you can read the full story of how they struggled to get them working somewhere in the Lucene blog.

If you want to implement fuzzy string matching, I would look at something like http://arxiv.org/abs/1008.1191 . The experiments look impressively fast.

rcsorensen• 11 years ago

Something of a story at http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is...

jules10• 11 years ago

The difficulty of Levenshtein automata is highly overstated. When I read that Lucene blog post I wrote an implementation in an hour, and prior to reading that post I hadn't even heard of Levenshtein automata.

lorenzhs11• 11 years ago

Yup that's the blog post I was referring to, I thought it had been on some official Lucene blog. Thanks for linking it.

jamra6• 11 years ago

The automata is incredibly slow, though it's also incredibly cool. I implemented a trie that allows for Levenshtein distance queries here github.com/jamra/LevenshteinTrie

That was just a fun project, not something I optimized or even tested appropriately.

The theory behind the trie is that the dynamic programming algorithm for Levenshtein distance gets passed to each recursive step, reducing the amount of comparisons needed.

I like this subject so I'm going to read the paper you linked ;)

darklajid4• 11 years ago

Plus, these automatons are somewhat useless (because too expensive to build/too big) when you need N >= 3

jamra6• 11 years ago

There is a trade off even in the paper that was linked. You have to disallow distances (d) that are too large when the words are small. If you have an array of words that are within distance 3 of a 3 letter word and you have many 3 letter words, you're going to have every single 3 letter word in your result set.

This is a running issue with fuzzy matching in general, but automatons are especially slow and take forever to build.

billwashere• 11 years ago

I suggest everyone check out the rest of the algorithms on that site. They are cool. http://blog.notdot.net/tag/damn-cool-algorithms

unhammer• 11 years ago

and in ocaml: https://github.com/c-cube/spelll/blob/master/spelll.ml#L124

Levenshtein Automata (2010)

Related Stories