python中有沒有這種字符串匹配方法的實現？

Question

我正在嘗試計算出我的數據存儲中的哪些條目是使用近似字符串匹配的近似重複項。

在python中是否有下列方法的實現，或者我需要嘗試和自己滾動？

謝謝:)

from wikipedia：

...

蠻力的方法是 計算對於P的編輯距離對於T的所有 子，然後選擇具有最小距離的 子串。 然而，該算法將具有 運行時間爲O（N 3米）

更好的解決方案[3] [4]，利用 動態規劃，使用 問題的 替代製劑：在每個位置j所述 文本T和在 圖案P中的每個位置i，計算，在 位置j結束圖案，Pi和任何 子TJ」，T的j的第i第一 字符之間的最小編輯 距離。

將這種方法應用於多個字符串的最有效方法是什麼？

Answer 1

difflib可能是答案，例如，

from difflib import context_diff 

a = 'acaacbaaca' 
b = 'accabcaacc' 

print ''.join(context_diff(a,b)) 

Answer 2

是。

google("python levenshtein") 

Answer 3

difflib.get_close_matches應該做的工作。

Answer 4

Levenshtein距離執行與fuzzywuzzy標準比率（）函數非常類似。 fuzzywuzzy使用difflib http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

例如從fuzzywuzzy文檔： https://github.com/seatgeek/fuzzywuzzy

fuzz.ratio("this is a test", "this is a test!") 
    96