字符串函数 - 关于php的levenshtein函数能否给个通俗易懂的解释，手册看不懂！

Question

如题，越详细越好。谢谢了！ {代码...} 它只要在第二个参数添加个'H'，只作了1个步骤！也当然返回'1'啦！ 这个函数还是蛮简单的，可是： {代码...} 第3个参数：插入一个字符的代价。默认是 1。 第4个参数：替换一...

PHP中文网 · Answer

@怡红公子已经回答的很好了，我想从底层实现上补充一下题主说的levenshtein('aaa','aab',0,1,0);这个例子，为什么会返回0?

PHP底层使用的算法是经典的矩阵方式(稍有改动)，即分别将s1和s2的每个字符作为矩阵的行(i[0,m])和列(j[0,n])，每个位置按顺序进行两两比较，如果相等则cost=0（因为不需要任何操作），否则cost=1（这个cost=1就是我们不传递后面3个参数时默认操作的cost了）；但是，这里矩阵该项M[i,j]的值还不能直接就等于cost，因为要保证前面操作的传递性（比如你在前面插入了1个字符，后面的字符就要跟着往后挪一位；你在前面插删除了2个字符，后面就要跟着往前挪一位），M[i,j]的值等于M[i-1, j]+1, M[i, j-1]+1, M[i-1, j-1]+cost三个值中最小的（3个值分别表示插入、替换、删除的代价，取最小值表示采用操作代价最小的方式）。这样直到计算到项M[m, n]的值，就是我们需要求的“编辑距离”了。（最后我贴出了php底层c代码对应的php实现）

levenshtein('aaa','aab',1,1,1);的计算演示,单元格[3,3]为最终结果:

		a	a	a
	0	1	2	3
a	1	0	1	2
a	2	1	0	1
b	3	2	1	1

levenshtein('aaa','aab',0,1,0);的计算演示,单元格[3,3]为最终结果（因为[1,1]=0, 而且插入的cost设置成了0，导致后面M[i, j-1]的结果都是0，而0是最小值，导致最终返回0）:

		a	a	a
	0	1	2	3
a	1	0	0	0
a	2	0	0	0
b	3	0	0	0

这里可以看出，levenshtein后面传递的3个参数，是对应的插入、替换、删除三种操作的当前代价（即替换上面求项M[i,j]值的时候后面+的1），而从算法角度来说，任何操作的最小代价单位是1，那么如果我们要得到一个“合理”的返回值，就不能传递0值。传递0就可能导致返回一个不合理，或者说没有实际参考价值的结果。当然，这是跟实际采用的算法密切相关的，就本例来说，最佳操作应该是替换（将aab中的b替换为a），但是PHP采用的算法来看，取的是3种操作方式中最小的值，而且要带入传递性，导致最终结果为0。

#php底层c代码对应的php实现
function levenshtein_php($s1, $s2, $cost_ins=1, $cost_rep=1, $cost_del=1){
    $l1 = strlen($s1);
    $l2 = strlen($s2);

    if ($l1 == 0) {
        return $l2 * $cost_ins;
    }
    if ($l2 == 0) {
        return $l1 * $cost_del;
    }

    $p1 = array();
    $p2 = array();

    for ($i2 = 0; $i2 <= $l2; $i2++) {
        $p1[$i2] = $i2 * $cost_ins;
    }
    for ($i1 = 0; $i1 < $l1 ; $i1++) {
        $p2[0] = $p1[0] + $cost_del;

        for ($i2 = 0; $i2 < $l2; $i2++) {
            $c0 = $p1[$i2] + (($s1[$i1] == $s2[$i2]) ? 0 : $cost_rep);
            $c1 = $p1[$i2 + 1] + $cost_del;
            if ($c1 < $c0) {
                $c0 = $c1;
            }
            $c2 = $p2[$i2] + $cost_ins;
            if ($c2 < $c0) {
                $c0 = $c2;
            }
            $p2[$i2 + 1] = $c0;
        }

        $tmp = $p1;
        $p1 = $p2;
        $p2 = $tmp;
    }
    $c0 = $p1[$l2];

    return $c0;
}

echo levenshtein_php('aaa', 'aab', 1, 10, 1));

PS: 实际上有比利用矩阵结构更优的算法，就不在本题展开了。我没太多算法基础，尝试分析，欢迎批评指正！

PHPz · Answer

通俗的来说就是检测两个字符串的相似程度的，一个字符串变成另外一个字符串的步骤越少的话就是越相似。

$a = "levenshtein";
$b = "levenjdslkfjslkdjfklsjdfljsdlfjsldfjlsdjflsdjltein";
$c = "leveshetin";

$r = levenshtein($a, $b); //int(40)
$s = levenshtein($a, $c); //int(3)

从$a变成$b需要在中间增加40个字符，从$a变成$c需要增加2个字符，删除1个字符，所以是3。

所谓的代价就是一次特定操作所占有的权重/比重，比如你设置了删除字符的代价是30，做1次删除最后返回给你的就是1*30了。通过设置这个参数有助于尽量多做某个操作避免某个操作。至于后面那个，我个人是这样理解的，所谓的替换其实是经过了“删除”和“增加”两个步骤的合体，如果你把增加和删除设置成0的话就相当于禁止做这两个操作了，替换也就无法操作了。如果你随便给增加和删除来个非0值，则总会返回1。当然这都是我的个人想法，如果有不对的话可以提出来指正。