我正在寻找一种算法，它需要 2 个字符串，并会给我一个“相似性因素”。
基本上，我将有一个可能拼写错误的输入，有字母转置等，我必须在我拥有的可能值列表中找到最接近的匹配项。
这不适用于在数据库中搜索。我将有一个包含 500 个左右的字符串的内存列表来匹配，所有字符串都在 30 个字符以下，所以它可能相对较慢。
我知道它存在，我以前见过它，但我不记得它的名字了。
编辑：感谢您指出 Levenshtein 和 Hamming。现在，我应该实施哪一个？它们基本上测量不同的东西，两者都可以用于我想要的东西，但我不确定哪个更合适。
我已经阅读了算法，汉明似乎明显更快。由于两者都不会检测到两个字符被转置（即 Jordan 和 Jodran），我认为这将是一个常见错误，这对于我想要的更准确？有人能告诉我一些关于权衡的事情吗？
好的，所以标准算法是：
1）汉明距离 只适用于相同长度的字符串，但非常有效。基本上它只是计算不同字符的数量。对于自然语言文本的模糊搜索无用。
2）莱文斯坦距离。Levenstein 距离根据将一个字符串转换为另一个字符串所需的“操作”数量来衡量距离。这些操作包括插入、删除和替换。计算 Levenstein 距离的标准方法是使用动态规划。
3）广义Levenstein/（Damerau-Levenshtein距离） 这个距离也考虑了单词中字符的换位，可能是最适合手动输入文本模糊匹配的编辑距离。计算距离的算法比 Levenstein 距离要复杂一些（检测转置并不容易）。最常见的实现是对bitap算法的修改（如 grep）。
一般来说，您可能需要考虑在基于 kd 树的某种最近邻搜索中实现的第三个选项的实现
Damerau -Levenshtein 距离类似于 Levenshtein 距离，但也包括两个字符的换位。维基百科页面（链接）包含应该很容易实现的伪代码。
您正在寻找Levenshtein 距离