56

このdiffプログラムは、さまざまな形で、2 つのテキスト ファイルの違いを計算し、両方のファイル全体を表示するよりもコンパクトに表現するのにかなり優れています。挿入および削除された一連の行のチャンク (または場合によっては変更された行ですが、これは削除の後に挿入が続くことと同じです) として違いを示します。ソース管理システムでは、同じまたは非常に類似したプログラムまたはアルゴリズムを使用してpatch、同じファイルの 2 つのバージョン間の違いを表すために必要なストレージを最小限に抑えます。アルゴリズムについては、こちらとこちらで説明しています。

しかし、テキストのブロックがファイル内で移動されると、それは失敗します。

次の 2 つのファイルがあるa.txtとb.txtします (両方とも 6 行ではなく数百行あると想像してください)。

a.txt   b.txt
-----   -----
1       4
2       5
3       6
4       1
5       2
6       3

diff a.txt b.txtこれを示します：

$ diff a.txt b.txt 
1,3d0
< 1
< 2
< 3
6a4,6
> 1
> 2
> 3

a.txtからへの変更はb.txt、「最初の 3 行を最後に移動する」と表現できますが、移動したdiff行のチャンクの完全な内容を 2 回示しており、この大きな変更を非常に簡単に説明する機会を逃しています。

テキストのブロックを 1 回だけ表示することに注意してください。これdiff -eは、削除された行の内容が表示されないためです。

(a) 挿入と削除を表す の機能をdiff保持し、(b) コンテンツ全体を表示することなく移動したテキスト ブロックを効率的に表すアルゴリズムの変形はありますか?diff

4

8 に答える 8

24

アプリケーションではなくアルゴリズムを要求したので、WalterTichyによる「ブロック移動による文字列から文字列への修正問題」を見てください。他にもありますが、それはオリジナルなので、それを引用している論文を探してさらに見つけることができます。

この論文は、Paul Heckelの論文「ファイル間の違いを分離するための手法」（この質問に対するこの回答で言及されている）を引用し、そのアルゴリズムについて次のように述べています。

Heckel [3]は、LCS手法に関する同様の問題を指摘し、ブロックの動きを検出するための線形石灰アルゴリズムを提案しました。文字列に重複する記号がほとんどない場合、アルゴリズムは適切に実行されます。ただし、それ以外の場合、アルゴリズムの結果は良くありません。たとえば、2つの文字列aabbとbbaaが与えられた場合、Heckelのアルゴリズムは一般的なサブ文字列を検出できません。

于 2012-04-09T15:11:29.753 に答える
12

次のメソッドは、ブロックの移動を検出できます。

Paul Heckel:ファイル間の相違点を分離するための手法
Communications of the ACM 21(4):264 (1978)
http://doi.acm.org/10.1145/359460.359467 (アクセス制限あり)
Mirror: http://documents.scribd. com/docs/10ro9oowpo1h81pgh1as.pdf (オープンアクセス)

wikEd diffは、このアルゴリズムを実装して改良した無料の JavaScript diff ライブラリです。また、挿入、削除、移動されたブロック、元のブロックの位置が新しいテキスト バージョンに挿入されたテキスト出力をコンパイルするコードも含まれています。詳細については、プロジェクト ページまたは広範囲にコメントされたコードを参照してください。テストには、オンライン デモも使用できます。

于 2014-09-26T10:03:49.793 に答える
5

これはうまくいくかもしれないもののスケッチです。わかりやすくするために、差分の挿入/削除は今のところ無視してください。

これは、テキスト圧縮と同様に、最適なブロッキングを見つけ出すことで構成されているようです。2 つのファイルの共通部分文字列を見つけたいとします。1 つのオプションは、一般化されたサフィックス ツリーを構築し、反復的に最大の共通部分文字列を取得し、それを削除して、あるサイズ $s$ の部分文字列がなくなるまで繰り返すことです。これは、O(N^2) 時間 ( https://en.wikipedia.org/wiki/Longest_common_substring_problem#Suffix_tree )でサフィックス ツリーを使用して実行できます。他の部分文字列から文字シーケンスを取得することは、同じ数の文字を別の場所に追加することを意味するため、貪欲に最大値を取得することが (圧縮された文字の関数として) 最適であるように見えます。

各部分文字列は、そのブロックの記号に置き換えられ、一種の「辞書」として一度表示されます。

$ diff a.txt b.txt 
1,3d0
< $
6a4,6
> $

 $ = 1,2,3

ここで、diff のような動作を再導入する必要があります。単純な (おそらく最適ではない) 答えは、最初に diff アルゴリズムを実行し、元の diff で出力されないすべてのテキストを省略して、上記のアルゴリズムを実行することです。

于 2012-04-09T00:21:55.307 に答える
4

SemanticMerge, the "semantic scm" tool mentioned in this comment to one of the other answers, includes a "semantic diff" that handles moving a block of lines (for supported programming languages). I haven't found any details about the algorithm but it's possible the diff algorithm itself isn't particular interesting as it's relying on the output of a separate parsing of the programming language source code files themselves. Here's SemanticMerge's documentation on implementing an (external) language parser, which may shed some light on how its diffs work:

I tested it just now and its diff is fantastic. It's significantly better than the one I produced using the demo of the algorithm mentioned in this answer (and that diff was itself much better than what was produced by Git's default diff algorithm) and I suspect still better than one likely to be produced by the algorithm mentioned in this answer.

于 2017-01-12T18:04:13.750 に答える
4

当社のSmart Differencerツールは、同じプログラミング言語の 2 つのプログラムのソース テキストの違いを計算するときに、まさにこれを行います。相違点は、行/列番号まで正確なプログラム構造 (識別子、式、ステートメント、ブロック) に関して、および妥当な編集操作 (削除、挿入、移動、コピー [単なる「コピー」に対する OP の要求を超えて) に関して報告されます。 ]、ブロック内の名前変更識別子)。

SmartDifferencers は構造化されたアーティファクト (プログラミング言語など) を必要とするため、任意のテキストに対してこれを行うことはできません。(構造を「単なるテキスト行」と定義することはできましたが、標準の diff と比較して特に価値があるとは思いませんでした)。

于 2012-04-08T23:26:26.847 に答える
1

SIM_TEXTアルゴリズムに基づくこのオンライン ツールsimtexterも確認してください。それは強く最高のようです。

また、Javascript 実装または C / Java のソース コードを確認することもできます。

ここに画像の説明を入力

于 2020-04-10T18:32:43.703 に答える