在之前的文章 << PHP中计算字符串相似度的函数 >>中我们介绍了similar_text函数的使用及实现过程。similar_text() 函数主要是用来计算两个字符串的匹配字符的数目，也可以计算两个字符串的相似度（以百分比计）。与 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[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;

在用状态转移方程前，我们需要初始化(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的矩阵存储距离值。

PHP向它运行的任何脚本提供了大量的预定义常量。
不过很多常量都是由不同的扩展库定义的，只有在加载了这些扩展库时才会出现，或者动态加载后，或者在编译时已经包括进去了。

有七个魔术常量它们的值随着它们在代码中的位置改变而改变。例如 __LINE__ 的值就依赖于它在脚本中所处的行来决定。这些特殊的常量不区分大小写。在手册中这几个变量的简单说明如下：
几个 PHP 的“魔术常量”

在写这篇文章时，由于把思维局限在语法解析和运行时赋值，导致寻找了好久都没有发现实现原因。还是网上的一篇文章将我们的思维找回到词法分析。PHP内核会在词法解析时将这些相对静态的内容赋值给这些变量，而不是在运行时执行的分析。如下PHP代码：

<?PHP
echo __LINE__;
function demo() {
	echo __FUNCTION__;
}
demo();

其实PHP已经在词法解析时将这些常量换成了对应的值，以上的代码可以看成如下的PHP代码：

<?PHP
echo 2;
function demo() {
	echo "demo";
}
demo();

如果我们使用VLD扩展查看以上的两段代码生成的中间代码，你会发现其结果是一样的。

前面我们有说PHP是在词法分析时做的赋值替换操作，以__FUNCTION__为例，在Zend/zend_language_scanner.l文件中，__FUNCTION__是一个需要分析的元标记（token）：

<ST_IN_SCRIPTING>"__FUNCTION__" {
	char *func_name = NULL;
 
	if (CG(active_op_array)) {
		func_name = CG(active_op_array)->function_name;
	}
 
	if (!func_name) {
		func_name = "";
	}
	zendlval->value.str.len = strlen(func_name);
	zendlval->value.str.val = estrndup(func_name, zendlval->value.str.len);
	zendlval->type = IS_STRING;
	return T_FUNC_C;
}

就是这里，当当前中间代码处于一个函数中时，则将当前函数名赋值给zendlval，如果没有，则将空字符串赋值给zendlval(因此在顶级作用域名中直接打印__FUNCTION__会输出空格)。这个值在语法解析时会直接赋值给返回值。这样我们就在生成的中间代码中看到了这些常量的位置都已经赋值好了。

和__FUNCTION__类似，在其附近的位置，上面表格中的其它常量也进行了类似的操作。在PHP5.4中增加了对于trait类的常量定义：__TRAIT__。

这些常量其实相当于一个常量模板，或者说是一个占位符，在词法解析时这些模板或占位符就被替换成实际的值