我有一个大城市的数据库，它是从许多不同的来源编译的。我试图找到一种轻松找到基于城市名称的重复的方法。天真的答案是使用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