使用編輯距離對名稱進行消歧

Question

我有一個巨大的公司名稱列表和與這些名稱相關聯的大量郵編。 （> 100,000）。

我必須輸出相似的名稱（例如，AJAX INC和AJAX是同一家公司，我選擇了編輯距離爲4個字符的閾值），但前提是其相應的郵編編碼也匹配。

麻煩的是，我可以將所有這些公司名稱放在字典中，並將郵遞區號和其他特性的列表與該字典鍵相關聯。然而，那麼我必須匹配每對，並與O（n^2），它需要永遠。有沒有更快的方法來做到這一點？

Answer 1

創建一個以zipcode爲密鑰的字典，並將公司名稱列表作爲值。現在你只需要匹配公司名稱每個郵編，一個小得多的搜索空間。