PHP中计算字符串相似度的函数

lilingjie2015

　　similar_text — 计算两个字符串的相似度
int similar_text ( string $first , string $second [, float &$percent ] )
$first 必需。规定要比较的第一个字符串。
$second 必需。规定要比较的第二个字符串。
$percent 可选。规定供存储百分比相似度的变量名。
　　两个字符串的相似程度计算依据 Oliver [1993] 的描述进行。注意该实现没有使用 Oliver 虚拟码中的堆栈，但是却进行了递归调用，这个做法可能会导致整个过程变慢或变快。也请注意，该算法的复杂度是 O(N**3)，N 是最长字符串的长度。
　　比如我们想找字符串abcdefg和字符串aeg的相似度：

$first = "abcdefg";
$second = "aeg";
echo similar_text($first, $second);
　　结果输出3.如果想以百分比显示，则可使用它的第三个参数,如下：

$first = "abcdefg";
$second = "aeg";
similar_text($first, $second, $percent);
echo $percent;
　　这里的相似度的算法是什么呢？本来是想看看Oliver[1993]对于这个算法的具体描述，各种google后，只找到这是从Ian Oliver1993年出版的书《Programming classics: implementing the world’s best algorithms》中记载，没有找到这本书的电子版。
　　直接代码，在string.c文件中我们找到了similar_text的实现PHP_FUNCTION(similar_text)，其最终调用php_similar_cha获取两个字符串的相似度，如下代码：

static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2)
{
int sum;
int pos1, pos2, max;
php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max);
if ((sum = max)) {
if (pos1 && pos2) {
sum += php_similar_char(txt1, pos1, txt2, pos2);
}
if ((pos1 + max < len1) && (pos2 + max < len2)) {
sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max,txt2 + pos2 + max, len2 - pos2 - max);                                               
}
}
return sum;
}
　　首先我们看php_similar_str函数的作用，从函数名和参数名我们可以大致猜测它的作用是求两个字符串的相似子串，具体代码如下：

static void php_similar_str(const char *txt1, int len1, const char *txt2, int len2, int *pos1, int *pos2, int *max)
{
char *p, *q;
char *end1 = (char *) txt1 + len1;
char *end2 = (char *) txt2 + len2;
int l;
*max = 0;
for (p = (char *) txt1; p < end1; p++) {
for (q = (char *) txt2; q < end2; q++) {
for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);
if (l > *max) {
*max = l;
*pos1 = p - txt1;
*pos2 = q - txt2;
}
}
}
}
　　很直白的三重循环，求两个字符串的最大相似子串的长度，以及这两个子串相等的开始位置。
　　在了解了php_similar_str的作用后，回到php_similar_char函数。这是一个很直白的二分算法。以当前两个字符串的最大 相似子串的位置为分隔，向两边二分查找相似子串，最终得到所有的相似子串长度的总和，这也就是我们这个函数的相似度算法：从最长子串开始，依次统计所有的 子串长度。
　　那么这里的百分比是如何计算的呢？
　　在PHP_FUNCTION(similar_text)的函数体中，如下代码：

sim = php_similar_char(t1, t1_len, t2, t2_len);
if (ac > 2) {
Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len);
}
　　sim是相似度的值，百分比是直接 sim * 200 / 两个字符串的长度。
　　原文参考：http://www.phppan.com/2012/02/php-similar-text/