使用者輸入錯字、搜尋建議、指令自動修正、地址匹配等場景,都需要「找出最接近的字串」。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
?>
abs(strlen($a) - strlen($b)) > $bestDist 直接跳過(編輯距離下界)。str_starts_with() 或前 2-3 字元分群,縮小候選池。LIKE 'prefix%' 或全文搜尋先篩選前 50 筆。static $cache)。levenshtein 為 C 實作,已極快;極大量級(百萬級)考慮 php-levenshtein 擴展或改用 similar_text()。levenshtein() **僅支援單位元組編碼**(ASCII/ISO-8859-1)。中文、日文、Emoji 會按位元組計算,結果不準。similar_text()(支援 UTF-8,但較慢,複雜度 O(N³))intl 擴展的 Collator 或第三方庫(如 php-string-similarity、jaybizzle/crawler-detect 內建的 UTF-8 Levenshtein)| 演算法 | PHP 函式 | 特點 | 適用場景 |
|---|---|---|---|
| Levenshtein | levenshtein() | 編輯距離、C 實作快、單位元組 | 英文單詞、代碼、短代碼修正 |
| Similar Text | similar_text() | 相似度百分比、支援 UTF-8、慢 | 短字串、多語言、需百分比 |
| Jaro-Winkler | 無內建(需庫) | 前綴加權、適合人名/地址 | 人名匹配、實體解析 |
| N-gram / Cosine | 無內建 | 向量空間、適合長文本 | 文檔去重、抄襲偵測 |
| Soundex/Metaphone | soundex()/metaphone() | 發音編碼、英文專用 | 姓名搜尋、語音查詢 |
<?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() 配合資料庫前置過濾,能以極低成本打造智慧型搜尋建議、錯字修正、指令自動完成等優質使用者體驗。