我正在寻找一种算法，它接受 2 个字符串并返回一个“相似因子”。
基本上，我会有一个可能拼写错误、字母转置等的输入，我必须在我拥有的可能值列表中找到最接近的匹配项。
这不是用于在数据库中搜索。我将有一个包含 500 个左右字符串的内存列表来匹配，所有字符串都在 30 个字符以下，因此速度可能相对较慢。
我知道这个存在，我以前见过它，但我记不起它的名字了。
编辑:感谢您指出 Levenshtein 和 Hamming。 现在，我应该实现哪一个？它们基本上测量不同的东西，两者都可以用于我想要的，但我不确定哪个更合适。
我已经阅读了算法，Hamming 似乎明显更快。因为两者都不会检测到两个字符被调换(即 Jordan 和 Jodran)，我认为这是一个常见的错误，哪个更符合我的要求？ 有人可以告诉我一些权衡取舍吗？
最佳答案
好的，所以标准算法是:
1) Hamming distance 仅适用于相同长度的字符串，但非常有效。基本上它只是计算不同字符的数量。对自然语言文本的模糊搜索没有用。
2) Levenstein distance . Levenstein 距离根据将一个字符串转换为另一个字符串所需的“操作”次数来衡量距离。这些操作包括插入、删除和替换。计算列文斯坦距离的标准方法是使用动态规划。
3) Generalized Levenstein/(Damerau–Levenshtein distance) 该距离还考虑了单词中字符的换位，可能是最适合手动输入文本模糊匹配的编辑距离。计算距离的算法比 Levenstein 距离复杂一点(检测转置并不容易)。最常见的实现是对 bitap 的修改算法(如 grep)。
一般来说，您可能会考虑在某种基于 k-d 树的最近邻搜索中实现第三个选项的实现
关于algorithm - 查找两个字符串的相似程度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/577463/