java - 无法理解字符串之间编辑距离的想法/用处

Question

我正在阅读有关 Edit Distance between 2 strings 的问题。
它可以使用编辑距离的公式通过动态规划来解决。我无法理解的是它的用处。 首先，这与知道 2 个字符串的最长公共(public)子序列有什么不同？
如果想法是选择一个具有最小编辑距离的字符串，您还不如使用字符串中的最大 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];  
    }    
}  

我的意思是只替换字符。进行赋值和检查字符是否相同之间有什么区别，如果不相同，则只在运行时进行赋值？不都是常数时间操作吗？
我对这个问题有什么误解？

Answer 1

如果在编辑中不允许替换(或者如果替换的代价是插入或删除的两倍)，编辑距离和 LCS 通过一个简单的公式联系起来:

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

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

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