Levenshtein Automata (2010) (opens in new tab)

(blog.notdot.net)

61 pointsbeau11y ago34 comments

34 comments

9 comments · 3 top-level

lorenzhs11y ago· 6 in thread

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.

rcsorensen11y ago

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

jules11y 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.

2 more replies

lorenzhs11y 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.

jamra11y 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 ;)

darklajid11y ago

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

jamra11y 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.

1 more reply

billwashere11y 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

unhammer11y ago

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

j / k navigate · click thread line to collapse

34 comments

9 comments · 3 top-level

lorenzhs11y ago· 6 in thread

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.

rcsorensen11y ago

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

jules11y ago

2 more replies

lorenzhs11y 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.

jamra11y 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 ;)

darklajid11y ago

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

jamra11y ago

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

1 more reply

billwashere11y 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

unhammer11y ago

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

j / k navigate · click thread line to collapse