algorithm - 替代 Levenshtein 距离的前缀/后缀

Question

我有一个从许多不同来源编译的大城市数据库。我正在尝试找到一种方法来根据城市名称轻松发现重复项。天真的答案是使用 levenshtein 距离。然而，城市的问题在于它们通常具有所在国家/地区通用的前缀和后缀。

例如:

bool 维尔与博舍维尔

这些几乎可以肯定是不同的城市。然而，因为它们都以“ville”结尾(并且都以“Bo”开头)，所以它们的 Levenstein 距离相当小。

*我正在寻找一种字符串距离算法，它考虑到字符的位置，通过对单词中间字母的权重高于单词末尾字母的权重来最小化前缀和后缀的影响. *

我或许可以自己写一些东西，但我很难相信还没有人发布合适的算法。

Answer 1

这类似于 stemming在自然语言编程中。

在该字段中，在执行进一步分析之前找到词干，例如

run => run
running => run
runs => run

(当然，ran 之类的东西并不是 run 的结果。为此可以使用词形还原器。但我离题了...)。尽管词干提取在 NLP 中远非完美，但它的效果非常好。

在您的情况下，在应用 Levenstein 之前使用特定于城市名称的规则来阻止城市可能会很有效。我不知道针对城市的词干分析器实现，但表面上看规则似乎相当简单。

您可以从前缀列表和后缀列表(包括任何常见的变体/拼写错误)开始，然后在检查 Levenstein 距离之前简单地删除这样的前缀/后缀。

附带说明一下，如果您有其他地址信息(例如街道地址或 zip /邮政编码)，许多国家/地区都有地址规范化软件，可以根据地址特定算法找到最佳匹配。