(PHP 4 >= 4.0.1, PHP 5, PHP 7, PHP 8)
levenshtein — 計(jì)算兩個(gè)字符串之間的編輯距離
$str1
, string $str2
): int$str1
,$str2
,$cost_ins
,$cost_rep
,$cost_del
編輯距離,是指兩個(gè)字串之間,通過替換、插入、刪除等操作將字符串str1
轉(zhuǎn)換成str2
所需要操作的最少字符數(shù)量。
該算法的復(fù)雜度是 O(m*n)
,其中 n
和 m
分別是str1
和str2
的長(zhǎng)度 (當(dāng)和算法復(fù)雜度為O(max(n,m)**3)的similar_text()相比時(shí),此函數(shù)還是相當(dāng)不錯(cuò)的,盡管仍然很耗時(shí)。)。
在最簡(jiǎn)單的形式中,該函數(shù)只以兩個(gè)字符串作為參數(shù),并計(jì)算通過插入、替換和刪除等操作將str1
轉(zhuǎn)換成str2
所需要的操作次數(shù)。
第二種變體將采用三個(gè)額外的參數(shù)來定義插入、替換和刪除操作的次數(shù)。此變體比第一種更加通用和適應(yīng),但效率不高。
str1
求編輯距離中的其中一個(gè)字符串
str2
求編輯距離中的另一個(gè)字符串
cost_ins
定義插入次數(shù)
cost_rep
定義替換次數(shù)
cost_del
定義刪除次數(shù)
此函數(shù)返回兩個(gè)字符串參數(shù)之間的編輯距離,如果其中一個(gè)字符串參數(shù)長(zhǎng)度大于限制的255個(gè)字符時(shí),返回-1。
示例 #1 levenshtein() 例子:
<?php
// 輸入拼寫錯(cuò)誤的單詞
$input = 'carrrot';
// 要檢查的單詞數(shù)組
$words = array('apple','pineapple','banana','orange',
'radish','carrot','pea','bean','potato');
// 目前沒有找到最短距離
$shortest = -1;
// 遍歷單詞來找到最接近的
foreach ($words as $word) {
// 計(jì)算輸入單詞與當(dāng)前單詞的距離
$lev = levenshtein($input, $word);
// 檢查完全的匹配
if ($lev == 0) {
// 最接近的單詞是這個(gè)(完全匹配)
$closest = $word;
$shortest = 0;
// 退出循環(huán);我們已經(jīng)找到一個(gè)完全的匹配
break;
}
// 如果此次距離比上次找到的要短
// 或者還沒找到接近的單詞
if ($lev <= $shortest || $shortest < 0) {
// 設(shè)置最接近的匹配以及它的最短距離
$closest = $word;
$shortest = $lev;
}
}
echo "Input word: $input\n";
if ($shortest == 0) {
echo "Exact match found: $closest\n";
} else {
echo "Did you mean: $closest?\n";
}
?>
以上例程會(huì)輸出:
Input word: carrrot Did you mean: carrot?