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

編集で置換が許可されていない場合 (または、置換が挿入または削除の 2 倍のコストがかかる場合)、Edit Distance と LCS は単純な式で関連付けられます。

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

代替が個別の単価操作である場合、ED はそれよりも少なくなる可能性があります。より短い差分ファイルを作成する方法が必要なため、これは実際には重要です。漸近的に一定の係数に制限されるだけでなく、実際に可能な限り最小の係数に制限されます。

より短い差分ファイルを編集することはおそらくここでは問題ではありません。置換を許可しない場合、大幅に短くなることはありません。スペル チェッカーでのランキング修正提案など、さらに興味深いアプリケーションがあります (これは、以下の @nhahtdh によるコメントに基づいています)。

于 2013-01-27T18:02:48.670 に答える
0

編集距離は LCS とはかなり異なります。編集距離は、1 つの文字列を別の文字列に変換するために必要な編集操作の最小数です。非常に一般的な例は 、編集操作を持つレビンスタイン距離です。

  • 一文字入れる
  • 1文字削除
  • 1文字置換

このすべての操作は、コスト1でバイアスされています。

他にも多くの操作とコスト関数が可能です。たとえば、操作を許可することもできます: 2 つの隣接する文字を交換します。

これは、例えば、DNA 配列 (またはタンパク質配列) を整列させるために使用されます。

STring の長さが n と m の場合、複雑さは次のようになります:
時間: O(n*m)
空間: O(min(n,m))

複雑なコスト関数では悪化する可能性があります。

于 2013-01-27T17:50:05.090 に答える