模糊匹配編號

Question

我一直在使用Double Metaphone和Caverphone2進行字符串比較，它們在名稱，地址等方面的工作很好（Caverphone2對我來說最合適）。然而，它們產生太多的誤報，當你到的數值，如電話號碼，IP地址，信用卡號碼等

所以我看了看Luhn和Verhoeff算法和他們本質上描述什麼我想要，但不完全。他們似乎擅長驗證，但似乎並不適合模糊匹配。有沒有像Luhn和Verhoeff那樣的行爲，可以檢測到包含兩個相鄰數字的單位錯誤和轉置錯誤，用於類似於模糊字符串算法的編碼和比較目的？

我想對一個數字進行編碼，然後將其與100,000個其他數字進行比較，以找到完全相同的匹配。所以像7041234這樣的東西可能會與7041324匹配成爲一個可能的轉錄錯誤，但是像4213704這樣的東西不會。

Answer 1

Levenshteinandfriends可能很適合找到特定字符串或數字之間的距離。但是，如果您想構建拼寫更正器，則不希望在每個查詢中都運行整個單詞數據庫。

Peter Norvig基於一些簡單的「模糊匹配」拼寫糾正器，基於谷歌拼寫建議背後的一些技術，寫了a very nice article。

如果您的字典有N條目，並且平均單詞長度爲L，則「蠻力Levenshtein」方法需要時間O(N*L^3)。 Peter Norvig的方法是在輸入的某個編輯距離內生成所有單詞，然後在字典中查找它們。因此它實現了O(L^k)，其中k是所考慮的最遠的編輯距離。