PHP相似度计算函数：levenshtein

玩龙天子

　　与 similar_text() 函数相比，我们今天要介绍的 levenshtein() 函数更快。不过，similar_text() 函数能通过更少的必需修改次数提供更精确的结果。在追求速度而少精确度，并且字符串长度有限时可以考虑使用 levenshtein() 函数。

使用说明
　　先看手册上 levenshtein() 函数的说明：
　　levenshtein() 函数返回两个字符串之间的 Levenshtein 距离。
　　Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
　　例如把 kitten 转换为 sitting：

sitten （k→s）
sittin （e→i）
sitting （→g）
　　levenshtein() 函数给每个操作（替换、插入和删除）相同的权重。不过，您可以通过设置可选的 insert、replace、delete 参数，来定义每个操作的代价。
　　语法：
　　levenshtein(string1,string2,insert,replace,delete)
　　参数 描述

• string1 必需。要对比的第一个字符串。
  
• string2 必需。要对比的第二个字符串。
  
• insert 可选。插入一个字符的代价。默认是 1。
  
• replace 可选。替换一个字符的代价。默认是 1。
  
• delete 可选。删除一个字符的代价。默认是 1。
  

　　提示和注释

• 如果其中一个字符串超过 255 个字符，levenshtein() 函数返回 -1。
  
• levenshtein() 函数对大小写不敏感。
  
• levenshtein() 函数比 similar_text() 函数更快。不过，similar_text() 函数提供需要更少修改的更精确的结果。
  

　　例子

<?php
echo levenshtein("Hello World","ello World");
echo "<br />";
echo levenshtein("Hello World","ello World",10,20,30);
?>



　　输出： 1 30

源码分析
　　levenshtein() 属于标准函数，在/ext/standard/目录下有专门针对此函数实现的文件：levenshtein.c。
　　levenshtein()会根据参数个数选择实现方式，针对参数为2和参数为5的情况，都会调用 reference_levdist() 函数计算距离。其不同在于对后三个参数，参数为2时，使用默认值1。
　　并且在实现源码中我们发现了一个在文档中没有说明的情况： levenshtein() 函数还可以传递三个参数，其最终会调用 custom_levdist() 函数。它将第三个参数作为自定义函数的实现，其调用示例如下：

echo levenshtein("Hello World","ello World", 'strsub');



　　执行会报Warning： The general Levenshtein support is not there yet。这是因为现在这个方法还没有实现，仅仅是放了一个坑在那。
　　reference_levdist() 函数的实现算法是一个经典的DP问题。
　　给定两个字符串x和y，求最少的修改次数将x变成y。修改的规则只能是如下三种之一：删除、插入、改变。
用a[j]表示把x的前i个字符变成y的前j个字符所需的最少操作次数，则状态转移方程为：

当x==y[j]时：a[j]  = min(a[i-1][j-1], a[i-1][j]+1, a[j-1]+1);
当x!=y[j]时：a[j] =  min(a[i-1][j-1], a[i-1][j], a[j-1])+1;



　　在用状态转移方程前，我们需要初始化(n+1)(m+1)的矩阵d，并让第一行和列的值从0开始增长。 扫描两字符串（nm级的），对比字符，使用状态转移方程，最终$a[$l1][$l2]为其结果。
　　简单实现过程如下：

<?PHP
$s1 = "abcdd";
$l1 = strlen($s1);
$s2 = "aabbd";
$l2 = strlen($s2);
 
 
for ($i = 0; $i < $l1; $i++) {
$a[0][$i + 1] = $i + 1;
}
for ($i = 0; $i < $l2; $i++) {
$a[$i + 1][0] = $i + 1;
}
 
for ($i = 0; $i < $l2; $i++) {
for ($j = 0; $j < $l1; $j++) {
if ($s2[$i] == $s1[$j]) {
$a[$i + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1] + 1, $a[$i + 1][$j] + 1);
}else{
$a[$i + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1], $a[$i + 1][$j]) + 1;
}
}
}
 
echo $a[$l1][$l2];
echo "\n";
echo levenshtein($s1, $s2);



　　在PHP的实现中，实现者在注释中很清楚的标明：此函数仅优化了内存使用，而没有考虑速度，从其实现算法看，时间复杂度为O(m×n)。其优化点在于将上面的状态转移方程中的二维数组变成了两个一组数组。简单实现如下：

<?PHP
$s1 = "abcjfdkslfdd";
$l1 = strlen($s1);
$s2 = "aab84093840932bd";
$l2 = strlen($s2);
 
$dis = 0;
for ($i = 0; $i <= $l2; $i++){
$p1[$i] = $i;
}
 
for ($i = 0; $i < $l1; $i++){
$p2[0] = $p1[0] + 1;
 
for ($j = 0; $j < $l2; $j++){
if ($s1[$i] == $s2[$j]){
$dis = min($p1[$j], $p1[$j + 1] + 1, $p2[$j] + 1);
}else{
$dis = min($p1[$j] + 1, $p1[$j + 1] + 1, $p2[$j] + 1);  // 注意这里最后一个参数为$p2  
}
$p2[$j + 1] = $dis;
}
$tmp = $p1;
$p1 = $p2;
$p2 = $tmp;  
}
 
echo "\n";
echo $p1[$l2];
echo "\n";
echo levenshtein($s1, $s2);



　　如上为PHP内核开发者对前面经典DP的优化，其优化点在于不停的复用两个一维数组，一个记录上次的结果，一个记录这一次的结果。如果按照PHP的 参数，分别给三个操作赋值不同的值，在上面的算法中将对应的1变成操作对应的值就可以了。 min函数的第一个参数对应的是修改，第二个参数对应的是删除，第三个参数对应的是添加。

Levenshtein distance说明
　　Levenshtein distance最先是由俄国科学家Vladimir Levenshtein在1965年发明，用他的名字命名。不会拼读，可以叫它edit distance（编辑距离）。Levenshtein distance可以用来：

• Spell checking(拼写检查)
  
• Speech recognition(语句识别)
  
• DNA analysis(DNA分析)
  
• Plagiarism detection(抄袭检测) LD用mn的矩阵存储距离值。
  

　　原文：http://www.phppan.com/2012/12/php-levenshtein-function/