テキスト差分アプリケーションはどのように機能しますか？

Question

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

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

Answer 1

ここでは、the paperは、UNIXコマンドラインツールdiffの基礎となっています。

Answer 2

実際はかなりシンプルです。ほとんどの場合、DIFFプログラムはLongest Common Sequenceに基づいており、これはグラフアルゴリズムを使用して解決することができます。

This web pageは、C＃で実装例を示します。

Answer 3

これは複雑な質問です。 diffを実行すると、2つのファイル間の最小編集距離を見つけることができます。つまり、あるファイルを別のファイルに変換するために必要な変更の最小回数です。これは、2つのファイルの間で最も長い共通部分列を見つけることに相当します。これは、さまざまなdiffプログラムの基礎となります。最長共通部分列問題はよく知られており、Googleで動的プログラミングソリューションを見つけることができるはずです。

ダイナミックプログラミングアプローチの問題は、それがO（n^2）だということです。したがって、大きなファイルでは非常に遅く、大きなバイナリ文字列では使用できません。 diffプログラムを書くことの難しい部分は、問題のあるドメインのアルゴリズムを最適化して、妥当なパフォーマンス（そして妥当な結果）を得ることです。 HuntとMcIlroyによる "Differential File Comparisonのためのアルゴリズム"という論文は、Unix diffユーティリティの初期のバージョンをよく説明しています。

Answer 4

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

StackOverflowは比較のためにBeyond Compareを使用します。私はコマンドラインからBeyond Compareを呼び出すことによって動作すると信じています。