Levenshtein距离和Wagner-Fischer算法有什么区别？

Question

Levenshtein距离是一种用于衡量两个序列之间差异的字符串度量。Wagner-Fischer算法是一种动态规划算法，用于计算字符两个字符串之间的编辑距离。

两者都使用矩阵，我没有看到区别在哪里？区别在于回溯，还是因为一个是“文献”，另一个是编程而没有进一步的区别？

此外，我只是在写论文，不确定该如何划分。是先解释Levenshtein距离，然后再解释Wagner-Fisher算法，还是两者同时讲解？我有些困惑。

- Haifa Warda

Answer 1

实际上，在第一段你已经回答了这个问题。在第二段中，你稍微混淆了一些。

Levenshtein距离是一种编辑距离度量，以Vladimir Levenshtein的名字命名，他在1965年考虑了这种距离，与动态规划“矩阵”无关。而Wagner-Fischer算法是一种动态规划算法，用于计算两个字符字符串之间的编辑距离。

然而，如果您需要进行通用计算，即计算两个随机输入字符串之间的编辑距离，则通常使用动态规划来计算Levenshtein距离。但在拼写检查器中比较一个字符串与字典时，可以使用Levenshtein距离。在这种情况下，通常使用通用计算速度太慢，类似于Levenshtein自动机可以提供线性时间以获得所有拼写建议。顺便说一句，这也被用于自Lucene 4版起的模糊搜索中。

关于你的论文，我认为这取决于情况。如果它是关于实际Levenshtein度量，则我认为那就是你应该开始的地方，如果它是关于动态规划，则应该从Wagner-Fischer开始。不管怎样，这是我的意见。祝你的论文好运。

- gustf

Answer 2

事实上，它们密切相关，但并不是同一件事。Levenshtein距离是一个由数学公式定义的概念。然而，直接实现递归公式来计算Levenshtein距离将会非常缓慢。Wagner-Fischer是一种动态编程算法，可以高效地计算它。

- Aasmund Eldhuset