You can get an awesome speedup for Levenshtein distance if your application only needs to compare for an edit distance of 1 (often you don't need more than that

You can get an awesome speedup for Levenshtein distance if your application only needs to compare for an edit distance of 1 (often you don't need more than that). Just tweak the algorithm to remove the extra branches beyond that. This can really help where you have a few hundred thousand strings in memory and where you only have a few ms to spare for things like auto-complete.