1

我正在阅读关于 2 个字符串之间的编辑距离的问题。
它可以通过使用编辑距离公式的动态规划来解决。我无法理解的是它的用处。首先，这与知道 2 个字符串的最长公共子序列有何不同？
如果想法是选择一个具有最小编辑距离的字符串，您不妨在字符串中使用最大 LCS。对吗？
此外，当我们实际编写代码来进行替换时，代码将类似于以下内容： 

if(a.length == b.length){  
   for(int i = 0;i < a.length;i++){  
          a[i] = b[i];  
   }  
}  
else{   
    a = new char[b.length];  
    for(int i = 0;i < a.length;i++){  
          a[i] = b[i];  
    }    
}

我的意思是替换字符。进行分配和检查字符是否相同之间有什么区别，如果不是，那么只有在运行时进行分配？两者都不是恒定时间操作吗？
我对这个问题有什么误解？

4

2 回答 2

3

如果在编辑中不允许替换（或者如果替换的成本是插入或删除的两倍），则编辑距离和 LCS 通过一个简单的公式相关联：

ed(x,y) = x.length + y.length - 2*lcs(x,y).length

如果替代是一个单独的单位成本操作，那么 ED 可能会小于这个值。这在实践中很重要，因为我们想要一种方法来创建更短的差异文件。不仅是渐近地限制在一个常数因子上，而且实际上是最小的可能因子。

在这里编辑较短的差异文件可能不是问题，如果我们不允许替换，它们不会显着缩短。还有更多有趣的应用程序，例如拼写检查器中的排名更正建议（这是基于下面@nhahtdh 的评论）。

于 2013-01-27T18:02:48.670 回答
0

编辑距离与 LCS 完全不同。编辑距离是将一个字符串转换为另一个字符串所需的最少编辑操作数。一个非常流行的例子是 具有编辑操作的莱文斯坦距离：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

所有这些操作 a 的成本为1。

放有许多其他可能的操作和成本函数。例如，您还可以允许以下操作：交换两个相邻的字符。

例如，它用于比对 DNA 序列（或蛋白质序列）。

如果字符串的长度为 n 和 m，则复杂度为：
时间：O(n*m)
空间：O(min(n,m))

对于复杂的成本函数，Can 变得更糟。

于 2013-01-27T17:50:05.090 回答