levenshtein

levenshtein() 函式返回兩個字元串之間的 Levenshtein 距離。n

基本介紹

  • 中文名:字元串相似度
  • 外文名:Levenshtein 
  • 又稱: 
  • 含義:兩個字元串之間的距離
定義和用法,轉換規則,語法,提示和注釋,例子,算法實現,

定義和用法

Levenshtein 距離,又稱編輯距離,指的是兩個字元串之間,由一個轉換成另一個所需的最少編輯操作次數。許可的編輯操作包括將一個字元替換成另一個字元,插入一個字元,刪除一個字元。
例如把 kitten 轉換為 sitting:
sitten (k→s)
sittin (e→i)
sitting (→g)
levenshtein() 函式給每個操作(替換、插入和刪除)相同的權重。不過,您可以通過設定可選的 insert、replace、delete 參數,來定義每個操作的代價。

轉換規則

B ----> B unless at the end of word after "m", as in "dumb", "McComb"
C ----> X (sh) if "-cia-" or "-ch-" S if "-ci-", "-ce-", or "-cy-" SILENT if "-sci-", "-sce-", or "-scy-" K otherwise, including in "-sch-"
D ----> J if in "-dge-", "-dgy-", or "-dgi-" T otherwise
F ----> F
G ----> SILENT if in "-gh-" and not at end or before a vowel in "-gn" or "-gned" in "-dge-" etc., as in above rule J if before "i", or "e", or "y" if not double "gg" K otherwise
H ----> SILENT if after vowel and no vowel follows or after "-ch-", "-sh-", "-ph-", "-th-", "-gh-" H otherwise
J ----> J
K ----> SILENT if after "c" K otherwise
L ----> L
M ----> M
N ----> N
P ----> F if before "h" P otherwise Q ----> K
R ----> R
S ----> X (sh) if before "h" or in "-sio-" or "-sia-" S otherwise
T ----> X (sh) if "-tia-" or "-tio-" 0 (th) if before "h" silent if in "-tch-" T otherwise
V ----> F
W ----> SILENT if not followed by a vowel W if followed by a vowel
X ----> KS
Y ----> SILENT if not followed by a vowel Y if followed by a vowel Z ----> S

語法

levenshtein(string1,string2,insert,replace,delete)
參數
描述
string1
必需。要對比的第一個字元串。
string2
必需。要對比的第二個字元串。
insert
可選。插入一個字元的代價。默認是 1。
replace
可選。替換一個字元的代價。默認是 1。
delete
可選。刪除一個字元的代價。默認是 1。

提示和注釋

注釋:如果其中一個字元串超過 255 個字元,levenshtein() 函式返回 -1。
注釋:levenshtein() 函式對大小寫不敏感。
注釋:levenshtein() 函式比 similar_text() 函式更快。不過,similar_text() 函式提供需要更少修改的更精確的結果。

例子

<?php
echo levenshtein("Hello World","ello World");
echo "<br />";
echo levenshtein("Hello World","ello World",10,20,30);
?>
輸出:
1
30
PHP String 函式

算法實現

步驟說明
1
設定n為字元串s的長度。(“GUMBO”)
設定m為字元串t的長度。(“GAMBOL”)
如果n等於0,返回m並退出。
如果m等於0,返回n並退出。
構造兩個向量v0[m+1] 和v1[m+1],串聯0..m之間所有的元素。
2
初始化 v0 to 0..m。
3
檢查 s (i from 1 to n) 中的每個字元。
4
檢查 t (j from 1 to m) 中的每個字元
5
如果 s[i] 等於 t[j],則編輯代價為 0;
如果 s[i] 不等於 t[j],則編輯代價為1。
6
設定單元v1[j]為下面的最小值之一:
a、緊鄰該單元上方+1:v1[j-1] + 1
b、緊鄰該單元左側+1:v0[j] + 1
c、該單元對角線上方和左側+cost:v0[j-1] + cost
7
在完成疊代 (3, 4, 5, 6) 之後,v1[m]便是編輯距離的值。

相關詞條

熱門詞條

聯絡我們