我需要寫一個返回最接近的匹配基於用戶輸入的姓名和地址的聯繫人的算法。這兩者都是令人不安的，因爲有這麼多的方法輸入公司名稱和地址，例如：加權搜索算法找到像聯繫人
Company A, 123 Any Street Suite 200, Anytown, AK 99012
Comp. A, 123 Any St., Suite 200, Anytown, AK 99012
CA, 123 Any Street Ste 200, Anytown, AK 99012
我已經看過這樣的名稱的Levenshtein距離，但似乎並沒有很大的工具，因爲它們可以縮寫名稱。我正在尋找可能的最多信息匹配的東西。
我最初的嘗試是首先以郵政編碼的前5位數字限制結果，然後嘗試根據其他信息過濾到一個結果，但必須有一個更加標準的方法來完成此操作。我在.NET中工作，但會查看您可以提供的任何代碼，以瞭解如何完成此操作。
我並不確切，現在這是如何實現的，但所有主要的快遞公司（聯邦快遞，美國郵政，UPS）似乎對他們的數據庫相匹配的地址，你輸入和其轉化爲規範化形式的一種方式。正如我在多個網站上看到過這種情況（亞馬遜想到的），我假設這個功能有一個API，但我不知道在哪裏尋找它，以及它是否適合您的目的。
雖然只是一個想法。
編輯：我發現USPS API
我認爲基於郵政編碼濾波首先是最簡單的，因爲發現它是相當明確的。從那裏你可以提取城市和街道。我不知道如何去查找名稱，但如果您已經有（名稱，地址）對的數據庫是可行的，它似乎與地址匹配。
敦& Bradstreet的做到這一點。他們要收錢，因爲這真的很難。沒有「標準」解決方案。這在D & B這樣的服務或自己推出的服務之間通常是一個痛苦的選擇。
其實，這聽起來像一個*有趣*的問題...所以我會去與後來:-) – 2009-01-28 01:14:19
作爲一個開始，我可能會做一個詞索引搜索。這將意味着兩個階段：
離線階段：通過生成的關鍵字的所有地址的索引。例如，「公司」，「A」和「123」都將成爲您在上面提供的地址的關鍵字。你可以做一些詞幹，這意味着像「街道」這樣的詞你也可以在它的索引中加入一個詞「st」。
在線階段：用戶給你的搜索查詢。將搜索查詢分解爲所有關鍵字，並查找數據庫中每個關鍵字的所有可能匹配項。計算每個地址上匹配關鍵字的數量。然後根據匹配關鍵字的數量對結果進行排序。如果沒有太多匹配，這應該能夠很快完成，因爲它只是一些排序列表合併和增量，最後是一種排序。
鑑於您知道您的問題的領域，您可以專門化該算法以使用關於該領域的知識 - 例如前面提到的郵政編碼過濾。
也只是爲了讓我能夠爲您提供更好的答案，您是否使用SQL數據庫？我問，因爲我會這樣做的方式是將關鍵字索引存儲在SQL數據庫中，然後通過關鍵字進行搜索的SQL查詢變得非常容易，因爲數據庫完成所有工作。
也許不是僅將Levenshtein用於名稱，而是與聯繫人的整個字符串表示形式一起使用時可能會有用。例如，你的第一個例子到第二個例子的距離是7到9。考慮到字符串長度爲54,50和45，這似乎是一個相對有用和相當簡單的相似性度量。
這是我會做的。我不知道算法，所以我只是使用有意義的東西。
我假設這個人會提供姓名，街道地址，城市名稱，州名稱和郵政編碼。
如果郵政編碼提供了9個數字，或者有一個連字符，我會將其分成5個數字。我將在數據庫中搜索具有該郵政編碼的所有地址。[查詢1] 然後，我將比較州數字與數據庫中的狀態字母。如果不匹配，那麼我會告訴用戶。城市名稱也一樣。
據我所知，街道名稱並不是數字，只有街道上的房子裏有數字。此外，房屋編號通常在一開始，除非是房屋或套房編號。
所以我會做正則表達式來搜索數字和旁邊的下一個空格或逗號。然後找到沒有句點（。）或以逗號結尾的第一個單詞的位置。我有街道名稱的一部分，所以我可以對之前獲取的行進行比較，或者我將更改查詢以使街道名稱LIKE％streetName％。
我猜數據庫有一個塊的房子的開始號碼和結束號碼。我會檢查那條街，看看提供的街道號是否在那條街上。 現在，您將知道要顯示的正確數據，並且可以在不同的表格中查找哪個名稱與該門牌號碼相關聯。我不知道你爲什麼要比較它。如果您想查找地址未提供的人，則僅用於名稱比較。你可以在這裏查看比較字符串的方法Similar String algorithm
如果你可以可靠地找出每個地址的一般結構（也許根據其他答案中的建議），最好的辦法是通過USPS認證的（含義：結果可靠，準確，並符合聯邦標準）地址驗證服務。
@RyanDelucchi，它是一個有趣的問題，但只有一次，你已經解決了它。因此，@SteveBering，我會建議您提交您的聯繫人列表a list processing service，根據美國郵政的指導方針，將根據地址標記重複。
由於我在地址驗證領域工作，我會建議SmartyStreets（我工作），因爲它會爲您的特定需求提供最大價值 - 但是，有幾個CASS認證的供應商基本上可以做類似的事情。
我已經使用地址規範化，Metaphone和Levenshtein距離的組合解決了這個問題。您需要將名稱與地址分開，因爲它們具有不同的特徵。以下是您需要執行的步驟：
1）使用（郵政編碼的前六個字符）縮小您的匹配列表。基本上你需要計算兩個琴絃的Levenshtein距離，並選擇最長距離爲1或2的琴絃。如果您確實需要加快搜索速度，您可以預先計算郵政編碼表及其「Levenshtein鄰居」表。
http://en.wikipedia.org/wiki/Levenshtein_distance
2）轉換所有地址縮寫使用從USPS官方前綴和後綴縮寫表的標準格式。這將有助於確保您的結果，爲下一步更均勻：
https://www.usps.com/send/official-abbreviations.htm
3）轉換地址使用Methaphone算法的短代碼。這將消除最常見的拼寫錯誤。只要確保您的實現可以消除所有非單詞字符，通過數字完整和處理多個字（確保每個字由一個空格隔開）：
http://en.wikipedia.org/wiki/Metaphone
4）一旦你的Methaphone結果比較使用Levenshtein距離的地址字符串。通過將結果除以較長字符串中的字符數來計算更改分數的百分比。
5）重複步驟3和4，但現在使用名稱而不是地址。
6）使用以下公式計算每個條目的分數：（地址權重*地址分數）+（名稱權重*名稱分數）。根據什麼更重要選擇你的權重。我以.9開頭的地址（因爲地址更具體）和.1的名稱，但權重可能取決於您的應用程序。選擇分數最低的條目。如果得分太高（超過.15，你可能會聲明沒有匹配）。
USPS API確實可以工作到一定程度，因爲它是免費的，但缺乏重要功能，可能不會返回所有需要的信息來查找重複的聯繫人。我認爲，CASS認證的USPS服務供應商（如SmartyStreets;請參閱我的補充答案）將提供更多SteveBering的需求。 – Matt 2012-01-05 19:30:43