C# でのバイナリ パッチ生成アルゴリズムの実装を持っている、または知っている人はいますか?
基本的に、2 つのファイル ( oldとnewで指定) を比較し、古いファイルをアップグレードして新しいファイルと同じ内容にするために使用できるパッチ ファイルを作成します。
実装は比較的高速で、巨大なファイルを処理する必要があります。O(n) または O(logn) ランタイムを示す必要があります。
私自身のアルゴリズムは、お粗末 (高速だが巨大なパッチを生成する) または遅い (小さなパッチを生成するが O(n^2) ランタイム) 傾向があります。
実装のためのアドバイスや指針があればいいでしょう。
具体的には、この実装は、1 つのマスター サーバーを持つさまざまな大きなデータ ファイルに対してサーバーの同期を維持するために使用されます。マスター サーバーのデータファイルが変更されると、いくつかのオフサイト サーバーも更新する必要があります。
私が作成した最も単純なアルゴリズムは、メモリに保持できるファイルに対してのみ機能します。次のとおりです。
- 古いファイルから最初の 4 バイトを取得し、これをキーと呼びます
- これらのバイトを辞書に追加します。ここで、key -> position、positionは、これらの 4 バイトを取得した位置であり、最初は 0 です
- これらの 4 バイトの最初をスキップし、別の 4 バイト (3 重複、1 1) を取得し、同じ方法で辞書に追加します。
- 古いファイルのすべての 4 バイト ブロックに対して、手順 1 ～ 3 を繰り返します。
- 新しいファイルの先頭から4 バイトを取得し、辞書で調べます。
- 見つかった場合は、2 つのファイルのバイトを比較して、複数ある場合は最長の一致を見つけます。
- 古いファイルでその場所への参照をエンコードし、新しいファイルで一致したブロックをスキップします
- 見つからない場合は、新しいファイルから 1 バイトをエンコードし、スキップします
- 新しいファイルの残りの部分について、手順 5 ～ 8 を繰り返します。
これは、ウィンドウ処理を行わない圧縮に似ているため、大量のメモリを使用します。ただし、コード出力を最小限に抑えようとする限り、かなり高速で、非常に小さなパッチが生成されます。
よりメモリ効率の良いアルゴリズムはウィンドウ処理を使用しますが、はるかに大きなパッチ ファイルを生成します。
上記のアルゴリズムには、この投稿では省略したニュアンスが他にもありますが、必要に応じて詳細を投稿できます。ただし、まったく別のアルゴリズムが必要であると感じているため、上記のアルゴリズムを改善しても、おそらく十分ではありません。
編集＃1：上記のアルゴリズムのより詳細な説明は次のとおりです。
まず、2 つのファイルを結合して、1 つの大きなファイルを作成します。2 つのファイル間のカットポイントを覚えておいてください。
次に、4 バイトを取得し、その位置をファイル全体のすべてのディクショナリ ステップに追加します。
3 番目に、新しいファイルの開始位置から、既存の 4 バイトの組み合わせを探してループを実行し、最長の一致を見つけます。古いファイルの位置、または新しいファイルの現在の位置より前の位置のみを考慮するようにしてください。これにより、パッチの適用中に古いファイルと新しいファイルの両方でマテリアルを再利用できます。
編集＃2：上記のアルゴリズムのソースコード
証明書に問題があるという警告が表示される場合があります。それを解決する方法がわからないので、当面は証明書を受け入れます。
ソースは、ライブラリの残りの部分から他の多くの型を使用しているため、必要なのはファイルだけではありませんが、それがアルゴリズムの実装です。
@lomaxx、xdeltaと呼ばれるsubversionで使用されるアルゴリズムの優れたドキュメントを見つけようとしましたが、アルゴリズムの仕組みをまだ知らない限り、見つけたドキュメントは私が知る必要があることを教えてくれません。
それとも、私は単に密集している... :)
いただいたサイトのアルゴリズムをざっと見てみましたが、残念ながら使えません。バイナリ差分ファイルからのコメントは次のように述べています。
最適な差のセットを見つけるには、入力サイズに対して二次時間が必要になるため、すぐに使用できなくなります。
ただし、私のニーズは最適ではないため、より実用的なソリューションを探しています。
答えてくれてありがとう、必要に応じて彼のユーティリティにブックマークを追加しました。
編集＃1：注意してください、私は彼のコードを見て、いくつかのアイデアを見つけることができるかどうかを確認します。また、後で質問をメールで送信しますが、彼が参照している本を読みましたが、解決策は良いです最適なソリューションを見つけるには、時間がかかるため実用的ではありません。
編集＃2：私は間違いなくpython xdeltaの実装を追い詰めます。