Speed up Levenshtein comparison with automata

[larsga]

From [email protected] on October 02, 2012 19:08:50

It's possible to generate a Levenshtein automaton in O(n), and to run comparison with another string in O(n), for a fixed max edit distance.

This paper has more info: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.652

Original issue: http://code.google.com/p/duke/issues/detail?id=82

[larsga]

From [email protected] on January 05, 2013 07:16:09

The Navarro paper has loads more information. Need to go through the algorithms described there to pick the right one to implement.