10

重複の可能性:
C++ からファイルを比較する方法はありますか?

diff とパッチを適用したい長いテキスト文字列があります。文字列 a と b が与えられます。

string a = ...;
string b = ...;

string a_diff_b = create_patch(a,b);
string a2 = apply_patch(a_diff_b, b);

assert(a == a2);

人間が読める場合a_diff_b、それはボーナスになります。

これを実装する 1 つの方法は、 を使用しておよびシェル コマンドsystem(3)を呼び出し、それらに文字列をパイプすることです。別の方法は、関数を自分で実装することです (各行をアトミックに処理し、標準の編集距離 n^3 アルゴリズムをバックトラッキングで行ごとに使用することを考えていました)。diffpatchdiffutils

インプロセスでジョブを実行する優れた Linux C または C++ ライブラリを誰かが知っているかどうか疑問に思っていましたか?

4

3 に答える 3

9

MyersDiffアルゴリズムの実装をグーグルで検索できます。（「O（ND）差分アルゴリズムとそのバリエーション」）または「最長共通部分列」問題を解決するライブラリ。

私の知る限り、C++でのdiff/ patchの状況は良くありません-いくつかのライブラリ（diff match patch、libmbaを含む）がありますが、私の経験によれば、それらは文書化がやや不十分であるか、外部依存関係が重いです（差分一致パッチにはQt4が必要です）、不要なタイプに特化している（たとえば、Unicodeが必要な場合はstd :: string）、十分に汎用的でない、またはメモリが非常に多い汎用アルゴリズムを使用する要件（（M + N）^ 2、ここでMとNは入力シーケンスの長さです）。

Myersアルゴリズム（（N + M）メモリ要件）を自分で実装することもできますが、問題の解決策を理解するのは非常に困難です。ドキュメントを読んで少なくとも1週間は無駄になると予想されます。マイヤーズアルゴリズムの人間が読める形式の説明は、こちらから入手できます。

于 2012-11-18T20:42:52.413 に答える
8

私は信じている

https://github.com/cubicdaiya/dtl/wiki/Tutorial

必要なものがあるかもしれません

于 2012-11-18T10:13:08.770 に答える
3

http://code.google.com/p/google-diff-match-patch/

Diff Match ライブラリと Patch ライブラリは、プレーン テキストの同期に必要な操作を実行するための堅牢なアルゴリズムを提供します。

現在、Java、JavaScript、Dart、C++、C#、Objective C、Lua、Python で利用できます。言語に関係なく、各ライブラリは同じ API と同じ機能を備えています。すべてのバージョンには、包括的なテスト ハーネスも含まれています。

于 2012-11-18T20:25:41.247 に答える