查找两个字符串的相似程度
我正在寻找一种算法，该算法需要2个字符串，并且会给我一个“相似性因素”。
基本上，我将输入可能会拼写错误，将字母转置等的情况，并且必须在可能的值列表中找到最接近的匹配项。
这不是用于在数据库中搜索。我要在内存中列出500个左右的字符串，所有字符串都必须少于30个字符，因此它可能相对较慢。
我知道它的存在，我以前见过，但是我不记得它的名字了。
编辑：感谢您指出Levenshtein和汉明。现在，我应该实施哪一个？他们基本上测量了不同的东西，两者都可以用于我想要的东西，但是我不确定哪一个更合适。
我已经阅读了算法，显然汉明似乎更快。既然没有人会检测到两个换位的字符（例如Jordan和Jodran），我相信这是一个常见的错误，对于我想要的错误来说，这会更准确吗？有人可以告诉我一些权衡吗？
回答：
好的，所以标准算法是：
1）汉明距离
仅适用于相同长度的琴弦，但非常有效。基本上，它只计算不同字符的数量。对于自然语言文本的模糊搜索没有用。
2）Levenstein距离。Levenstein距离是根据将一个字符串转换为另一个字符串所需的“操作”次数来度量距离。这些操作包括插入，删除和替换。计算Levenstein距离的标准方法是使用动态规划。
3）广义Levenstein
/（Damerau–Levenshtein距离）
该距离还考虑了单词中字符的转置，并且可能是最适合手动输入文本的模糊匹配的编辑距离。计算距离的算法比Levenstein距离要复杂得多（检测换位并不容易）。最常见的实现是对bitap算法的修改（例如grep）。
通常，您可能需要考虑在基于kd树的某种最近邻居搜索中实现的第三个选项的实现
以上是 查找两个字符串的相似程度 的全部内容， 来源链接： utcz.com/qa/398055.html
