PHP 找出最相似字串：levenshtein() 演算法實戰與應用場景

使用者輸入常有拼字錯誤（如 "Wiscsin" vs "Wisconsin"）。PHP 內建 levenshtein() 函數計算兩字串的「編輯距離」（插入、刪除、替換所需最少步數），距離越小代表越相似。本文示範如何封裝函數、優化效能、並擴展應用於自動修正、搜尋建議、資料清洗等場景。

核心函數封裝

<?php
/**
 * 從候選陣列中找出與輸入字串最相似的一項
 * @param string $input 輸入字串（可能含錯誤）
 * @param array  $candidates 候選字串陣列
 * @param int    $maxDistance 最大允許距離，超過回傳 null（預設無限制）
 * @return string|null 最相似字串，或 null
 */
function findClosest(string $input, array $candidates, int $maxDistance = PHP_INT_MAX): ?string
{
    $shortest = -1;
    $closest = null;

    foreach ($candidates as $candidate) {
        // levenshtein 大小寫敏感，統一轉小寫比較
        $dist = levenshtein(strtolower($input), strtolower($candidate));

        if ($dist === 0) {
            return $candidate; // 完全相符，直接返回
        }

        if ($dist <= $maxDistance && ($shortest === -1 || $dist < $shortest)) {
            $shortest = $dist;
            $closest = $candidate;
        }
    }

    return $closest;
}
?>

實戰範例：美國州名自動修正

<?php
$states = [
    'AL' => 'Alabama', 'AK' => 'Alaska', 'AZ' => 'Arizona', 'AR' => 'Arkansas',
    'CA' => 'California', 'CO' => 'Colorado', 'CT' => 'Connecticut', 'DE' => 'Delaware',
    'DC' => 'District Of Columbia', 'FL' => 'Florida', 'GA' => 'Georgia', 'HI' => 'Hawaii',
    'ID' => 'Idaho', 'IL' => 'Illinois', 'IN' => 'Indiana', 'IA' => 'Iowa',
    'KS' => 'Kansas', 'KY' => 'Kentucky', 'LA' => 'Louisiana', 'ME' => 'Maine',
    'MD' => 'Maryland', 'MA' => 'Massachusetts', 'MI' => 'Michigan', 'MN' => 'Minnesota',
    'MS' => 'Mississippi', 'MO' => 'Missouri', 'MT' => 'Montana', 'NE' => 'Nebraska',
    'NV' => 'Nevada', 'NH' => 'New Hampshire', 'NJ' => 'New Jersey', 'NM' => 'New Mexico',
    'NY' => 'New York', 'NC' => 'North Carolina', 'ND' => 'North Dakota', 'OH' => 'Ohio',
    'OK' => 'Oklahoma', 'OR' => 'Oregon', 'PA' => 'Pennsylvania', 'RI' => 'Rhode Island',
    'SC' => 'South Carolina', 'SD' => 'South Dakota', 'TN' => 'Tennessee', 'TX' => 'Texas',
    'UT' => 'Utah', 'VT' => 'Vermont', 'VA' => 'Virginia', 'WA' => 'Washington',
    'WV' => 'West Virginia', 'WI' => 'Wisconsin', 'WY' => 'Wyoming',
];

$input = 'Wiscsin'; // 使用者輸入錯誤
$match = findClosest($input, array_values($states), 3); // 允許距離 3 以內

if ($match) {
    echo "您是指：$match ?"; // 輸出：您是指：Wisconsin ?
} else {
    echo "找不到相似項目";
}
?>

進階：加權成本與多語言支援

levenshtein() 允許自訂「插入、刪除、替換」三種操作的成本：

<?php
// 範例：替換成本較低（視為拼音錯誤機率高），插入/刪除成本較高
$dist = levenshtein($input, $candidate, 1, 2, 1); // insert=1, replace=2, delete=1

// 多位元組字串（中文、日文）注意：
// levenshtein() 僅支援單位元組編碼。
// 中文相似度建議使用類似 soundex、metaphone 或專門套件（如 php-levenshtein 支援 UTF-8 的分支）。
?>

效能優化策略

1. 預先過濾：先用 strlen() 長度差異過濾，差距超過閾值直接跳過。
2. 建立索引：大量候選詞（如字典）建議建立 BK-Tree 或 Trie 結構，查詢複雜度從 O(N) 降為 O(log N)。
3. 快取結果：相同輸入常重複出現，用 Redis/APCu 快取結果。
4. 平行處理：候選集極大時，可用 pcntl_fork 或外部服務（Elasticsearch fuzzy query）分流。

應用場景擴展

替代方案：similar_text()

<?php
similar_text($input, $candidate, $percent);
// $percent 為相似百分比（0-100），而非編輯距離
// 適合需要「相似度百分比」呈現的 UI
?>

善用 levenshtein()，能大幅提升使用者體驗，減少「查無資料」的挫折感，是打造智慧型介面的關鍵工具之一。