莱文斯坦距离,又称Levenshtein距离，编辑距离，俄罗斯科学家弗拉基米尔·莱文斯坦（毕业于莫斯科国立大学数学和力学系）在1965年提出，他因对纠错码理论和信息理论的贡献，于2006年获得IEEE Richard W. Hamming奖章。

定义：莱文斯坦距离也称编辑距离，指的是将文本 A 编辑成文本 B 需要的最少变动次数（每次只能增加、删除或修改一个字）。

用途：可以用来计算字符串的相似度，文本相似度, 拼写纠错和抄袭侦测等等

优点：准确率很高，编辑距离算出来很小，文本相似度肯定很高。

缺点：召回率不高，由于编辑距离与文本的顺序有关。在文字相同，文字顺序变化很大的情况下，相似度会变得很低。比如“正大光明”和“光明正大”其实是一个意思。但编辑距离是4，完全不匹配

计算解析：

首先定义的单字符编辑操作有且仅有三种：

插入（Insertion）

删除（Deletion）

替换（Substitution）

image

我们可以给不同的操作赋予不同代价值，莱温斯坦（Levenshtein）定义该编辑距离最简单的方式是给每种操作赋予相同的代价值1。莱温斯坦另外一种定义只允许插入和删除操作，不允许替换操作。这样相当于替换用插入和删除两种操作实现，替换的代价值相当于变成2。

我们这里先用第一种定义将插入，删除，替换的三种操作代价都定为值1

假设我们把要比较相似度的两个字符串做成一个二维数组

假如两个字符串分别是String A="xyz"和String B="xymn"做成一个二维数组 i代表B的序号[行]，j代表A的序号[列]，i或者j等于0的时候代表大家都是空字符串, 我们用lev(i,j)来代表截止到指定坐标点，字符串要变成一样所需的编辑距离。因此，如下图，这里我们要求的值就是右下角(最终编辑距离)位置的值。

image

1.如果i=0或者j=0，lev(i,j)=j或者i，这里我们用0代表最前面的空串，这个位置的空串要编辑成一样则不需要操作，lev(i,j) = 0，也就是下面这个情况

image

2.继续用上面的公式（如果i=0或者j=0，lev(i,j)=j或者i），比如"0”编辑成”0x”只需要增加x一个操作。"0”编辑成”0xy”需要增加x和增加y一共两个操作。推导出如下图：

image

3.如果i&&j>=1 则lev(i,j)=min{lev(i-1,j)+1,lev(i,j-1)+1,lev(i-1,j-1)+h} 如果B[i]=A[j]相等，则h=0，否则h=1； min函数用来取三个编辑距离的最小值。我们先由此推导出i=1,j=1位置的值，lev(1,1) = min(lev(0,1)+1, lev(1,0)+1, lev(0,0)+h); 由于这个位置B[i]=A[j]相等, 所以h=0，那么lev(1,1) = min(2, 2, 0) = 0; 也就是”0x”编辑成”0x”的编辑距离为0。

image

4.依上公式继续推导

image

image

image

由此可以得出”xyz”和“xymn”的编辑距离为2，那么两个文本的相似度为（1 - （2/max(”xyz”字符串的长度，“xymn”字符串的长度)），（1 - (2/4)） = 0.50, 则相似度为50%.

Java版

public static float levenshtein(String msg, String msg2) {
        //计算两个字符串的长度。  
        int len1 = msg.length();
        int len2 = msg2.length();
        //建立文中说的数组，比字符长度大一个空间  
        int[][] dif = new int[len1 + 1][len2 + 1];
        //赋初值
        for (int a = 0; a <= len1; a++) {
            dif[a][0] = a;
        }
        for (int a = 0; a <= len2; a++) {
            dif[0][a] = a;
        }
        //计算两个字符是否一样，计算左上的值  
        int temp;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (msg.charAt(i - 1) == msg2.charAt(j - 1)) {
                    temp = 0;
                } else {
                    temp = 1;
                }
                //取三个值中最小的  
                dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1,
                        dif[i - 1][j] + 1);
            }
        }
        //取数组右下角的值，不同位置代表不同字符串的比较  
        //计算相似度  
        float similarity = 1 - (float) dif[len1][len2] / Math.max(len1, len2);
        return similarity * 100.0f;
}

 //得到最小值 
public static int min(int... is) {
        int min = Integer.MAX_VALUE;
        for (int i : is) {
            if (min > i) {
                min = i;
            }
        }
        return min;
}

php版

<?php
$str1 = "正大光明";
$str2 = "正光大";
echo sprintf("%.2f",(1.0 - (levenshtein($str1,$str2) / max(strlen($str1), strlen($str2)))) * 100.0);

是的，你没看错，php为了提高代码执行效率和你的编码效率把算法封装到C里面了。
┑(￣▽ ￣)┍