Levenshtein與擾亂字符的距離？

Question

我正在尋找一個字符串比較度量ala Levenshtein，它也可以在字符串中的字符被加密時起作用。有誰知道這樣的指標？如果有一個可以計算這樣的度量的Python模塊，那也是很棒的。 謝謝！

Answer 1

您可以嘗試difflib庫或者還有一個名爲pylevenshtein的外部庫。

Answer 2

計算每種字符的數量（使用HashMap或等價物），然後減去結果值並取每個減法的絕對值。將所有這些加在一起，然後除以2（因爲你已經重複計算了每個差異）。

實施例：

banana 
batman 

a - 3 , 2 -> |1| -> 1 
b - 1 , 1 -> |0| -> 0 
m - 0 , 1 -> |-1| -> 1 
n - 2 , 1 -> |1| -> 1 
t - 0 , 1 -> |-1| -> 1 

因此，你必須1+1+1+1 = 4 -> 4/2 = 2

檢查：在banana，更改一個n到t和一個a到m（2的變化）和你有字母batman

如果字符串的長度不同，計算字符串長度的差異，你的差異計數（上面）。然後除以2，然後再添加該數字。

例子：

nab 
banana 

total difference count: 3 
3 - 3 = 0 -> 0/2 = 0 -> 0 + 3 = 3 

而且我也不會，因爲很多這一問題的難度是定位，你不關心使用萊文斯坦的都在這裏。

Answer 3

Levenstien距離的動態編程解決方案可以簡單地進行編輯，以便捕獲例如delhi，dehli的pair wise擾碼，並且與相應的替換或添加或刪除操作相比，可以降低權重。

編輯：此算法已存在並被命名爲Damerau–Levenshtein distance。搜索這個算法會給你一個Python package，你可以直接使用它。