3

2 つのバイトストリームの違いを伝えようとしています。パッチのバイト数を最小限に抑えたい。

(必ずしも差分の「変更」の数を最小限に抑えたいとは限りません。これは、レーベンシュタイン距離計算の最適なパッチが私に与えるものです。)

パッチは、理想的には、ソース バイトストリームと差分があれば、ターゲット バイトストリームを簡単に再構築できるような形式である必要があります。

これを行うための適切なアルゴリズムはありますか?


編集:記録のために、「スポット506で、次のバイトを挿入します...」という形式の変更を送信してみました。ここで、レーベンシュタイン距離アルゴリズムから変更リストを作成します。

私が抱えている問題は、レーベンシュタイン距離アルゴリズムが次のような多くの変更を与えることです。

at spot 506 substitute [some bytes1]
at spot 507 do nothing
at spot 508 substitute [some bytes2]
at spot 509 do nothing
at spot 510 substitute [some bytes3]
...

これは、lev 距離アルゴリズムが変更の数を最小限に抑えようとするためです。ただし、私の目的では、この命令セットは無駄です。アルゴリズムが次のように言った方が良いでしょう。

At spot 506 substitute [some bytes1, [byte at spot 507], some bytes2, [byte at spot 509], some bytes3, ...]

これらのタイプの変更を優先するためにレフ距離を変更する方法はおそらくいくつかありますが、少し難しいようです. 変更リストを取得した後に置換を合体することはできますが(それを試してみます)、削除/挿入も合体する可能性があり、それを正しく行う方法はあまり明白ではありません.

このための特別な目的のアルゴリズムがあるかどうか (または、誰かがすでにこれらのタイプの変更を優先するためにレフ距離の変更を行っているかどうか) を考えてみてください。

4

4 に答える 4

2

これは、アフィンギャップコストを使用したペアワイズアラインメントを使用して行うことができます。これには、それぞれ長さnおよびmの2つのストリングに対してO(nm)時間がかかります。

まず最初に、使用されるビットまたはバイトに関して、おそらく最小限のパッチを見つける方法はありません。これは、そのような方法があれば、それshortest_patch(x, y)を計算する関数を使用して、を使用して任意の文字列の最小の圧縮を見つけることができるためですsshortest_patch('', s)コルモゴロフの複雑さは、特定の文字列の可能な限り最短の圧縮は形式的に計算できないことを示しています。 。しかし、ここにあるように編集が空間にクラスター化される傾向がある場合は、通常のレーベンシュタイン距離アルゴリズムを使用して生成されたパッチよりも小さいパッチを見つけることが確かに可能です。

スクリプトを編集する

パッチは通常、CSでは「スクリプトの編集」と呼ばれます。xある文字列を別の文字列に変換するための最小限の(挿入数と削除数の観点から)編集スクリプトを見つけることは、等しい文字のすべてのペアが値0を持ち、等しくない文字のすべてのペアが値をy持つ最適なペアワイズアラインメントを見つけることと同じです。 -infであり、1つの文字列の文字が-ギャップ文字と整列するすべての位置の値は-1です。配置は簡単に視覚化できます。

st--ing    st-i-ng
stro-ng    str-ong

これらは、ストリングstingとの2つの最適な配置でありstrong、モデルではそれぞれコストが-3です。等しくない文字のペアに-infではなく値-1が指定されている場合、コストはレーベンシュタイン距離(挿入数、削除数、置換数)に等しいアラインメントが得られます。

st-ing    sti-ng
strong    strong

これらは、新しいモデルでの2つの最適な配置であり、それぞれのコストは-2です。

これらが編集スクリプトとどのように対応するかを確認するために、上の文字列を「元の」文字列と見なし、下の文字列を「ターゲット」文字列と見なすことができます。等しくない文字のペアを含む列は置換に対応-し、上の行にaを含む列は文字の挿入に対応し-、下の行にaを含む列は文字の削除に対応します。「命令」(C)opy、(D)elete、(I)nsert、および(S)ubstituteを使用して、アライメントから編集スクリプトを作成できます。各命令の後には、アラインメントから消費する列の数を示す数字が続きます。IおよびSの場合は、挿入または置換する対応する文字数が続きます。たとえば、前の2つの配置の編集スクリプトは次のとおりです。

C2, I1"r", S1"o", C2     and     C2, S1"r", I1"o", C2

バンチングの増加

mississippiここで、とのような文字列がある場合tip、2つの配置が見つかります

mississippi
------tip--

mississippi
t---i----p-

どちらも-9の同じスコアを持っています:両方とも同じ合計数の挿入、削除、および置換を必要とします。ただし、編集スクリプトをより簡潔に記述できるため、一番上のものを使用することをお勧めしますD6, S1"t", C2, D2。2番目の編集スクリプトはですS1"t", D3, C1, D4, C1, D1

アラインメントアルゴリズムが最初のアラインメントも「優先」するようにするために、ギャップコストを調整して、ギャップのブロックを開始すると、既存のギャップのブロックを継続するよりもコストがかかるようにすることができます。前の列にギャップが含まれていないときにギャップを含む列のコストが-1ではなく-2になるようにすると、効果的に実行しているのは、連続するギャップのブロックの数にペナルティを課すことです(隣接するギャップの各ブロックは明らかに最初の位置を持っています)。このモデルでは、2つの連続したギャップのブロックが含まれているため、上記の最初の配置のコストは-11になります。2番目の配置には、3つの連続したギャップのブロックが含まれているため、コストは-12になります。IOW、アルゴリズムは最初の配置を優先するようになりました。

このモデルは、ギャップコストgを含むすべての整列位置と、ギャップ列の隣接ブロックの最初の位置コストg + sであり、アフィンギャップコストモデルと呼ばれ、O(nm)アルゴリズムが後藤によって与えられました。 1982年:http://www.genome.ist.i.kyoto-u.ac.jp/~aln_user/archive/JMB82.pdf。ギャップオープンコストを増やすと、整列されたセグメントが一緒に束ねられます。経験的に正しく見え、十分に小さいアライメント(パッチに対応)が得られるまで、さまざまなコストパラメータで遊ぶことができます。

于 2012-12-09T07:47:00.043 に答える
1

この種の問題を解決するには、次の 2 つの方法があります。

1) (この場合はスクリプトを編集する) ための言語を確立しX、該当する文の長さを最小限に抑える方法を見つけます。また、

2) (文字列の違い) のある種の最小表現を計算Yし、それを最短形式で表現する方法を考えます。

Myers の論文は、特定の言語の場合、変更の最小セットを見つけることと、変更表現の最小の長さを見つけることは同じ問題であることを示しています。

明らかに、言語を変更するとその仮定が無効になる可能性があり、特定の変更を正しく適用するのが非常に複雑になる場合があります (たとえば、インデックスが素数でkPある次の文字を削除することを意味するプリミティブが言語に含まれているとします。特定の diff では、そのプリミティブを使用すると、kばかげた例だとは思いますが、言語から始めることの難しさを示しています。

そこで、挿入と削除を識別する最小限の変更リストから始めることを提案します。これを単純な方法で一連のコマンドに変換します。そのうちの 3 つは正確です。ここにはインデックスはありません。アイデアは、元の文字列の先頭にあるカーソルから始めて、コマンドを順番に実行するというものです。コマンドは次のとおりです。

=  Advance the cursor without altering the character it points to
Ic Insert the character `c` before the cursor.
D  Delete the character at the cursor.

正確に 3 つのコマンドがあると言いましたが、それは正確ではありません。アルファベットのサイズは実際にA+2どこにありますか。A

これにより、次のような文字列が生成される場合があります。

=========================IbIaInIaInIaDD=D=D============================

では、これを圧縮してみましょう。まず、ランレングス エンコード (RLE) を実行して、すべてのコマンドの前に繰り返し回数を追加し、末尾=の sを削除します。

27=1Ib1Ia1In1Ia1In1Ia2D1=1D1=1D

(事実上、RLE はインデックスを再作成しますが、インデックスは絶対的ではなく相対的です)。

最後に、zlib を使用して結果の文字列を圧縮します。ここではそれを行うつもりはありません。

27=1Ib1Ia1In||2D1=1D|
      ______+|  ____+
      ___<---+

(後方参照を表示しようとしています。あまり適切なアスキー アートではありません。申し訳ありません。)

Liv-Zempell は、予期しない繰り返しを見つけて最適化するのが得意です。実際、中間の RLE ステップを実行する代わりにそのまま使用することもできましたが、RLE が非常に効果的である場合は、ソースよりも RLE を LZ する方がよいことが経験からわかっています。ただし、アプリケーションにとってどちらが優れているかを確認するには、両方の方法を試してみる価値があります。

于 2012-12-08T20:45:27.223 に答える
0

非常に少数のバイトを使用するこれに対する一般的なアプローチは次のとおりです (ただし、必ずしも理論上の最適なバイト数ではありません)。

  1. 同じ長さになるまで、バイトを何らかの文字 (おそらくゼロ) で埋めます。
  2. 2 つのストリームを XOR します。これにより、バイトが同じ場合はどこでもゼロになり、それ以外の場合はゼロ以外のバイト ストリームが生成されます。
  3. おそらくLZWのような圧縮アルゴリズムを使用して、XORedストリームを圧縮します。

あなたが持っているパッチがファイルの小さな部分へのローカライズされた変更のセットであると仮定すると、ファイルの大部分がゼロになり、効率的に圧縮できるため、これは非常に短いパッチになります。

パッチを適用するには、XOR された文字列を解凍し、それをバイト ストリームと XOR してパッチを適用します。これは計算します

元の XOR (元の XOR 新) = (元の XOR 元) XOR 新 = 新

XOR は連想的で自己反転するためです。

お役に立てれば!

于 2012-12-08T18:41:13.007 に答える