7

DiffMergeのようなアプリケーションは、テキストファイルの違いをどのように検出し、チェック対象のファイルとは異なる行だけでなく、行が新しいかどうかをどのように判断しますか？

これは実装がかなり簡単なものですか？これを行うためのライブラリはすでにありますか？

4

4 に答える 4

5

これは、UNIXコマンドライン ツールdiffの基礎となった論文です。

于 2009-05-29T16:55:00.287 に答える
4

実際には非常に単純です。DIFF プログラム (ほとんどの場合)は、グラフ アルゴリズムを使用して解決できるLongest Common Sequenceに基づいています。

この Web ページでは、C# での実装例を示します。

于 2009-05-29T16:56:16.477 に答える
4

それは複雑な質問です。差分を実行するということは、2 つのファイル間の最小編集距離を見つけることを意味します。つまり、あるファイルを別のファイルに変換するために必要な変更の最小数です。これは、2 つのファイル間の行の最長共通サブシーケンスを見つけることと同じであり、これがさまざまな diff プログラムの基礎となっています。最も長い一般的な部分列の問題はよく知られており、Google で動的計画法の解決策を見つけることができるはずです。

動的計画法の問題は、それが O(n^2) であることです。したがって、大きなファイルでは非常に遅く、大きなバイナリ文字列には使用できません。diff プログラムを作成する上で難しいのは、適切なパフォーマンス (および適切な結果) が得られるように、問題のドメインに合わせてアルゴリズムを最適化することです。Hunt と McIlroy による論文「An Algorithm for Differential File Comparison」は、Unix diff ユーティリティの初期バージョンについて適切に説明しています。

于 2009-05-29T16:56:53.637 に答える
4

ライブラリがあります。ここに 1 つがあります: http://code.google.com/p/google-diff-match-patch/

StackOverflow は、差分に Beyond Compare を使用します。コマンドラインから Beyond Compare を呼び出すことで機能すると思います。

于 2009-05-29T17:01:22.540 に答える