我有一個大城市的數據庫，它是從許多不同的來源編譯的。我試圖找到一種輕鬆找到基於城市名稱的重複的方法。天真的答案是使用levenshtein距離。然而，隨着城市的問題在於，他們往往有前綴和後綴是共同的國家，他們是在前綴/後綴替代Levenshtein距離
例如：
布勒維爾與Boscherville
這幾乎肯定是不同的城市。然而，因爲它們都以「ville」結尾（並且都以「Bo」開始），所以它們具有相當小的Levenstein距離。
* 我正在尋找一種字符串距離算法，該算法考慮到字符的位置，以便通過在字中間加權字母比單詞末尾的字母更高來最小化前綴和後綴的影響。 *
我可以自己寫一些東西，但我很難相信沒有人發佈過適合的算法。
一個非常簡單的方法就是在進行距離計算之前刪除通用的前綴和後綴。結果字符串之間的絕對距離將與完整字符串相同，但考慮到較短的長度時，距離看起來要大得多。
還請記住，一般甚至greilis錯誤拼寫獲得第一個字母的權利。這是極有可能的話，那Cowville和Bowville是不同的城市，即使他們L.距離只有1
你可以讓你的工作更輕鬆通過，至少在第一，不做距離計算如果兩個單詞以不同的字母開始。他們可能會有所不同。首先集中刪除以相同字母開頭的單詞的重複。如果在此之後，您仍然有大量潛在的重複項，則可以優化距離閾值以更仔細地檢查以不同字母開頭的單詞。
關於第一個字母的很好的一點。我最終刪除了單詞末尾的常見字符，長度縮短了一半。對於多詞城市（例如洛杉磯vs洛斯加託斯），我在比較之前首先刪除了相同的字符串（所以我比較了洛杉磯和加託斯） – scottmrogowski
這與自然語言編程中的stemming類似。
在該字段中，詞的詞幹在執行進一步分析之前被發現，例如，
run => run
running => run
runs => run
（當然之類的東西ran不幹到run。對於一個可以使用lemmatizer。但是，我離題...）。儘管在NLP中詞幹分析並不完美，但它的工作非常出色。
就你而言，在應用Levenstein之前，使用特定於城市名稱的規則來阻止城市行之有效。我並沒有意識到城市的stemmer實現，但規則似乎表面上相當簡單。
您可以從前綴列表和後綴列表（包括任何常見變體/拼寫錯誤拼寫）開始，只需在檢查Levenstein距離之前刪除這樣的前綴/後綴。
在附註中，如果您有其他地址信息（例如街道地址或郵政編碼），則會爲許多國家/地區提供地址標準化軟件，這些軟件將根據地址特定的算法找到最佳匹配。
我幾乎將它作爲http://stackoverflow.com/questions/10425238/modifying-levenshtein-distance-for-positional-bias的副本關閉，但那個人有一個艱難的答案來工作...... – Wrikken