关于PHP的相似度计算函数：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[i][j]表示把x的前i个字符变成y的前j个字符所需的最少操作次数，则状态转移方程为：
代码如下:
当x[i]==y[j]时：a[i][j]  = min(a[i-1][j-1], a[i-1][j]+1, a[i][j-1]+1);
当x[i]!=y[j]时：a[i][j] =  min(a[i-1][j-1], a[i-1][j], a[i][j-1])+1;