levenshtein
(PHP 4 >= 4.0.1, PHP 5, PHP 7, PHP 8)
levenshtein — 計算兩個字串之間的編輯距離
說明
levenshtein(string
$str1, string $str2): intlevenshtein(
string
string
int
int
int
): int
string
$str1,string
$str2,int
$cost_ins,int
$cost_rep,int
$cost_del): int
編輯距離，是指兩個字串之間，通過替換、插入、刪除等操作將字串str1轉換成str2所需要操作的最少字元數量。
該演算法的複雜度是 O(m*n)，其中 n 和 m 分別是str1 和str2的長度 （當和演算法複雜度為O(max(n,m)**3)的similar_text()相比時，此函式還是相當不錯的，儘管仍然很耗時。）。
在最簡單的形式中，該函式只以兩個字串作為參數，並計算通過插入、替換和刪除等操作將str1轉換成str2所需要的操作次數。
第二種變體將採用三個額外的參數來定義插入、替換和刪除操作的次數。此變體比第一種更加通用和適應，但效率不高。
參數
-
str1 -
求編輯距離中的其中一個字串
-
str2 -
求編輯距離中的另一個字串
-
cost_ins -
定義插入次數
-
cost_rep -
定義替換次數
-
cost_del -
定義刪除次數
返回值
此函式返回兩個字串參數之間的編輯距離，如果其中一個字串參數長度大於限制的255個字元時，返回-1。
範例
示例 #1 levenshtein() 例子：
<?php
// 輸入拼寫錯誤的單詞
$input = 'carrrot';
// 要檢查的單詞陣列
$words = array('apple','pineapple','banana','orange',
'radish','carrot','pea','bean','potato');
// 目前沒有找到最短距離
$shortest = -1;
// 遍歷單詞來找到最接近的
foreach ($words as $word) {
// 計算輸入單詞與目前單詞的距離
$lev = levenshtein($input, $word);
// 檢查完全的匹配
if ($lev == 0) {
// 最接近的單詞是這個（完全匹配）
$closest = $word;
$shortest = 0;
// 退出循環；我們已經找到一個完全的匹配
break;
}
// 如果此次距離比上次找到的要短
// 或者還沒找到接近的單詞
if ($lev <= $shortest || $shortest < 0) {
// 設定最接近的匹配以及它的最短距離
$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";
}
?>
以上例程會輸出：
Input word: carrrot Did you mean: carrot?
參見
- soundex() - Calculate the soundex key of a string
- similar_text() - 計算兩個字串的相似度
- metaphone() - Calculate the metaphone key of a string