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

Question

Levenshtein距离是用于测量两个序列之间差异的字符串度量.Wagner-Fischer算法是一种动态编程算法,用于计算两个字符串之间的编辑距离.

两者都使用矩阵,我没有看到差异？这种差异是回溯还是由于一个是"文学"而另一个是编程这一事实没有进一步的区别？

另外,我只是写一篇论文,我不知道如何划分它 - 我是否应首先首先解释Levenshtein距离,然后再解释Wagner-Fisher算法或两者兼而有之？我在这里有点困惑.

Answer 1

您实际上是在第一段中自己回答了这个问题.在第二段中,你将它们混合了一下.

Levenshtein距离是一个以Vladimir Levenshtein命名的编辑距离度量,他在1965年考虑了这个距离并且与动态编程"矩阵"无关.和瓦格纳-菲舍尔算法是计算字符的两个字符串之间的编辑距离的动态规划算法.

但是,Levenshtein距离通常使用动态编程计算,如果您需要的是通用计算,即计算两个随机输入字符串之间的编辑距离.但是,当您将一个字符串与字典进行比较时,Levenshtein距离也可用于拼写检查.在这种情况下,通常使用通用计算的速度较慢,而像Levenshtein Automaton这样的东西 可以提供线性时间来获取所有拼写建议.顺便说一下,自版本4以来,这也用于Lucene的模糊搜索.

关于你的论文,我认为这取决于你.如果它是关于实际的Levenshtein度量标准,那么我认为你应该从哪里开始,如果它是关于动态编程的,你应该从Wagner-Fischer开始.无论如何,这就是我的两分钱.并祝你好运.

Answer 2

的确，它们是密切相关的，但它们不是一回事。Levenshtein 距离是一个由数学公式定义的概念。然而，试图通过直接实现递归公式来计算 Levenshtein 距离将非常缓慢。Wagner-Fischer 是一种动态规划算法，可以有效地计算它。