快速路

Question

快速的方法來搜索基於非字面比較

我開發過相當大的數據集一個小的搜索，基本上所有字符串。表格字段之間的關係很簡單，儘管比較不一定是字面的。即它應該能夠關聯「filippo」，「philippo」，「filipo」等等。

我已經找到了一些方法就可以完成，非常頻繁絆倒在Levinstein距離（this，here和here），雖然我不知道這是對我的具體情況的切實可行的。

簡而言之，我有兩個表格，一個是帶有「搜索鍵」的小表格，另一個是應該執行搜索的更大的表格。兩個表都有相同的字段，它們都具有相同的「含義」。例如。

KEYS_TABLE 
# | NAME | MIDNAME | SURNAME | ADDRESS   | PHONE 
1 | John | Fake | Doe  | Sesame St.  | 333-12-32 
2 | Ralph | Stue | Michel | Bart. Ghost St. | 778-13000 
... 

和

SEARCH_TABLE 
# | NAME  | MIDNAME | SURNAME | ADDRESS   | PHONE 
... 
532 | Jhon  | F.  | Doe  | Sesame Street | 3331232 
... 
999 | Richard | Dalas | Doe  | Sesame St.  | 333-12-32 

所有我想要做的是操作系統獲得某種度量或排名爲每個給定的紀錄KEYS_TABLE，報告從SEARCH_TABLE超過一定關聯的所有記錄（定義或者通過度量或者簡單的一些「KNN」類似的方法）。

我說萊文斯坦距離可能不實際，因爲它需要計算每行中的每個字段在KEYS_TABLE x SEARCH_TABLE。考慮到SEARCH_TABLE有大約4億條記錄，KEYS_TABLE從100k到1mil不等，結果數量太大。

我希望有一些方法可以預先豐富這兩個表格，或者一些更簡單（更便宜）的方式來執行搜索。

值得一提的是，我被允許隨意轉換數據。例如將St.標準化爲st，Street至st，刪除特殊字符等。

我的選擇是什麼？

Answer 1

一種方法（！啓發式）我能想到的是：

除了表中的信息字段，每個字段還可以存儲一些stemming算法得到其標準化形式。如果您使用的是java，lucene的EnglishAnalyzer可能會幫助您完成此步驟。

做一個準確比較使用標準方法爲table1中的每個條目查找候選列表。如果table2中的條目e2的在table1中具有某些常規字段，其中規範化形式與常規形式相匹配，則該條目將成爲e1的候選字段。這可以使用一些允許快速搜索字符串的數據結構來高效地完成 - 其中有很多。

對於e1每個條目 - 找到「最佳」人選/對IT方面在列表中，使用您選擇的準確度（例如您的建議leneshtein距離）

您可能需要做一些後期處理以確保0123'中沒有兩個元素映射到table2中的相同元素，如果這是個問題。

Answer 2

根據可能的拼寫錯誤，您可能可以使用Soundex或Metaphone進行搜索。