萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 尋找相似度最高字串:Levenshtein 距離演算法實戰與優化

使用者輸入錯字、搜尋建議、指令自動修正、地址匹配等場景,都需要「找出最接近的字串」。PHP 內建 levenshtein() 計算編輯距離(插入/刪除/替換次數),是實作相似度搜尋的核心工具。本文從基本用法延伸至效能優化、多語言支援、替代演算法比較。

核心函式:levenshtein()

<?php
// 基本語法
$dist = levenshtein('kitten', 'sitting'); // 3 (k→s, e→i, +g)

// 自訂成本(插入、刪除、替換)
$dist = levenshtein('kitten', 'sitting', 1, 1, 2); // 替換成本 2

// 大小寫不敏感
$dist = levenshtein(strtolower($a), strtolower($b));
?>

完整函式:從陣列找出最相似字串

<?php
/**
 * 從候選陣列中找出與輸入字串相似度最高者
 *
 * @param string $input       使用者輸入
 * @param array  $candidates  候選字串陣列
 * @param int    $maxDist     最大允許距離(超過回傳 null)
 * @param bool   $caseInsensitive 不區分大小寫
 * @return string|null
 */
function findClosest(string $input, array $candidates, int $maxDist = -1, bool $caseInsensitive = true): ?string
{
    if ($caseInsensitive) {
        $input = mb_strtolower($input);
        $candidates = array_map('mb_strtolower', $candidates);
    }

    $closest = null;
    $shortest = $maxDist >= 0 ? $maxDist : PHP_INT_MAX;

    foreach ($candidates as $candidate) {
        // 快速捷徑:長度差超過目前最短距離,直接跳過
        $lenDiff = abs(mb_strlen($input) - mb_strlen($candidate));
        if ($lenDiff > $shortest) continue;

        $dist = levenshtein($input, $candidate);
        if ($dist < $shortest) {
            $shortest = $dist;
            $closest = $candidate;
            if ($shortest === 0) break; // 完全相符
        }
    }

    return $maxDist >= 0 && $shortest > $maxDist ? null : $closest;
}

// 使用範例:美國州名修正
$states = [
    'AL' => 'Alabama', 'AK' => 'Alaska', 'AZ' => 'Arizona', 'AR' => 'Arkansas',
    'CA' => 'California', 'CO' => 'Colorado', 'CT' => 'Connecticut', 'DE' => 'Delaware',
    '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), maxDist: 3);
echo "輸入:$input\n";
echo "建議:$match\n"; // Wisconsin
?>

效能優化策略

  1. 長度預檢:abs(strlen($a) - strlen($b)) > $bestDist 直接跳過(編輯距離下界)。
  2. 前綴過濾:先用 str_starts_with() 或前 2-3 字元分群,縮小候選池。
  3. 限制候選數:搭配資料庫 LIKE 'prefix%' 或全文搜尋先篩選前 50 筆。
  4. 快取距離:相同字串對重複計算可快取(static $cache)。
  5. C 擴展:levenshtein 為 C 實作,已極快;極大量級(百萬級)考慮 php-levenshtein 擴展或改用 similar_text()。

多語言與 Unicode 注意事項

  • levenshtein() **僅支援單位元組編碼**(ASCII/ISO-8859-1)。中文、日文、Emoji 會按位元組計算,結果不準。
  • 解決方案:
    • 改用 similar_text()(支援 UTF-8,但較慢,複雜度 O(N³))
    • 使用 intl 擴展的 Collator 或第三方庫(如 php-string-similarity、jaybizzle/crawler-detect 內建的 UTF-8 Levenshtein)
    • 將字串轉為音標/拼音/羅馬字後比較(如中文轉拼音)

替代演算法比較

演算法PHP 函式特點適用場景
Levenshteinlevenshtein()編輯距離、C 實作快、單位元組英文單詞、代碼、短代碼修正
Similar Textsimilar_text()相似度百分比、支援 UTF-8、慢短字串、多語言、需百分比
Jaro-Winkler無內建(需庫)前綴加權、適合人名/地址人名匹配、實體解析
N-gram / Cosine無內建向量空間、適合長文本文檔去重、抄襲偵測
Soundex/Metaphonesoundex()/metaphone()發音編碼、英文專用姓名搜尋、語音查詢

實戰:搜尋建議 API 端點

<?php
// API: /api/suggest?q=Wiscsin&limit=5
$q = $_GET['q'] ?? '';
$limit = min((int)($_GET['limit'] ?? 5), 20);

if (mb_strlen($q) < 2) {
    jsonResponse(['suggestions' => []]);
}

// 1. 先從 DB 取前綴匹配(利用索引)
$stmt = $pdo->prepare("SELECT name FROM cities WHERE name LIKE ? LIMIT 100");
$stmt->execute([$q . '%']);
$candidates = $stmt->fetchAll(PDO::FETCH_COLUMN);

// 2. 不夠則補全文搜尋或所有城市
if (count($candidates) < 20) {
    $stmt = $pdo->query("SELECT name FROM cities LIMIT 500");
    $candidates = array_merge($candidates, $stmt->fetchAll(PDO::FETCH_COLUMN));
    $candidates = array_unique($candidates);
}

// 3. Levenshtein 排序取前 N
$scored = [];
foreach ($candidates as $city) {
    $dist = levenshtein(strtolower($q), strtolower($city));
    $scored[] = ['name' => $city, 'distance' => $dist];
}
usort($scored, fn($a, $b) => $a['distance'] <=> $b['distance']);
$result = array_slice($scored, 0, $limit);

jsonResponse(['suggestions' => $result]);

function jsonResponse(array $data, int $code = 200): never
{
    http_response_code($code);
    header('Content-Type: application/json; charset=utf-8');
    echo json_encode($data, JSON_UNESCAPED_UNICODE | JSON_UNESCAPED_SLASHES);
    exit;
}
?>

善用 levenshtein() 配合資料庫前置過濾,能以極低成本打造智慧型搜尋建議、錯字修正、指令自動完成等優質使用者體驗。

copyright © 萬盛學電腦網 all rights reserved