Two simple optimizations to DP algorithm for calculating Levenstein edit distance
Posted by Kelvin on 01 Jul 2009 | Tagged as: programming
Levenstein/edit distance is a most often calculated using a dynamic programming (DP) algorithm.
The algorithm goes like this:
1. given 2 strings, s and t
2. instantiate d, an m x n matrix where m = length of s + 1 and n = length of t + 1
3. for each char in s
4. for each char in [...]