胖胖 PHP 2012/02/21 给我留言 500 views

上次reeze提到similar_text函数，这个真心没用过。
在手册上查找其说明如下：
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 / 两个字符串的长度。

关于那本书：

名称 Programming classics: implementing the world’s best algorithms
作者 Ian Oliver
出版商 Prentice Hall, 1993
出处： 密歇根大学
数字化处理时间 2007年11月15日
ISBN 0131004131, 9780131004139
页数 386 页
这里也许可以下载到
http://filecom.net/8EMrrcoyc8/
http://ebooks-files.org/download/programming-classics-implementing-the-worlds-best-algorithms.html

标签：PHP源码, PHP源码阅读笔记