Levenshtein 距离是一种字符串度量，用于衡量两个序列之间的差异。 Wagner-Fischer算法是一种动态规划算法，计算两个字符串之间的编辑距离。
两者都使用矩阵，我看不出有什么区别？ 区别是回溯还是没有进一步的区别，一个是“文学”，另一个是编程？
此外，我只是在写一篇论文，我不确定如何划分它——我应该先解释 Levenshtein 距离，然后再解释 Wagner-Fisher 算法，还是两者合而为一？我在这里有点困惑。
最佳答案
您实际上在第一段中自己回答了问题。 在第二段中，您将它们混合了一点。
Levenshtein 距离是以 Vladimir Levenshtein 命名的编辑距离度量谁在 1965 年考虑过这个距离，与动态规划“矩阵”无关。和 Wagner–Fischer algorithm是一种动态规划算法，计算两个字符串之间的编辑距离。
但是，如果您需要的是通用计算，即计算两个随机输入字符串之间的编辑距离，则编辑距离通常使用动态规划来计算。但是，当您将一个字符串与字典进行比较时，编辑距离也可以用于拼写检查器。在这种情况下，使用通用计算通常会变慢，比如 Levenshtein Automaton。可以提供线性时间来获得所有拼写建议。顺便说一句，这也用于 Lucene since version 4 中的模糊搜索。 .
关于您的论文，我认为这取决于情况。如果它与实际的 Levenshtein 度量有关，那么我认为这就是你应该开始的地方，如果它与动态规划有关，你应该从 Wagner-Fischer 开始。无论如何，这就是我的两分钱。祝你论文顺利。
关于algorithm - Levenshtein距离和Wagner-Fischer算法有什么区别，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35908166/