前后缀的曼哈顿距离算法替代方案

Question

我有一个大型城市数据库，它是从许多不同的来源编译而成。我正在尝试找到一种简单的方法来基于城市名称轻松识别重复项。天真的答案可能是使用Levenshtein距离。然而，城市的问题在于它们经常具有与所在国家有关的前缀和后缀。

例如：

Boulleville vs. Boscherville 这几乎肯定是不同的城市。然而，因为它们都以"ville"结尾（并且都以"Bo"开头），所以它们的Levenstein距离相对较小。

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

我可能可以自己编写一些东西，但我很难相信还没有人发表过合适的算法。

- scottmrogowski

---

我几乎要把它关闭并视为 https://dev59.com/aWPVa4cB1Zd3GeqP5WZM 的重复，但那个问题的答案难以实现... - Wrikken

Answer 1

这类似于自然语言编程中的词干提取。

在该领域，先找到单词的词干，然后再进行进一步的分析。

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

当然像“ran”这样的词并不是“run”的词干。为此，可以使用词形还原器。尽管在自然语言处理中，词干提取远非完美，但它的效果非常好。

在您的情况下，使用特定于城市名称的规则对城市进行词干提取，然后再应用Levenstein算法可能效果很好。我不知道是否有适用于城市的词干提取器实现，但表面上看，这些规则似乎相当简单。

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

另外，如果您有其他地址信息（例如街道地址或邮政编码），许多国家都存在地址标准化软件，根据地址特定的算法找到最佳匹配。

- Eric J.

Answer 2

一个相对简单的方法是在计算距离之前仅删除公共前缀和后缀。结果字符串之间的绝对距离将与完整字符串一样，但考虑到较短长度时，距离看起来要大得多。

还要记住，通常情况下，即使是严重的拼写错误也会正确输入第一个字母。因此，Cowville 和 Bowville 可能是不同的城市，尽管它们的 L. 距离只有 1。

如果两个单词以不同的字母开头，可以通过不进行距离计算来更轻松地完成工作。它们可能是不同的。首先集中精力消除以相同字母开头的单词的重复项。如果在那之后仍然有大量潜在的重复项，则可以调整距离阈值以更仔细地检查以不同字母开头的单词。

- Jim Mischel

---

关于首字母的观点非常好。我最终删除了单词末尾共同的字符，直到较短单词长度的一半。对于多个单词组成的城市名称（例如洛杉矶 vs 洛斯加托斯），我首先删除相同的字符串后再进行比较（因此我将Angeles与Gatos进行比较）。 - scottmrogowski