字符串匹配算法

Question

我有一個商業數據庫的Python應用程序，我希望能夠按名稱搜索業務（用於自動完成的目的）。
例如，考慮名稱「最好買」，「麥當勞」，「索尼」和「蘋果」。

我想「應用程序」返回「蘋果」，以及「APPEL」和「PLE」。 「麥當勞」應該返回「麥當勞」。 「bst b」和「best-buy」都應該返回「best buy」。

我正在尋找哪種算法，並且它是否具有python實現？

謝謝！

Answer 1

該Levenshtein distance應該做的。

環顧四周 - 有許多語言的實現。

Answer 2

Soundex或Metaphone可能工作。

Answer 3

我想你正在尋找的是數據質量和數據清理的一個巨大的領域。我擔心如果你能找到一個關於這個python的實現，因爲它必須能夠清理大量數據庫中可能具有商業價值的數據。

Answer 4

Levenshtein距離將做到這一點。

注：這是一個距離，你必須把它計算到數據庫中的每一個字符串，它可以是一個大問題，如果你有很多條目。

如果你有那麼這個問題記錄所有的錯別字用戶作出（錯字=沒有直接匹配）和離線建立包含所有typo->修改映射修正數據庫。有些公司這樣做更聰明，例如：谷歌觀察用戶如何糾正自己的拼寫錯誤，並從中學習映射。

Answer 5

Levensthein距離走向正確的方向，但只有一半的路。有幾個技巧可以讓它使用半場比賽。

一個將是使用一個子序列動態時間規整（DTW實際上是levensthein距離的概括）。爲此，您在計算成本矩陣時放寬開始和結束案例。如果您只放鬆其中一個條件，則可以通過拼寫檢查自動完成。我不確定是否有可用的python實現，但如果你想自己實現它，它不應該超過10-20 LOC。

另一個想法是使用一個特里的加快，它可以在多個結果呢DTW/Levensthein同時放（速度大大提高了，如果你的數據庫很大）。在IEEE的Tries上有一篇關於Levensthein的論文，所以你可以在那裏找到算法。再次爲此，您需要放鬆最終邊界條件，以便獲得部分匹配。然而，由於你在樹中下臺，你只需要檢查什麼時候你已經完全消耗了輸入，然後返回所有樹葉。

Answer 6

檢查這一項http://docs.python.org/library/difflib.html 它應該幫助你