levenshtein

(PHP 4 >= 4.0.1, PHP 5, PHP 7, PHP 8)

levenshtein — 計算兩個字串之間的 Levenshtein 距離

描述

levenshtein(
    string $string1,
    string $string2,
    int $insertion_cost = 1,
    int $replacement_cost = 1,
    int $deletion_cost = 1
): int

Levenshtein 距離定義為將 string1 轉換成 string2 所需替換、插入或刪除的最小字元數。該演算法的複雜度為 O(m*n)，其中 n 和 m 分別為 string1 和 string2 的長度（相較於 similar_text() 的 O(max(n,m)**3) 來說相當不錯，但仍然很耗費資源）。

如果 insertion_cost、replacement_cost 和/或 deletion_cost 不等於 1，則演算法會調整以選擇成本最低的轉換。例如，如果 $insertion_cost + $deletion_cost < $replacement_cost，則不會進行替換，而是改為插入和刪除。

參數

string1: 用於計算 Levenshtein 距離的其中一個字串。
string2: 用於計算 Levenshtein 距離的其中一個字串。
insertion_cost: 定義插入的成本。
replacement_cost: 定義替換的成本。
deletion_cost: 定義刪除的成本。

回傳值

此函式會回傳兩個引數字串之間的 Levenshtein 距離。

更新日誌

版本	描述
8.0.0	在此版本之前，levenshtein() 必須使用兩個或五個引數呼叫。
8.0.0	在此版本之前，如果其中一個引數字串的長度超過 255 個字元，levenshtein() 會回傳 `-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\n";
if ($shortest == 0) {
 echo "找到完全匹配：$closest\n";
} else {
 echo "您是指：$closest？\n";
}

?>

以上範例將輸出

Input word: carrrot
Did you mean: carrot?

參見

soundex() - 計算字串的 soundex 鍵值
similar_text() - 計算兩個字串之間的相似度
metaphone() - 計算字串的 metaphone 鍵值

發現問題？

了解如何改進此頁面 • 提交 Pull Request • 回報錯誤

＋新增註解

使用者貢獻的註解 27 則註解

上

下

luciole75w at no dot spam dot gmail dot com ¶

11 年前

levenshtein 函式會個別處理輸入字串的每個位元組。因此，對於多位元組編碼（例如 UTF-8），它可能會產生誤導性的結果。

以法文重音字詞為例
- levenshtein('notre', 'votre') = 1
- levenshtein('notre', 'nôtre') = 2 (蛤？！)

您可以輕鬆找到一個多位元組相容的 Levenshtein 函式 PHP 實作，但它當然會比 C 實作慢得多。

另一種選擇是將字串轉換為單一位元組（無損）編碼，以便它們可以輸入快速的核心 Levenshtein 函式。

這是我在搜尋引擎儲存 UTF-8 字串時使用的轉換函式，以及一個快速的基準測試。我希望這對您有所幫助。

<?php
// 將 UTF-8 編碼的字串轉換為適用於諸如 levenshtein 等函式的單字元組字串。
//
// 這個函式簡單地使用（並更新）一個客製化的動態編碼
// (輸入/輸出 map 參數)，其中非 ASCII 字元會依照出現順序重新對應到
// [128-255] 的範圍。
//
// 因此，它最多支援在共享此編碼的整個字串集合中最多 128 個不同的多位元組碼點。
//
function utf8_to_extended_ascii($str, &$map)
{
 // 找出所有多位元組字元 (參見 UTF-8 編碼規範)
 $matches = array();
 if (!preg_match_all('/[\xC0-\xF7][\x80-\xBF]+/', $str, $matches))
 return $str; // 純 ASCII 字串
 
 // 使用尚未遇到的字元更新編碼 map
 foreach ($matches[0] as $mbc)
 if (!isset($map[$mbc]))
 $map[$mbc] = chr(128 + count($map));
 
 // 最後重新對應非 ASCII 字元
 return strtr($str, $map);
}

// 教學範例，展示了先前轉換函式的使用方法，但是，
// 為了獲得更好的效能，在實際應用中，對於單一的輸入字串
// 與資料庫中的許多字串進行比對，您可能會想要
// 只對輸入進行一次預先編碼。
//
function levenshtein_utf8($s1, $s2)
{
 $charMap = array();
 $s1 = utf8_to_extended_ascii($s1, $charMap);
 $s2 = utf8_to_extended_ascii($s2, $charMap);
 
 return levenshtein($s1, $s2);
}
?>

結果 (約 6000 次呼叫)
- 參考時間核心 C 函式 (單字元組) : 30 毫秒
- UTF-8 轉為擴充 ASCII 轉換 + 核心函式 : 90 毫秒
- 完整的 PHP 實作 : 3000 毫秒

上

下

paulrowe at iname dot com ¶

16 年前

[編輯註記：原始貼文和 2 個更正合併成 1 個 -- mgf]


這裡有一個 Levenshtein 距離計算的實作，它只使用一維陣列，並且不限制字串長度。這個實作的靈感來自於也只使用一維陣列的迷宮產生演算法。


我已經使用兩個 532 字元的字串測試了這個函式，它在 0.6-0.8 秒內完成。


<?php 
/* 
* 這個函式首先進行幾個檢查，試圖節省時間。
* 1. 較短的字串始終用作「右側」字串（因為陣列的大小是基於它的長度）。
* 2. 如果左側字串為空，則傳回右側字串的長度。
* 3. 如果右側字串為空，則傳回左側字串的長度。
* 4. 如果字串相等，則傳回零距離。
* 5. 如果左側字串包含在右側字串中，則傳回長度差異。
* 6. 如果右側字串包含在左側字串中，則傳回長度差異。
* 如果以上條件均不滿足，則使用 Levenshtein 演算法。
*/ 
function LevenshteinDistance($s1, $s2) 
{ 
 $sLeft = (strlen($s1) > strlen($s2)) ? $s1 : $s2; 
 $sRight = (strlen($s1) > strlen($s2)) ? $s2 : $s1; 
 $nLeftLength = strlen($sLeft); 
 $nRightLength = strlen($sRight); 
 if ($nLeftLength == 0) 
 return $nRightLength; 
 else if ($nRightLength == 0) 
 return $nLeftLength; 
 else if ($sLeft === $sRight) 
 return 0; 
 else if (($nLeftLength < $nRightLength) && (strpos($sRight, $sLeft) !== FALSE)) 
 return $nRightLength - $nLeftLength; 
 else if (($nRightLength < $nLeftLength) && (strpos($sLeft, $sRight) !== FALSE)) 
 return $nLeftLength - $nRightLength; 
 else { 
 $nsDistance = range(1, $nRightLength + 1); 
 for ($nLeftPos = 1; $nLeftPos <= $nLeftLength; ++$nLeftPos) 
 { 
 $cLeft = $sLeft[$nLeftPos - 1]; 
 $nDiagonal = $nLeftPos - 1; 
 $nsDistance[0] = $nLeftPos; 
 for ($nRightPos = 1; $nRightPos <= $nRightLength; ++$nRightPos) 
 { 
 $cRight = $sRight[$nRightPos - 1]; 
 $nCost = ($cRight == $cLeft) ? 0 : 1; 
 $nNewDiagonal = $nsDistance[$nRightPos]; 
 $nsDistance[$nRightPos] = 
 min($nsDistance[$nRightPos] + 1, 
 $nsDistance[$nRightPos - 1] + 1, 
 $nDiagonal + $nCost); 
 $nDiagonal = $nNewDiagonal; 
 } 
 } 
 return $nsDistance[$nRightLength]; 
 } 
} 
?>

上

下

Johan Gennesson php at genjo dot fr ¶

8 年前

請注意

<?php
// Levenshtein 單引號 (U+0027 &#39;) 和右單引號 (U+2019 &#8217;)
echo levenshtein("'", "’");
?>

將會輸出 3！

上

下

engineglue at gmail dot com ¶

12 年前

我真的很喜歡 [手冊中的] 使用 levenshtein 函式來與陣列比對的範例。我遇到了需要指定結果靈敏度的需求。在某些情況下，如果比對結果差異太大，您會希望它傳回 false。我不會希望「marry had a little lamb」與「saw viii」比對，僅僅因為它是陣列中最佳的匹配。因此需要靈敏度。


<?php 
 function wordMatch($words, $input, $sensitivity){ 
 $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; 
 } 
 } 
 if($shortest <= $sensitivity){ 
 return $closest; 
 } else { 
 return 0; 
 } 
 } 
 
 $word = 'PINEEEEAPPLE'; 
 
 $words = array('apple','pineapple','banana','orange', 
 'radish','carrot','pea','bean','potato'); 
 
 echo wordMatch($words, strtolower($word), 2); 
?>

上

下

fgilles at free dot fr ¶

23 年前

論壇使用範例：使用者不能發佈太多大寫的訊息


<?php 
if ((strlen($subject)>10) and ( ( levenshtein ($subject, strtolower ($subject) / strlen ($subject) ) > .3 ) ){ 
 $subject = strtolower($subject); 
} 
?>

上

下

dale3h ¶

16 年前

結合 PHP 的範例和 Patrick 的比較百分比函式，我設計了一個函式，可以從陣列中返回最接近的單字，並將百分比賦值給一個參考變數。

<?php
 function closest_word($input, $words, &$percent = null) {
 $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;
 }
 }

 $percent = 1 - levenshtein($input, $closest) / max(strlen($input), strlen($closest));

 return $closest;
 }
?>

用法
<?php
 $input = 'carrrot';
 $words = array('apple','pineapple','banana','orange',
 'radish','carrot','pea','bean','potato');

 $percent = null;
 $found = closest_word($input, $words, $percent);

 printf('Closest word to "%s": %s (%s%% match)', $input, $found, round($percent * 100, 2));
?>

我發現當大小寫不重要時，例如比較使用者輸入的類別和現有類別列表時，在比較之前將陣列轉換為小寫可以產生更好的比較結果。

我也發現當百分比高於 75% 時，通常會是我想找的匹配項。

上

下

june05 at tilo-hauke dot de ¶

19 年前

//陣列的 levenshtein
function array_levenshtein($array1,$array2)
{ $aliases= array_flip(array_values(array_unique(array_merge($array1,$array2))));
if(count($aliases)>255) return -1;
$stringA=''; $stringB='';
foreach($array1 as $entry) $stringA.=chr($aliases[$entry]);
foreach($array2 as $entry) $stringB.=chr($aliases[$entry]);
return levenshtein($stringA,$stringB);
         }
         
// 例如，使用 array_levenshtein 來偵測使用者輸入中的特殊表達式

echo array_levenshtein(split(" ", "my name is xxx"), split(" ","my name is levenshtein"));

//輸出：1

上

下

yhoko at yhoko dot com ¶

8 年前

請注意，當使用 UTF-8 等多位元組字元時，此函式可能會造成問題。範例

<?php
print( similar_text( 'hä', 'hà' ) ); // 返回 2，但實際上只有 1 個字元匹配
?>

上

下

dschultz at protonic dot com ¶

24 年前

如果你想建立某種註冊頁面，並確保註冊的使用者不會選擇與密碼非常相似的使用者名稱，這也很有用。

上

下

carey at NOSPAM dot internode dot net dot au ¶

18 年前

我發現 levenshtein 實際上是區分大小寫的（至少在 PHP 4.4.2 中是這樣）。

<?php
$distance=levenshtein('hello','ELLO');
echo "$distance";
?>

輸出："5"，而不是 "1"。如果你正在實作使用 levenshtein 的模糊搜尋功能，你可能需要找到解決這個問題的方法。

上

下

"inerte" is my hotmail.com username ¶

21 年前

我正在使用這個函式來避免客戶資料庫中的重複資訊。

在擷取一系列列並將結果賦值給陣列值後，我使用 foreach 迴圈，將其 levenshtein() 與使用者提供的字串進行比較。

這有助於避免人們重新註冊 "John Smith"、"Jon Smith" 或 "Jon Smit"。

當然，如果使用者真的想這麼做，我無法阻止操作，但會顯示類似這樣的建議：「有一個類似名稱的客戶。」，後面接著類似字串的列表。

上

下

justin at visunet dot ie ¶

19 年前

<?php

 /*********************************************************************
 * 以下函數 btlfsa（用於拼寫應用程式時比 Levenshtein 更好）
 * 在比較 haert 和 haart 及 heart 等單字時，能產生更好的結果。
 *
 * 例如，以下是將 'haert' 與 'herat, haart, heart, harte' 比較時，Levenshtein 與 btlfsa 的輸出結果：
 *
 * btlfsa('haert','herat'); 輸出為.. 3
 * btlfsa('haert','haart'); 輸出為.. 3
 * btlfsa('haert','harte'); 輸出為.. 3
 * btlfsa('haert','heart'); 輸出為.. 2
 *
 * levenshtein('haert','herat'); 輸出為.. 2
 * levenshtein('haert','haart'); 輸出為.. 1
 * levenshtein('haert','harte'); 輸出為.. 2
 * levenshtein('haert','heart'); 輸出為.. 2
 *
 * 換句話說，如果您使用 Levenshtein，'haart' 會是與 'haert' 最接近的匹配。而 btlfsa 則認為它應該是 'heart'
 */

 function btlfsa($word1,$word2)
 {
 $score = 0;

 // 對於每個不同的字元，分數加 2
 // 因為這是一個很大的差異

 $remainder = preg_replace("/[".preg_replace("/[^A-Za-z0-9\']/",' ',$word1)."]/i",'',$word2);
 $remainder .= preg_replace("/[".preg_replace("/[^A-Za-z0-9\']/",' ',$word2)."]/i",'',$word1);
 $score = strlen($remainder)*2;

 // 將字串長度差異加到分數上
 $w1_len = strlen($word1);
 $w2_len = strlen($word2);
 $score += $w1_len > $w2_len ? $w1_len - $w2_len : $w2_len - $w1_len;

 // 計算有多少字母在不同的位置
 // 並將其加到分數上，例如：
 //
 // h e a r t
 // 1 2 3 4 5
 //
 // h a e r t a e = 2
 // 1 2 3 4 5 1 2 3 4 5
 //

 $w1 = $w1_len > $w2_len ? $word1 : $word2;
 $w2 = $w1_len > $w2_len ? $word2 : $word1;

 for($i=0; $i < strlen($w1); $i++)
 {
 if ( !isset($w2[$i]) || $w1[$i] != $w2[$i] )
 {
 $score++;
 }
 }

 return $score;
 }

 // *************************************************************
 // 以下是一個完整的程式碼範例，顯示差異

 $misspelled = 'haert';

 // 假設這些是由 soundex 或 metaphone 返回的範例建議..
 $suggestions = array('herat', 'haart', 'heart', 'harte');

 // 首先，根據 Levenshtein 對陣列進行排序
 $levenshtein_ordered = array();
 foreach ( $suggestions as $suggestion )
 {
 $levenshtein_ordered[$suggestion] = levenshtein($misspelled,$suggestion);
 }
 asort($levenshtein_ordered, SORT_NUMERIC );

 print "<b>依 Levenshtein 排序的建議...</b><ul><pre>";
 print_r($levenshtein_ordered);
 print "</pre></ul>";

 // 其次，根據 btlfsa 對陣列進行排序
 $btlfsa_ordered = array();
 foreach ( $suggestions as $suggestion )
 {
 $btlfsa_ordered[$suggestion] = btlfsa($misspelled,$suggestion);
 }
 asort($btlfsa_ordered, SORT_NUMERIC );

 print "<b>依 btlfsa 排序的建議...</b><ul><pre>";
 print_r($btlfsa_ordered);
 print "</pre></ul>";

?>

上

下

atx dot antrax at gmail dot com ¶

16 年前

我建立了一個函數，可以移除 Levenshtein 函數的長度限制，並使用 similar_text 調整結果。

<?php
function _similar($str1, $str2) {
 $strlen1=strlen($str1);
 $strlen2=strlen($str2);
 $max=max($strlen1, $strlen2);

 $splitSize=250;
 if($max>$splitSize)
 {
 $lev=0;
 for($cont=0;$cont<$max;$cont+=$splitSize)
 {
 if($strlen1<=$cont || $strlen2<=$cont)
 {
 $lev=$lev/($max/min($strlen1,$strlen2));
 break;
 }
 $lev+=levenshtein(substr($str1,$cont,$splitSize), substr($str2,$cont,$splitSize));
 }
 }
 else
 $lev=levenshtein($str1, $str2);

 $porcentage= -100*$lev/$max+100;
 if($porcentage>75)// 使用 similar_text 調整
 similar_text($str1,$str2,$porcentage);

 return $porcentage;
}
?>

上

下

WiLDRAGoN ¶

9 年前

一些小的更改允許您計算多個單字。

<?php

$input = array();
$dictionary = array();
foreach ($input as $output) {
 $shortest = -1;
 foreach ($dictionary as $word) {
 $lev = levenshtein($output, $word);
 if ($lev == 0) {
 $closest = $word;
 $shortest = 0;
 }
 if ($lev <= $shortest || $shortest < 0) {
 $closest = $word;
 $shortest = $lev;
 }
 }
 echo "輸入的字詞： $output\n";
 if ($shortest == 0) {
 echo "找到完全匹配的字詞： $closest\n";
 } else {
 echo "您是不是要找： $closest?\n";
 }
}

?>

上

下

Chaim Chaikin ¶

13 年前

關於上面的範例 #1，是否應該先使用簡單的 php == 比較來檢查字串是否相等，甚至在用 levenshtein() 測試字詞之前？

像這樣：

<?php
// 輸入拼錯的字詞
$input = 'carrrot';

// 要比對的字詞陣列
$words = array('apple','pineapple','banana','orange',
 'radish','carrot','pea','bean','potato');

// 尚未找到最短距離
$shortest = -1;

// 迴圈遍歷字詞，找出最接近的字詞
foreach ($words as $word) {

 // 檢查是否有完全匹配
 if ($input == $word) {

 // 最接近的字詞是這個 (完全匹配)
 $closest = $word;
 $shortest = 0;

 // 跳出迴圈；我們已經找到完全匹配的字詞
 break;
 }

 // 計算輸入字詞與目前字詞之間的距離
 $lev = levenshtein($input, $word);

 // 如果此距離小於下一個找到的最短距離，或尚未找到下一個最短字詞
 if ($lev <= $shortest || $shortest < 0) {
 // 設定最接近的匹配和最短距離
 $closest = $word;
 $shortest = $lev;
 }
}

echo "輸入的字詞： $input\n";
if ($shortest == 0) {
 echo "找到完全匹配的字詞： $closest\n";
} else {
 echo "您是不是要找： $closest?\n";
}

?>

上

下

mcreuzer at r-world dot com ¶

19 年前

我正在使用 Levenshtein 距離來排序我的搜尋結果。

我有一個搜尋人名的頁面。我對 MySQL 中的名稱執行 SOUNDEX() 搜尋。MySQL SOUNDEX() 會為我執行「模糊」搜尋。

然後，我計算搜尋詞與 SOUNDEX() 搜尋找到的實際名稱之間的 Levenshtein 距離。這會給我一個分數，表示我的結果與搜尋字串的接近程度。

然後，我可以排序我的結果以顯示，最接近的結果會先列出。

<?php
// 此處包含資料庫查詢的 PHP 程式碼
 usort($searchresults, "finallevenshteinsortfunction");

function finallevenshteinsortfunction($a, $b)
{
 if(($a['levenshtein'] > $b['levenshtein']) || ( $a['levenshtein'] == $b['levenshtein'] && strnatcasecmp( $a['Last_Name'], $b['Last_Name']) >= 1) ){ return $a['levenshtein'];} // 好的... Levenshtein 距離較大，或是 Levenshtein 距離相同，但姓氏的字母順序較先
 elseif($a['levenshtein'] == $b['levenshtein']){ return '0';} // Levenshtein 距離相同
 elseif($a['levenshtein'] < $b['levenshtein']){ return -$a['levenshtein'];}
 else{die("<!-- 一個可怕的死亡 -->");}
}
?>

上

下

gzink at zinkconsulting dot com ¶

21 年前

嘗試將此與 metaphone() 結合，以獲得真正驚人的模糊搜尋功能。稍微玩一下，當正確實作時，結果可能非常嚇人（使用者會認為電腦幾乎有心電感應）。我希望拼字檢查程式能像我寫的程式碼一樣好用。


如果合理的話，我會發布我的完整程式碼，但由於著作權問題，這是不合理的。我只希望有人能從這個小技巧中學習！

上

下

bisqwit at iki dot fi ¶

22 年前

在本手冊註記時，使用者定義的內容
在 levenshtein() 中尚未實作。我想要類似的東西
所以我寫了自己的函式。請注意，這
不會傳回 levenshtein() 的差異，而是
一個將字串轉換為另一個字串的操作陣列。

請注意，差異查找部分 (resync)
在長字串上可能非常慢。

<?php

/* matchlen(): 傳回 $a 和 $b 開頭匹配的
 * 子字串長度
 */
function matchlen(&$a, &$b)
{
 $c=0;
 $alen = strlen($a);
 $blen = strlen($b);
 $d = min($alen, $blen);
 while($a[$c] == $b[$c] && $c < $d)
 $c++; 
 return $c;
}

/* 傳回一個表格，描述 $a 和 $b 的差異 */
function calcdiffer($a, $b)
{
 $alen = strlen($a);
 $blen = strlen($b);
 $aptr = 0;
 $bptr = 0;
 
 $ops = array();
 
 while($aptr < $alen && $bptr < $blen)
 {
 $matchlen = matchlen(substr($a, $aptr), substr($b, $bptr));
 if($matchlen)
 {
 $ops[] = array('=', substr($a, $aptr, $matchlen));
 $aptr += $matchlen;
 $bptr += $matchlen;
 continue;
 }
 /* 找到差異 */
 
 $bestlen=0;
 $bestpos=array(0,0); 
 for($atmp = $aptr; $atmp < $alen; $atmp++)
 {
 for($btmp = $bptr; $btmp < $blen; $btmp++)
 {
 $matchlen = matchlen(substr($a, $atmp), substr($b, $btmp));
 if($matchlen>$bestlen)
 {
 $bestlen=$matchlen; 
 $bestpos=array($atmp,$btmp);
 }
 if($matchlen >= $blen-$btmp)break;
 }
 }
 if(!$bestlen)break;
 
 $adifflen = $bestpos[0] - $aptr;
 $bdifflen = $bestpos[1] - $bptr;

 if($adifflen)
 {
 $ops[] = array('-', substr($a, $aptr, $adifflen));
 $aptr += $adifflen;
 }
 if($bdifflen)
 {
 $ops[] = array('+', substr($b, $bptr, $bdifflen));
 $bptr += $bdifflen;
 }
 $ops[] = array('=', substr($a, $aptr, $bestlen));
 $aptr += $bestlen;
 $bptr += $bestlen;
 }
 if($aptr < $alen)
 {
 /* b 有太多東西 */
 $ops[] = array('-', substr($a, $aptr));
 }
 if($bptr < $blen)
 {
 /* a 的東西太少 */
 $ops[] = array('+', substr($b, $bptr));
 }
 return $ops;
}
 

範例:

$tab = calcdiffer('T?m? on jonkinlainen testi',
 'T?m? ei ole mink??nlainen testi.'); 
$ops = array('='=>'Ok', '-'=>'移除', '+'=>'新增');
foreach($tab as $k)
 echo $ops[$k[0]], " '", $k[1], "'\n";

範例輸出:

Ok 'T?m? '
移除 'on jonki'
新增 'ei ole mink??'
Ok 'nlainen testi'
新增 '.'

上

下

hartmut at php dot net ¶

4 個月前

這個函式是以位元組為單位操作，而不是字元，因此在處理 UTF-8 編碼的 Unicode 字串時，其用途有限。

將輸入字串通過 Normalizer（ https://php.dev.org.tw/manual/en/class.normalizer.php ）處理至少可以有所幫助，但您仍然需要注意，替換、插入或刪除單個 UTF-8 編碼的 Unicode 字元可能會錯誤地報告 2、3 或 4 的成本，具體取決於表示它的 UTF-8 序列的長度，或者在處理組合字元修飾符時甚至更高。

上

下

peratik at gmail dot com ¶

7 年前

python get_close_matches 等效函式

function get_close_matches($str, $arr) {
$closest = 1000;
$word = false;
foreach($arr as $w) {
$po = levenshtein($str, $w);
if ($po<$closest) {
$closest = $po;
$word = $w;
        }
    }
return $word;
}

上

下

qbolec ¶

9 年前

在少數情況下，您想要
1. 多位元組 UTF-8 字元
2. 線性記憶體消耗（即 O(n+m)，而不是 O(n*m)）
3. 學習最長公共子序列的字串
4. 合理的（即 O(n*m)）時間複雜度
請考慮此實作
<?php
class Strings
{
 public static function len($a){
 return mb_strlen($a,'UTF-8');
 }
 public static function substr($a,$x,$y=null){
 if($y===NULL){
 $y=self::len($a);
 }
 return mb_substr($a,$x,$y,'UTF-8');
 }
 public static function letters($a){
 $len = self::len($a);
 if($len==0){
 return array();
 }else if($len == 1){
 return array($a);
 }else{
 return Arrays::concat(
 self::letters(self::substr($a,0,$len>>1)),
 self::letters(self::substr($a,$len>>1))
 );
 }
 }
 private static function lcs_last_column(array $A,array $B){
 $al=count($A);
 $bl=count($B);
 $last_column = array();
 for($i=0;$i<=$al;++$i){
 $current_row = array();
 for($j=0;$j<=$bl;++$j){
 //$a[0,$i) vs $b[0,$j)
 if($i==0 || $j == 0){
 $v = 0;
 }else if($A[$i-1]===$B[$j-1]){
 $v = 1 + $last_row[$j-1];
 }else{
 $v = max($last_row[$j],$current_row[$j-1]);
 }
 $current_row[] = $v;
 }
 $last_column[] = $current_row[$bl];
 $last_row = $current_row;
 }
 return $last_column;
 }
 public static function lcs($a,$b){
 $A = self::letters($a);
 $B = self::letters($b);
 $bl=count($B);
 if($bl==0){
 return '';
 }else if($bl==1){
 return FALSE===array_search($B[0],$A,true)?'':$B[0];
 }
 $left=self::lcs_last_column($A,array_slice($B,0,$bl>>1));
 $right=array_reverse(self::lcs_last_column(array_reverse($A),array_reverse(array_slice($B,$bl>>1))));

 $best_i = 0;
 $best_lcs = 0;
 foreach($left as $i => $lcs_left){
 $option = $lcs_left + $right[$i];
 if($best_lcs < $option){
 $best_lcs = $option;
 $best_i = $i;
 }
 }
 return 
 self::lcs(self::substr($a,0,$best_i), self::substr($b,0,$bl>>1)).
 self::lcs(self::substr($a,$best_i), self::substr($b,$bl>>1));
 }
?>
這是一個經典的實作，其中使用了一些技巧
1. 字串在 O(n log n) 時間內被分解為多位元組字元
2. 我們並非在預先計算的二維陣列中尋找最長路徑，而是尋找位於中間列的最佳點。這透過將第二個字串分成兩半，並遞迴呼叫演算法兩次來達成。我們從遞迴呼叫中唯一需要的是中間列的值。訣竅是從每個遞迴呼叫中返回最後一列，這是我們左半部分所需要的，但右半部分需要一個額外的技巧 - 我們簡單地鏡像字串和陣列，以便最後一列成為第一列。然後，我們只需找到使每個部分長度總和最大化的行。
3. 可以證明演算法所消耗的時間與（虛擬）二維陣列的面積成正比，因此它是 O(n*m)。

上

下

luka8088 at gmail dot com ¶

16 年前

簡單的 levenshtein 函數，沒有字串長度限制...

<?php

function levenshtein2($str1, $str2, $cost_ins = null, $cost_rep = null, $cost_del = null) {
 $d = array_fill(0, strlen($str1) + 1, array_fill(0, strlen($str2) + 1, 0));
 $ret = 0;
 
 for ($i = 1; $i < strlen($str1) + 1; $i++)
 $d[$i][0] = $i;
 for ($j = 1; $j < strlen($str2) + 1; $j++)
 $d[0][$j] = $j;
 
 for ($i = 1; $i < strlen($str1) + 1; $i++)
 for ($j = 1; $j < strlen($str2) + 1; $j++) {
 $c = 1;
 if ($str1{$i - 1} == $str2{$j - 1})
 $c = 0;
 $d[$i][$j] = min($d[$i - 1][$j] + 1, $d[$i][$j - 1] + 1, $d[$i - 1][$j - 1] + $c);
 $ret = $d[$i][$j];
 }
 
 return $ret;
}

?>

上

下

genialbrainmachine at dot IHATESPAM dot tiscali dot it ¶

21 年前

我寫這個函式是為了在要寫入資料庫的資料和已存在的資料之間進行「智慧型」比較。
不僅計算距離，還平衡每個欄位的距離。
每個欄位的距離。
<?php
/*
此函式計算字串陣列 "$record" 與比較的陣列 "$compared" 之間的平衡百分比距離，
透過權重陣列 "$weight" 進行平衡。這三個陣列必須具有相同的索引。
若要計算不平衡的距離，請將所有權重設定為 1。
使用的公式為：
百分比距離 = sum(欄位_萊文斯坦距離 * 欄位權重) / sum(記錄欄位長度 * 欄位權重) * 100
*/
function search_similar($record, $weights, $compared, $precision=2) {
 $field_names = array_keys($record);
 # $record 的「加權長度」和「加權距離」。
 foreach ($field_names as $field_key) {
 $record_weight += strlen($record[$field_key]) * $weights[$field_key];
 $weighted_distance += levenshtein($record[$field_key],$compared[$field_key]) * $weights[$field_key];
 }
 # 建立結果..
 if ($record_weight) {
 return round(($weighted_distance / $record_weight * 100),$precision);
 } elseif ((strlen(implode("",$record)) == 0) && (strlen(implode("",$compared)) == 0)) { // 空記錄
 return round(0,$precision);
 } elseif (array_sum($weights) == 0) { // 所有權重 == 0
 return round(0,$precision);
 } else {
 return false;
 }
 /*
 請仔細區分 0 結果和 false 結果。
 如果出現以下情況，函式會返回 0（如果 $precision 為 2，則為 '0.00'，依此類推）：
 - $record 和 $compared 相等（即使 $record 和 $compared 為空）；
 - 所有權重都為 0（可能表示「不在乎任何欄位」）。
 相反地，如果 $record 為空，但權重不全為 0，且 $compared 不為空，則函式會返回 false。這會導致「除以 0」的錯誤。
 我編寫了這種檢查：
 
 if ($rel_dist = search_similar(...)) {
 print $rel_dist;
 } elseif ($rel_dist == "0.00") { // 假設 $precision 為 2
 print $rel_dist;
 } else {
 print "infinite";
 }
 
 */
 }
?>

上

下

dinesh AT dinsoft DOT net ¶

18 年前

這是一個字串重新同步函式

<?php
// 尋找將 $b 修改為 $a 所需的操作，並利用它們的相似性 (Finds the operations required to change $b to $a)
// 與 Hex Workshop 的 Resynch Compare 功能相同
//
// 參數：
// $a 第一個字串（目標字串，target）
// $b 第二個字串（來源字串，source）
// $l 視為相似區塊所需匹配的位元組數 (number of matching bytes required)
// $s 搜尋相似區塊的最大距離 (search window)
//
// 回傳值：
// 陣列
// 陣列
// [0] 操作：+ 新增，- 刪除，/ 取代，= 匹配
// [1] 來源偏移量
// [2] 來源計數
// [3] 目標偏移量
// [4] 目標計數
//
function str_resynch($a,$b,$l=32,$s=2048) {
 $r=array();
 for($i=0,$c=strlen($a),$cc=strlen($b),$ii=0,$z=$s-1,$z2=($z<<1)+1; $i<$c; $i++) {
 $d=$i-$z;
 $d=($d<$ii)?substr($b,$ii,$z2-$ii+$d):substr($b,$d,$z2);

 $p=strpos($d,$a{$i});
 $n=0;
 while ($p!==FALSE) {
 $m=1;
 $bi=$i;
 $bp=$p;
 $p+=$ii;
 while ((++$i<$c) && (++$p<$cc)) {
 if ($a{$i}!=$b{$p}) break;
 $m++;
 }
 if ($m<$l) {
 $i=$bi;
 $n=$bp+1;
 $p=@strpos($d,$a{$i},$n);
 }
 else {
 $i--;
 $r[]=array($bi,$bp+$ii,$m); // offset a, offset b, Count
 $ii=$p;
 break;
 }
 }
 }

 if (!count($r)) return ($cc)?array('/',0,$c,0,$cc):array(array('+',0,$c,0,0));

 $o=array();
 $bi=0;
 $bp=0;
 for($i=0,$m=count($r);$i<$m;$i++) {
 if ($r[$i][0]!=$bi) {
 if ($r[$i][1]!=$bp) {
 // 取代
 $o[]=array('/',$bi,$r[$i][0]-$bi,$bp,$r[$i][1]-$bp);
 $bi=$r[$i][0];
 $bp=$r[$i][1];
 }
 else {
 // 插入
 $o[]=array('+',$bi,$r[$i][0]-$bi,$bp,0);
 $bi=$r[$i][0];
 }
 }
 elseif ($r[$i][1]!=$bp) {
 // 刪除
 $o[]=array('-',$bi,0,$bp,$r[$i][1]-$bp);
 $bp=$r[$i][1];
 }

 // 匹配
 $o[]=array('=',$r[$i][0],$r[$i][2],$r[$i][1],$r[$i][2]);
 $bi+=$r[$i][2];
 $bp+=$r[$i][2];
 }

 if ($c!=$bi) {
 if ($cc!=$bp) $o[]=array('/',$bi,$c-$bi,$bp,$cc-$bp);
 else $o[]=array('+',$bi,$c-$bi,$bp,0);
 }
 elseif ($cc!=$bp) $o[]=array('-',$bi,0,$bp,$cc-$bp);

 return $o;
}
?>

上

下

Anonymous ¶

22 年前

對於拼字檢查應用程式，如果您假設打字員每個單字的前兩個或三個字元都正確，則可以容忍延遲。 那麼您只需要計算字典一小部分的距離。 這是一種折衷方案，但我認為很多拼字檢查器都會這樣做。
有關使用此功能的網站搜尋範例，請參閱此頁面上的 PHP 手冊搜尋按鈕。 它似乎正在為 PHP 函數列表執行此操作。

上

下

ad1n at dc dot uba dot ar ¶

24 年前

當您想要尋找相似的匹配項而不是完全匹配項時，可以使用此方法。 您可以將單字與字典之間的距離檢查結果排序，並對它們進行排序以查看哪些更相似。 當然，這仍然會是一項非常耗費資源的任務。

上

下

-1

jlsalinas at gmx dot net ¶

21 年前

關於 fgilles 於 2001 年 4 月 26 日發表的文章，我建議不要使用 levenshtein() 函數來測試過度使用大寫字母，除非您有很多時間可以在主機上浪費。 ;) 無論如何，我認為這是一個有用的功能，因為當我讀到整篇都是大寫字母的消息時，我真的會感到很惱火。

PHP 的 levenshtein() 函數只能處理最多 255 個字元，這對於使用者輸入來說是不現實的（僅此文章的第一段就有 285 個字元）。 如果您選擇使用能夠處理超過 255 個字元的自訂函數，效率是一個重要的問題。

我使用這個針對這種情況的特定函數，但速度快得多

function ucase_percent ($str) {
$str2 = strtolower ($str);
    
$l = strlen ($str);
$ucase = 0;

for ($i = 0; $i < $l; $i++) {
if ($str{$i} != $str2{$i}) {
$ucase++;
        }
    }
    
return $ucase / $l * 100.0;
}

我認為 10% 對於書寫英文來說已經足夠了（也許其他像德文這樣使用較多大寫字母的語言需要更多）。如果有一些句子使用大寫（每個人都有偶爾大喊的權利），20% 就足夠了；所以我使用 30% 的閾值。當超過這個值時，我會將整個訊息轉換為小寫。

希望您覺得它有用，並且有助於保持網路免受不文明人士的影響。

＋新增註解