PHP similar_text 函數源碼深度解析：核心算法與遞歸實現

PHP 相似度計算核心：similar_text 函數 C 源碼詳細解讀

similar_text() 是 PHP 內置的字符串相似度計算函數，返回兩字符串匹配字符數，可選計算百分比。本文深入分析其 C 源碼實現，揭示底層算法邏輯。

核心算法：最長公共子串 + 分治遞歸

函數採用「尋找最長公共子串 → 分治遞歸處理左右剩餘部分」的策略，屬於動態規劃思想的簡化實現。

關鍵函數解析

1. 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;
            }
        }
    }
}

時間複雜度：O(n×m×min(n,m))，對長字符串性能較差。
輸出：max 最長公共子串長度，pos1/pos2 其在兩字符串中的起始位置。

2. php_similar_char：遞歸分治累加匹配長度

static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2) {
    int sum, 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;
}

關鍵點：if ((sum = max)) 是賦值表達式，先將 max 賦給 sum，再判斷 sum 是否非零。若無公共子串（max=0），直接返回 0，遞歸終止。

3. PHP_FUNCTION(similar_text)：對外接口封裝

PHP_FUNCTION(similar_text) {
    zval **t1, **t2, **percent;
    int ac = ZEND_NUM_ARGS();
    int sim;

    // 參數檢查：2-3 個參數
    if (ac < 2 || ac > 3 || zend_get_parameters_ex(ac, &t1, &t2, &percent) == FAILURE) {
        WRONG_PARAM_COUNT;
    }
    convert_to_string_ex(t1);
    convert_to_string_ex(t2);
    if (ac > 2) convert_to_double_ex(percent);

    // 空字符串特殊處理
    if (Z_STRLEN_PP(t1) + Z_STRLEN_PP(t2) == 0) {
        if (ac > 2) Z_DVAL_PP(percent) = 0;
        RETURN_LONG(0);
    }

    // 核心計算
    sim = php_similar_char(Z_STRVAL_PP(t1), Z_STRLEN_PP(t1),
                          Z_STRVAL_PP(t2), Z_STRLEN_PP(t2));

    // 計算百分比：匹配字符數 × 2 / (長度1 + 長度2) × 100
    if (ac > 2) {
        Z_DVAL_PP(percent) = sim * 200.0 / (Z_STRLEN_PP(t1) + Z_STRLEN_PP(t2));
    }
    RETURN_LONG(sim);
}

算法特點與局限

使用建議

• 短文本（< 100 字符）：可直接使用
• 長文本/高性能場景：考慮 levenshtein() 或引入專用庫（如 text_similarity 擴展）
• 中文處理：按字節比較，多字節字符可能產生誤判，建議預處理轉換

理解底層實現有助於正確評估適用場景，避免在大數據量下誤用導致性能問題。