18

両方とも非常に大きい（100GBなど）2つのファイルAとBを保存する必要があります。ただし、BはAと大部分が類似している可能性が高いため、Aとdiff（A、B）を格納できます。この問題には2つの興味深い側面があります。

  1. ファイルはメモリ内にあるため、私が知っているdiffライブラリで分析するには大きすぎます
  2. 私は実際にはdiffを必要としません-diffは人間が読むことを目的としているため、通常は挿入、編集、削除があります。より少ない情報で逃げることができます：「新しいバイト範囲」と「任意のオフセットから古いファイルからバイトをコピーする」だけが必要です。

私は現在、これらの条件下でAからBへのデルタを計算する方法に迷っています。誰かがこれのためのアルゴリズムを知っていますか？

繰り返しになりますが、問題は単純です。ファイルAとBの両方が非常に類似しているという事実を考慮して、ファイルAとBを可能な限り少ないバイト数で格納できるアルゴリズムを記述します。

追加情報：大きな部品は同一である可能性がありますが、オフセットが異なり、故障している可能性があります。最後の事実は、従来の差分があまり節約できない理由です。

4

5 に答える 5

16

を使用できますrdiff。これは、大きなファイルで非常にうまく機能します。ここでは、2つの大きなファイルの差分を作成しAますB。

  1. たとえば、1つのファイルの署名を作成します

    rdiff signature A sig.txt

  2. 生成された署名ファイルsig.txtと他の大きなファイルを使用して、デルタを作成します。

    rdiff delta sig.txt B delta

  3. との両方がある場合にdeltaファイルを再作成するために必要なすべての情報が含まれるようになりました。Bを再作成するには、BAdelta

    rdiff patch A delta B

Ubuntuでは、実行sudo apt-get install rdiffしてインストールします。それは非常に高速で、PCで毎秒約40MBを取得します。8GBのファイルで試したところ、rsyncで使用されるメモリは約1MBでした。

于 2010-01-09T15:37:09.170 に答える
14

RSYNCアルゴリズムを見てください。これは、デルタを効率的にコピーできるように、これを正確に実行するように設計されているためです。そして、私が思い出したように、アルゴリズムはかなりよく文書化されています。

于 2010-01-08T19:49:44.737 に答える
8

それはまさに「データ重複排除」として知られている問題です。最も一般的に使用されるアプローチは次のとおりです。

  • ブロック単位でファイルを読み取ります。
    • いわゆる「チャンク」のデータを分割します。最も頻繁に使用されるアプローチは、「Rabinsフィンガープリント方式を使用したコンテンツ定義チャンキング」（コード）と呼ばれます。このチャンク化アプローチを使用すると、静的サイズのチャンクを使用するよりも、ほとんどのデータセットで重複排除が改善されます（例：ここに表示）。
    • SHA-256などの暗号化フィンガープリント方式を使用してチャンクをフィンガープリントします。
    • フィンガープリントをインデックスに保存し、フィンガープリントがすでにわかっている場合は各チャンクを検索します。フィンガープリントがわかっている場合は、チャンクをもう一度保存する必要はありません。指紋がわからない場合にのみ、データを保存する必要があります。

このようなデータ重複排除アルゴリズムは、たとえばxdeltaほど正確ではありませんが、大規模なデータセットに対してより高速でスケーラブルです。チャンク化とフィンガープリントは、コアあたり約50 MB /秒で実行されます（Java）。インデックスサイズは、冗長性、チャンクサイズ、およびデータサイズによって異なります。200 GBの場合、16KBなどのチャンクサイズのメモリに収まる必要があります。

BentleysとMciloysの圧縮アプローチは非常に似ていますが（たとえば、GoogleのBigTableで使用されています）、圧縮技術を使用したすぐに使用できるコマンドラインツールを認識していません。

「fs-c」オープンソースプロジェクトには、必要なコードのほとんどが含まれています。ただし、fs-c自体は、メモリ内またはHadoopクラスターを使用して冗長性と分析ファイルのみを測定しようとします。

于 2010-01-08T20:11:14.130 に答える
6

1つの質問は、ファイルのレコードサイズはどれくらいかということです。つまり、オフセットをバイトごとに変更できるのか、それともファイルが1024Bブロックで構成されているのかということです。データがバイト指向であると仮定すると、次のように実行できます。

  1. ファイルAのサフィックス配列を作成します。この配列はファイルAへのすべてのインデックス値の並べ替えです。Aが2^37バイトの場合、インデックス配列は64ビット整数で表すのが最も簡単なので、すべてのバイト（ file）はインデックス配列の8バイトに対応するため、インデックス配列の長さは2^40バイトになります。たとえば、800GBです。たとえば、インデックス配列のサイズを小さくするために、1024番目の場所ごとにのみインデックスを作成することもできます。これにより、コピー可能なフラグメントの平均実行時間に応じて、パッキングの品質が低下します。

  2. 次に、ファイルBを貪欲にパックするために、オフセットo = 0で開始し、インデックス配列を使用して、「o」で始まるデータと一致するA内の最長の一致を見つけます。パックされたファイルにペアを出力します。これは、16バイトをエンコードしない場合に発生するため、実行が16バイト未満の場合、実際にはスペースが失われます。これは、ビットレベルのエンコードを使用し、ビットマーカーを使用して、分離されたバイト（マーカー+8ビット=9ビット）またはオフセット/長さのペア（マーカー+40ビット+40ビット=81）のどちらをエンコードするかをマークすることで簡単に修正できます。ビット）、言う。最長のフラグメントをoにパックした後、oをフラグメントの次のバイトに増やし、ファイルの終わりまで繰り返します。

接尾辞配列の作成と使用は簡単で、参照を簡単に見つけることができます。高速アプリケーションでは、代わりに接尾辞木または接尾辞試行を使用します。これらは操作がより複雑ですが、より高速な検索を提供します。あなたの場合、セカンダリストレージにアレイを配置し、パッキングフェーズの実行速度が問題にならない場合は、サフィックスアレイで十分です。

于 2010-01-08T20:02:00.017 に答える
1

パフォーマンス要件に応じて、フィンガープリントしたチャンクをサンプリングし、それらが一致したときにそれらを拡張することで回避できます。そうすれば、大きなファイル全体に対してチェックサムを実行する必要がありません。

任意のバイトアラインメントが必要で、パフォーマンスを本当に気にする場合は、simhash アルゴリズムを調べ、それを使用して、類似しているがアラインメントされていないブロックを見つけます。

于 2010-01-08T20:28:31.710 に答える