C# でのバイナリ パッチの生成
https://stackoverflow.com/questions/5831
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
C# でバイナリ パッチ生成アルゴリズムを実装した人、または知っている人はいますか?
基本的には、2 つのファイル (指定されたファイル) を比較します。 古い そして 新しい)、アップグレードに使用できるパッチ ファイルを作成します。 古い ファイルと同じ内容にする 新しい ファイル。
実装は比較的高速で、巨大なファイルを処理できる必要があります。O(n) または O(logn) のランタイムを示す必要があります。
私自身のアルゴリズムは、ひどい (速いが、巨大なパッチを生成する) か遅い (小さなパッチを生成するが、実行時間が O(n^2) である) 傾向があります。
アドバイスや実装のためのヒントがあれば幸いです。
具体的には、この実装は、1 つのマスター サーバーがあるさまざまな大規模なデータファイルに対してサーバーの同期を保つために使用されます。マスターサーバーのデータファイルが変更されると、いくつかのオフサイトサーバーも更新する必要があります。
私が作成した最も単純なアルゴリズムは、メモリ内に保持できるファイルに対してのみ機能します。次のとおりです。
- 最初の 4 バイトを取得します。 古い ファイル。これを 鍵
- それらのバイトを辞書に追加します。 キー -> 位置, 、 どこ 位置 はこれらの 4 バイトを取得した位置で、最初は 0
- これら 4 バイトの最初のバイトをスキップし、別の 4 バイト (3 つは重複、1 つは 1) を取得し、同じ方法で辞書に追加します。
- 内のすべての 4 バイト ブロックに対して手順 1 ～ 3 を繰り返します。 古い ファイル
- の始まりから 新しい ファイルを開き、4 バイトを取得して、辞書で調べてみます。
- 見つかった場合は、2 つのファイルのバイトを比較して、最長一致を見つけます (複数ある場合)。
- その場所への参照をエンコードします。 古い ファイル内で一致したブロックをスキップします。 新しい ファイル
- 見つからない場合は、そこから 1 バイトをエンコードします。 新しい ファイルを作成し、スキップします
- 残りの部分について手順 5 ～ 8 を繰り返します。 新しい ファイル
これはウィンドウ処理を行わない圧縮に似ているため、大量のメモリを使用します。ただし、コード出力を最小限に抑えようとする限り、これはかなり高速で、非常に小さなパッチを生成します。
メモリ効率の高いアルゴリズムではウィンドウ処理が使用されますが、生成されるパッチ ファイルははるかに大きくなります。
上記のアルゴリズムにはさらに細かい点がありますが、この投稿では省略しましたが、必要に応じて詳細を投稿できます。ただし、まったく別のアルゴリズムが必要であると感じているため、上記のアルゴリズムを改善しても十分な成果は得られないでしょう。
編集 #1:上記のアルゴリズムをさらに詳しく説明します。
まず、2 つのファイルを結合して、1 つの大きなファイルを作成します。2 つのファイル間のカットポイントを覚えておいてください。
第二に、それをしてください 4バイトを取得し、その位置を辞書に追加します ファイル全体のすべてのステップ。
第三に、どこから 新しい ファイルが開始されると、既存の 4 バイトの組み合わせを探すループを実行し、最長一致を見つけます。古いファイルからの位置のみを考慮するようにしてください。 新しいファイルの現在よりも前に. 。これにより、パッチ適用中に古いファイルと新しいファイルの両方でマテリアルを再利用できるようになります。
編集 #2: 上記アルゴリズムのソースコード
証明書に問題があるという警告が表示される場合があります。これを解決する方法がわからないので、当面は証明書を受け入れるだけです。
ソースはライブラリの残りの部分にある他の多くの型を使用しているため、そのファイルだけで十分というわけではありませんが、それがアルゴリズムの実装です。
@lomaxx、私は、Subversion で使用される xdelta と呼ばれるアルゴリズムに関する適切なドキュメントを見つけようとしましたが、アルゴリズムがどのように機能するかをすでに知っていない限り、私が見つけたドキュメントでは、私が知る必要があることはわかりません。
それとも私がただ濃いだけなのかもしれません...:)
教えていただいたサイトのアルゴリズムをちょっと覗いてみましたが、残念ながら使えませんでした。バイナリ diff ファイルのコメントには次のように書かれています。
最適な差分のセットを見つけるには、入力サイズに対して 2 次時間が必要となるため、すぐに使用できなくなります。
ただし、私のニーズは最適ではないため、より実用的なソリューションを探しています。
ただし、答えてくれてありがとう。必要に応じて彼のユーティリティにブックマークを追加しました。
編集 #1:注、私は彼のコードを見てアイデアが見つかるかどうかを確認するつもりです。また、後で彼に質問のメールを送りますが、私は彼が参照しているその本を読みました。その解決策は最適な解決策を見つけるのに適していますが、時間がかかるため、使用するのは現実的ではありません。
編集 #2:私は間違いなく Python xdelta 実装を追い詰めるつもりです。
解決
申し訳ありませんが、これ以上お手伝いできませんでした。私は、製品を配布するために生成した 600MB 以上の ISO ファイルで高品質の差分を生成するために何度も xdelta を使用しており、非常に優れたパフォーマンスを発揮するため、xdelta を引き続き検討します。
他のヒント
見たことがありますか VCDiff?これは、かなりアクティブであると思われる Misc ライブラリの一部です (最終リリース r259、2008 年 4 月 23 日)。使用したことはありませんが、言及する価値があると思いました。
必ずしも C# の分野ではなく、この分野で他の人が何をしているのかをチェックしてみる価値はあるかもしれません。
SVN にはバイナリ diff アルゴリズムもあり、簡単な検索では見つけられませんでしたが、Python での実装があることは知っています。独自のアルゴリズムをどこで改善すればよいかについてのアイデアが得られるかもしれません
インストールまたは配布が目的の場合、Windows インストーラー SDK の使用を検討しましたか?バイナリファイルにパッチを適用する機能があります。
http://msdn.microsoft.com/en-us/library/aa370578(VS.85).aspx
これは大まかなガイドラインですが、バイナリ パッチの作成に使用できる rsync アルゴリズムについては次のとおりです。
