对于两个字符串，a和b：

1. Levenshtein 距离：将a转换为b所需的最小插入、删除和符号替换次数。
2. Damerau Levenstein：与 Levenstein 距离类似，但您也可以使用换位（交换相邻符号）。
3. 最佳字符串对齐距离：与 Damerau Levenstein 类似，但不允许对同一子字符串应用多个转换（例如，首先转置两个符号，然后在它们之间插入第三个）。

距离都可以使用动态规划来计算。

在我看来，维基百科页面解释得很好。

如果您对书籍感兴趣，可以尝试 Gusfield 的“字符串、树和序列的算法：计算机科学和计算生物学”（以及您的在线书店在搜索上述内容后可能会推荐给您的其他书籍）。

我假设您了解算法背后的一般目的。即计算关于转换字符串 A 以使其等于字符串 B 所需的“编辑”次数的“距离”。此算法（通常）受其在评估时可以处理的编辑“类型”的约束。

Levenshtein 计算距离时考虑了三种可能的方式，即单个字符的插入、删除或替换。维基百科文章涵盖的细节超出了此处尝试的意义，https://en.wikipedia.org/wiki/Levenshtein_distance。

Damerau-Levenshtein 变体增加了第四种方法，即考虑两个相邻字符的换位的能力，作为一个可能的步骤。同样，维基百科的覆盖范围很广，并且与其他方法相比，https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance。

Optimal String Alignment 添加了类似的第四种方式。虽然它很相似，但它与上面的“真正的” Damerau-Levenshtein 算法不同。上面的深度学习文章中介绍了 OSA。

试图简而言之，算法在遍历两个字符串时根据比较编辑成本的 3/4 方法在字符相交处保持一个最小成本矩阵。

检查上面 Levenshtein 文章中的两个示例矩阵，以了解矩阵是如何形成的。

这是一篇解释它的文章：https ://people.cs.pitt.edu/~kirk/cs1501/Pruhs/Spring2006/assignments/editdistance/Levenshtein%20Distance.htm ，

一般还有第三篇关于“编辑距离”的文章：https ://en.wikipedia.org/wiki/Edit_distance

除了这些文章，你可以搜索互联网，因为那里有很多信息。最重要的是不要淹没在行话中。算法实际上很简单（即优雅），有时会让人想太多。