文本相似度之Levenshtein算法

levenshtein() 函数返回两个字符串之间的 Levenshtein 距离。

 

Levenshtein算法是计算两个字符串之间的最小编辑距离的算法，所谓的最小编辑距离就是把字符串A通过添加，删除，替换字符的方式转变成B所需要的最少步骤。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念，所以叫做Levenshtein算法。

 

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

 

Levenshtein算法的流程：

1：计算strA的长度n，strB的长度m

2：如果n=0,则最小编辑距离是m，m=0，则最小编辑距离是n

3：构造一个 (m+1)*(n+1)的矩阵Arr，并初始化矩阵的第一行和第一列分别为0-n，0-m

4：两重循环，遍历strA，在此基础上遍历strB，如果strA[i]=strB[j]，那么cost=0，否则cost=1，判断Arr[j-1][i]+1,Arr[j][i-1]+1,Arr[j-1][i-1]+cost的最小值，将最小值赋值给Arr[j][i]。

5：循环结束后，矩阵的最后一个元素就是最小编辑距离。