文本相似度之Levenshtein算法 _算法

() 函数返回两个字符串之间的距离。
算法是计算两个字符串之间的最小编辑距离的算法，所谓的最小编辑距离就是把字符串A通过添加，删除，替换字符的方式转变成B所需要的最少步骤。俄罗斯科学家在1965年提出这个概念，所以叫做算法。
距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

文章插图
算法的流程：
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] 。
【文本相似度之Levenshtein算法】5：循环结束后，矩阵的最后一个元素就是最小编辑距离。

文章插图