前言

在之前的工作中曾经使用过 similar_text() 函数比对字符串相似度，一直想了解其内部实现，故今天来填坑。

代码实现

下列代码便是截取自 php 源码中有关 similar_text() 函数的部分，不难看出，整个函数的逻辑就是通过暴力法取出两个对比字符串的最长公共子集，然后按照最长公共子集为界，再将前后两部分按照同样的方式继续递归，直到递归完成。

// {php_src_path}/ext/standard/string.c
// line 3305 - line 3382

/* {{{ php_similar_str */
static void php_similar_str(const char *txt1, size_t len1, const char *txt2, size_t len2, size_t *pos1, size_t *pos2, size_t *max, size_t *count)
{
    const char *p, *q;
    const char *end1 = (char *) txt1 + len1; // 模式串 1 最后一个字符
    const char *end2 = (char *) txt2 + len2; // 模式串 2 最后一个字符
    size_t l;

    *max = 0;
    *count = 0;
    // 暴力法获取最长重复子串，时间复杂度 O(n^3)
    // 以第一个字符串为基准开始遍历
    for (p = (char *) txt1; p < end1; p++) {
        // 同时遍历第二个字符串
        for (q = (char *) txt2; q < end2; q++) {
            // 重复循环至第一个模式串 1 和模式串 2 不同的字符或直到任一字符串结束
            for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);
            // 找到最大的重复长度
            if (l > *max) {
                // 记录循环结束后遍历到的首个不重复时的长度
                *max = l;
                // 记录循环次数
                *count += 1;
                // 记录最长重复子串模式串 1 的起始位置
                *pos1 = p - txt1;
                // 记录最长重复子串模式串 2 的起始位置
                *pos2 = q - txt2;
            }
        }
    }
}
/* }}} */

/* {{{ php_similar_char */
static size_t php_similar_char(const char *txt1, size_t len1, const char *txt2, size_t len2)
{
    size_t sum;
    size_t pos1 = 0, pos2 = 0, max, count;
    // 找出两个字符串相同部分最长的一段
    php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max, &count);
    // 赋值 sum, 同时检查若 max 为 0 直接跳出，证明没有任何重复子串
    if ((sum = max)) {
        // 对返回最长相同子串起始位置前段递归，相同段长度累加
        if (pos1 && pos2 && count > 1) {
            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_FUNCTION(similar_text)
{
    zend_string *t1, *t2; // 声明用于接收 zend 参数的变量
    zval *percent = NULL;
    int ac = ZEND_NUM_ARGS();
    size_t sim;

    // php 函数参数解析方法
    // ZEND_PARSE_PARAMETERS_START(至少传入的参数数量, 最多传入的参数数量)
    ZEND_PARSE_PARAMETERS_START(2, 3) 
        Z_PARAM_STR(t1)  // 读取字符串参数 1
        Z_PARAM_STR(t2)  // 读取字符串参数 2
        Z_PARAM_OPTIONAL // 标识可选参数开始
        Z_PARAM_ZVAL(percent) // 从外部传入用于接收相似度百分比的变量
    ZEND_PARSE_PARAMETERS_END(); // php 函数参数解析结束方法

    if (ZSTR_LEN(t1) + ZSTR_LEN(t2) == 0) { // 两个字符串都为空的情况
        if (ac > 2) {
            ZEND_TRY_ASSIGN_REF_DOUBLE(percent, 0); // 返回相似度百分比 0
        }

        RETURN_LONG(0);
    }

    sim = php_similar_char(ZSTR_VAL(t1), ZSTR_LEN(t1), ZSTR_VAL(t2), ZSTR_LEN(t2)); // 计算相同的字符个数

    if (ac > 2) {
        ZEND_TRY_ASSIGN_REF_DOUBLE(percent, sim * 200.0 / (ZSTR_LEN(t1) + ZSTR_LEN(t2))); // 计算相似度百分比，由于最终计算百分比会两串长度相加，故算出的重复字符长度也需要 x2 计算
    }

    RETURN_LONG(sim); // 返回相同字符长度
}
/* }}} */

简单举例

假设字符串 x: abcabcabc, 字符串 y: aacabcabb, 就有如下匹配过程：

layer 1 - 1
matches: cabcab
sum = 6

layer 2 - 1
matches: a
sum = 7

layer 3 - 1
matches:
sum = 7

layer 3 - 2
matches:
sum = 7

layer 2 - 2
matches:
sum = 7

layer 1 - 2
matches:
sum = 7

最后根据算法，可以计算出最终的百分比为 7*2/(9+9) ≈77.78%。

<?php
$percent = 0.00;
$max = similar_text("abcabcabc", "aacabcaba", $percent);
echo "max:" . $max . "\n";
echo "percent: " . round($percent, 2) ."%";

// output
// max: 7
// percent: 77.78%

小结

总的来说，similar_text() 的内部实现比较简单粗暴，时间复杂度高达 O(n^3)，因此，如无必要，减少该函数的使用，尤其是比较长字符串的情况下。