PHP 相似字串匹配：Levenshtein 距離演算法實戰應用

核心函數

function closest_word(string $input, array $words): string {
    $shortest = -1;
    $closest = '';
    
    foreach ($words as $word) {
        $lev = levenshtein($input, $word);
        
        if ($lev === 0) {
            return $word; // 完全匹配
        }
        
        if ($lev <= $shortest || $shortest < 0) {
            $closest = $word;
            $shortest = $lev;
        }
    }
    
    return $closest;
}

實戰範例：美國州名拼寫修正

$states = [
    'AL' => 'Alabama', 'AK' => 'Alaska', 'AZ' => 'Arizona',
    'CA' => 'California', 'NY' => 'New York', 'TX' => 'Texas',
    // ... 完整 50 州
];

$input = 'Wiscsin'; // 用戶輸入錯誤
$corrected = closest_word($input, array_values($states));
echo $corrected; // Wisconsin

Levenshtein 深度解析

演算法原理

計算將字串 A 轉換為字串 B 所需的最少單字元編輯操作次數（插入、刪除、替換）。動態規劃實現，時間複雜度 O(m×n)。

PHP 內建函數變體

// 基本用法
levenshtein($str1, $str2);

// 自定義成本 (插入、替換、刪除)
levenshtein($str1, $str2, $costIns, $costRep, $costDel);

// 限制最大距離 (超過回傳 -1，效能優化)
levenshtein($str1, $str2, 1, 1, 1, $maxDistance);

進階應用場景

1. 搜尋建議 / 自動完成

function searchSuggestions(string $query, array $dictionary, int $limit = 5): array {
    $results = [];
    foreach ($dictionary as $word) {
        $dist = levenshtein($query, $word, 1, 1, 1, 3); // 只找編輯距離 ≤ 3
        if ($dist !== -1) {
            $results[$word] = $dist;
        }
    }
    asort($results);
    return array_slice(array_keys($results), 0, $limit);
}

2. 關鍵字去重/合併

function mergeSimilarKeywords(array $keywords, int $threshold = 2): array {
    $merged = [];
    foreach ($keywords as $kw) {
        $found = false;
        foreach ($merged as $existing) {
            if (levenshtein($kw, $existing) <= $threshold) {
                $found = true; break;
            }
        }
        if (!$found) $merged[] = $kw;
    }
    return $merged;
}

3. 中文相似度 (需分詞)

Levenshtein 基於字元，中文需先分詞 (jieba-php) 再計算詞級距離，或使用專門的中文相似度庫。

效能優化策略

• 長度預過濾：abs(strlen($a) - strlen($b)) > $threshold 直接跳過
• BK-Tree 索引：大規模字典 (10萬+) 建立 BK-Tree，查詢 O(log n)
• Trie + Levenshtein 自動機：超大規模專業級方案
• 快取熱門查詢：Redis 快取近期查詢結果

替代演算法對比