Speed up Levenshtein comparison with automata

Babzsak / duke

Automatically exported from code.google.com/p/duke

0 stars 0 forks source link

Speed up Levenshtein comparison with automata #82

Open GoogleCodeExporter opened 8 years ago

GoogleCodeExporter commented 8 years ago

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 reported on code.google.com by lar...@gmail.com on 2 Oct 2012 at 5:08

GoogleCodeExporter commented 8 years ago

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

Original comment by lar...@gmail.com on 5 Jan 2013 at 3:16