from Hacker News

Levenshtein Automata (2010)

by beau on 6/10/15, 6:37 PM with 34 comments

• by lorenzhs on 6/10/15, 9:08 PM

  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.

• by billwashere on 6/10/15, 10:20 PM

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

• by unhammer on 6/11/15, 7:55 AM

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