PHP similar_text() 函數原理深度解析：最長公共子串遞歸算法

PHP 內置 similar_text() 可計算兩字符串相似度百分比，常用於模糊搜索、驗證碼識別特徵匹配等場景。本文基於 PHP 5.4.6 源碼（ext/standard/string.c），深度解析其核心算法——最長公共子串遞歸分治。

函數行為速覽

similar_text('aaaa', 'aaaa', $p);   // $p = 100
similar_text('aaaa', 'aaaabbbb', $p); // $p ≈ 66.67
similar_text('abcdef', 'aabcdefg', $p); // $p ≈ 85.71

核心算法三步走

1. 尋找最長公共子串：在兩字符串中找出連續相同字符最長的一段，記錄長度 max 及在兩串中的起始位置 pos1、pos2。
2. 遞歸處理剩餘部分：以最長公共子串為分界，分別遞歸處理「左側剩餘部分」和「右側剩餘部分」，累加各段最長公共子串長度。
3. 計算相似度百分比：similarity = (總公共長度 * 2) / (字符串1長度 + 字符串2長度) * 100%。

源碼關鍵邏輯（註釋版）

// 步驟1：查找最長公共子串（雙重循環暴力匹配，O(n³)）
static void php_similar_str(const char *txt1, int len1, const char *txt2, int len2,
                            int *pos1, int *pos2, int *max) {
    *max = 0;
    for (char *p = (char*)txt1; p < txt1 + len1; p++) {
        for (char *q = (char*)txt2; q < txt2 + len2; q++) {
            int l = 0;
            while (p+l < txt1+len1 && q+l < txt2+len2 && p[l] == q[l]) l++;
            if (l > *max) { *max = l; *pos1 = p - txt1; *pos2 = q - txt2; }
        }
    }
}

// 步驟2：遞歸累加公共長度
static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2) {
    int pos1, pos2, max;
    php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max);
    if (max == 0) return 0; // 無公共部分
    
    int sum = max;
    // 遞歸左側
    if (pos1 > 0 && pos2 > 0) 
        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;
}

// 步驟3：PHP 函數入口
PHP_FUNCTION(similar_text) {
    // ... 參數解析 ...
    int sim = php_similar_char(t1, t1_len, t2, t2_len);
    if (ac > 2) 
        Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len); // 百分比公式
    RETURN_LONG(sim);
}

複雜度與性能對比

結論：similar_text() 因三層循環 + 遞歸，性能隨長度惡化劇烈（>100 字符明顯卡頓）。長文本相似度請優先用 levenshtein() 或引入 text_similarity 擴展（基於 Simhash/MinHash）。

實用封裝建議

function similarityPercent(string $a, string $b): float {
    if (max(strlen($a), strlen($b)) > 200) {
        // 長文本降級用 levenshtein 轉換近似百分比
        $dist = levenshtein($a, $b);
        return (1 - $dist / max(strlen($a), strlen($b))) * 100;
    }
    similar_text($a, $b, $p);
    return $p;
}