In a previous Damn Cool Algorithms post, I talked about BK-trees, a clever indexing structure that makes it possible to search for fuzzy matches on a text string based on Levenshtein distance - or any other metric that obeys the triangle inequality. Today, I’m going to describe an alternative approach, which makes it possible to do fuzzy text search in a regular index: Levenshtein automata.
Read in full here:
http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata
This thread was posted by one of our members via one of our news source trackers.