我有一个从许多不同来源编译的大城市数据库。我正在尝试找到一种根据城市名称轻松发现重复项的方法。天真的答案是使用 levenshtein 距离。但是，城市的问题在于它们通常具有所在国家/地区通用的前缀和后缀。
例如：
布勒维尔与博舍维尔
这些几乎可以肯定是不同的城市。但是，因为它们都以“ville”结尾（并且都以“Bo”开头），所以它们的列文斯坦距离相当小。
*我正在寻找一种字符串距离算法，该算法考虑到字符的位置，通过将单词中间的字母权重于单词末尾的字母来最小化前缀和后缀的影响。*
我自己可能会写一些东西，但我很难相信还没有人发布过合适的算法。
这类似于自然语言编程中的词干提取。
在该字段中，在执行进一步分析之前找到一个词的词干，例如
run => run
running => run
runs => run
（当然，像ran不干的事情run。为此可以使用词形还原器。但我离题了......）。尽管词干提取在 NLP 中远非完美，但它的效果非常好。
在您的情况下，在应用 Levenstein 之前使用特定于城市名称的规则来阻止城市可能会很好。我不知道城市的词干分析器实施，但规则表面上似乎相当简单。
您可以从前缀列表和后缀列表（包括任何常见的变体/拼写错误）开始，然后在检查 Levenstein 距离之前简单地删除这样的前缀/后缀。
附带说明一下，如果您有其他地址信息（例如街道地址或邮政编码），则可以使用适用于许多国家/地区的地址规范化软件，该软件将根据特定地址的算法找到最佳匹配。
一个非常简单的方法是在进行距离计算之前删除公共前缀和后缀。结果字符串之间的绝对距离将与完整字符串相同，但是当考虑到较短的长度时，距离看起来要大得多。
还要记住，一般来说，即使是严重的拼写错误，第一个字母也是正确的。那么，这很可能Cowville是Bowville不同的城市，即使它们的 L. 距离只有 1。
如果两个单词以不同的字母开头，则至少在开始时不进行距离计算，您可以使您的工作更轻松。他们很可能是不同的。首先集中精力删除以相同字母开头的重复单词。如果在那之后，您仍然有大量潜在的重复项，您可以优化您的距离阈值，以更仔细地检查以不同字母开头的单词。