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]便是編輯距離的值。 |
