sco*_*ski 7 algorithm string-algorithm levenshtein-distance
我有一个大城市数据库,它是从许多不同来源编译而来的.我正试图找到一种方法,可以根据城市名称轻松发现重复项.天真的答案是使用levenshtein距离.然而,城市的问题在于它们通常具有前缀和后缀,这些前缀和后缀对于它们所在的国家而言是共同的.
例如:
Boulleville对阵Boscherville
这些几乎肯定是不同的城市.然而,因为它们都以"ville"结尾(并且都以"Bo"开头),所以它们具有相当小的Levenstein距离.
*我正在寻找一种字符串距离算法,该算法考虑到字符的位置,通过将单词中间的字母加权高于单词末尾的字母来最小化前缀和后缀的影响.*
我本可以自己写一些东西,但我觉得很难相信没有人发表过合适的算法.
一种非常简单的方法是在进行距离计算之前删除公共前缀和后缀。生成的字符串之间的绝对距离将与完整字符串相同，但是当考虑到较短的长度时，距离看起来要大得多。
还要记住，一般来说，即使是严重的拼写错误，第一个字母也是正确的。那么，Cowville和很可能Bowville是不同的城市，即使它们的 L. 距离仅为 1。
如果两个单词以不同的字母开头，则至少在开始时不进行距离计算，可以使您的工作变得更加轻松。他们很可能会有所不同。首先集中精力删除以相同字母开头的单词的重复项。如果之后，您仍然有大量潜在的重复项，您可以细化距离阈值，以更仔细地检查以不同字母开头的单词。