寻找两个字符串的相似程度

Question

40

我正在寻找一种算法，可以获取两个字符串之间的“相似度因子”。

基本上，我的输入可能会有错别字，字母顺序颠倒等问题，而我必须在一组可能值中找到最接近的匹配项。

这不是用于在数据库中搜索。我将拥有一个内存中的字符串列表，其中包含约500个字符串进行匹配，所有字符串长度均小于30个字符，因此速度可以相对较慢。

我知道这种算法存在，以前见过，但我不能记起它的名字。

编辑：感谢指出Levenshtein和Hamming算法。

现在，应该选择哪一个来实现呢？它们基本上测量不同的东西，都可以用于我想要的目的，但我不确定哪一个更合适。

我已经阅读了有关算法的资料，Hamming算法看起来显然更快。由于两个字符换位（例如Jordan和Jodran）都无法检测出来，而我认为这可能是一个常见的错误，那么哪个算法对我想要的更准确？

有人能告诉我一些权衡取舍吗？

- Daniel Magliola

实际上，Hamming距离和Levenshtein距离都可以检测到置换，并且每个距离都会分配2的成本。这是Hamming距离将合理地捕捉到的少数典型错误之一 - 任何单个字符的插入或删除都会立即给您带来巨大的不相似度分数。使用Levenshtein距离。 - j_random_hacker

4个回答

4

- vartec

哼...好的...我应该使用哪个？如果我没记错，Soundex并不实用，因为它依赖于第一个字母相同，而且上次我使用它（在另一个项目中），我对它并不满意。例如，Levenshtein和Hamming之间有什么权衡？ - Daniel Magliola

汉明距离只能用于相同长度的字符串…… 莱文斯坦距离就像是汉明距离的一般化。 - tehvan

嗯，汉明距离更多用于理论目的。如果你想要纠正或忽略拼写错误，可以使用Levenstein算法。如果你想要纠正或忽略糟糕的拼写，可以使用metaphone算法。但请注意，Levenstein算法适用于任何语言，而metaphone算法仅适用于英语。 - vartec

Benoit，是的，我同意。我之前也使用过Soundex（我可以为我的记录预先计算它，并在其上进行快速SQL查询）。但在这种情况下，我需要更高的准确性和更少的速度。 - Daniel Magliola

Soundex 的一个优点是 MSSQL 内置支持它。 - Stefan

显示剩余3条评论

4

Damerau-Levenshtein距离与Levenshtein距离类似，但也包括两个字符的转置。维基百科页面（链接）包含了伪代码，应该很容易实现。

- Autoplectic

2

你正在寻找 Levenshtein距离。

- tehvan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Il-Bhima · Accepted Answer

好的，标准算法如下：

1）汉明距离仅适用于相同长度的字符串，但非常高效。基本上它只是简单地计算不同字符的数量，对于模糊搜索自然语言文本没有用。

2）莱文斯坦距离。莱文斯坦距离以“操作”的数量来衡量将一个字符串转换为另一个字符串所需的距离。这些操作包括插入、删除和替换。计算莱文斯坦距离的标准方法是使用动态规划。

3）广义莱文斯坦/(Damerau-Levenshtein 距离) 此距离还考虑了单词中字符的置换，并且可能是手动输入文本的模糊匹配最合适的编辑距离。计算距离的算法比莱文斯坦距离复杂一些（检测置换不容易）。大多数常见的实现都是修改了比特帕算法（像grep）。

一般来说，最好考虑实现第三个选项的某种k-d树最近邻搜索。