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

我正在寻找一个需要2个字符串的算法,它会给我一个"相似因子".

基本上,我将有一个可能拼写错误,输入字母等的输入,我必须在我可能的值列表中找到最接近的匹配项.

这不适用于在数据库中搜索.我将有一个500个左右的字符串匹配的内存列表,全部在30个字符以下,所以它可能相对较慢.

我知道这存在,我以前见过,但我不记得它的名字.

编辑:感谢指出Levenshtein和汉明.现在,我应该实施哪一个？它们基本上测量不同的东西,两者都可以用于我想要的东西,但我不确定哪一个更合适.

我已经阅读了算法,汉明似乎显然更快.既然都不会检测到两个被转置的角色(即乔丹和乔丹),我相信这将是一个常见的错误,这对我想要的更准确？有人可以告诉我一些关于权衡的事吗？

好的,所以标准算法是:

1)汉明距离 仅适用于相同长度的琴弦,但非常有效.基本上它只是计算不同字符的数量.对自然语言文本的模糊搜索没有用.

2)Levenstein距离.Levenstein距离根据将一个弦转换为另一个弦所需的"操作"的数量来测量距离.这些操作包括插入,删除和替换.计算Levenstein距离的标准方法是使用动态规划.

3)广义Levenstein /(Damerau-Levenshtein距离) 该距离还考虑了单词中字符的转置,并且可能是最适合手动输入文本的模糊匹配的编辑距离.计算距离的算法比Levenstein距离更复杂(检测换位并不容易).最常见的实现是对bitap算法的修改(如grep).

通常,您可能希望考虑在基于kd树的某种最近邻搜索中实现的第三个选项的实现