Levenshtein Distance

Levenshtein distance是一种常用的衡量两个字符串之间相似情况的度量。它是编辑距离的最为广泛使用的一种定义，大多数情况下编辑距离被用来特指Levenshtein距离。所谓字符串A和B的编辑距离就是指一个字符串A需要经过多少次编辑可以得到字符串B。

要计算Levenshtein距离可以用动态规划的方法来进行。

假设我们需要计算两个字符串s和t的Levenshtein距离，其中s长为m，t长为n。记d[i,j]表示将子串s[1...i]转换为t[1...j]所需的最少操作数，那么Levenshtein距离即为d[m,n]。

有如下几个事实成立：

d[i,0]=i，d[0,j]=j。因为s[1..i]可以通过i次删除操作变为空字符串t[1...0]，所以d[i,0]=i。同样的d[0,j]=0。
如果s[i]=t[j]且d[i-1,j-1]=k，那么d[i,j]=k。因为最后一个字符相同，所以在将字符串s[1...i]变为t[1...j]时，只需考虑子串s[1...(i-1)]变为t[1...(j-1)]，由条件可知需k次编辑。
在其它情况下，距离为下面三种可能操作中编辑数最小的那个：
- 插入。若d[i,j-1]=k，那么通过插入t[j]在k+1次编辑时可以得到t[1...j]。
- 删除。若d[i-1,j]=k，那么通过删除s[i]在k+1次编辑时可以得到t[1...j]。
- 替换。若d[i-1,j-1]=k，那么可以通过将s[i]替换为t[j]在k+1次编辑时得到t[1...j]。

有兴趣的童鞋见这里。

可以减少空间复杂度到O(min(m,n))，而不是O(m*n)，因为在计算过程中每次仅需要前一行和当前行的数据。
可以将距离标准化到区间[0, 1]。
如果只关心距离是否小于某个给定的阈值k，那么只需要计算对角线上宽度为2k+1的方块。此时算法可以在O(kI)的时间内结束，其中I为短字符串的长度。
对于插入、删除、替换操作可以分别赋予不同的惩罚函数。同样可以根据插入、删除、替换的字符定义不同的惩罚函数。
将矩阵的首行置为0，则该算法可以用来在文本中进行模糊查找字符串。
由于计算过程前后的相关性，这个算法很难并行。However, all the cost values can be computed in parallel, and the algorithm can be adapted to perform the minimum function in phases to eliminate depedencies. （TODO: 暂时不是很理解它的做法，先记下来）
通过检查对角线而非行，并使用延迟计算（lazy evaluation）技术，可以在O(m*(1+d))的时间内（d为Levenshtein距离）完成距离的计算。当距离很小时，这种算法比常规的动态规划要快很多。