1

効率的に対処する必要がある以下の状況がありますが、

クライアントデバイスからサーバーへのファイル同期を行っています。サーバーの問題が原因で、あるデバイスのファイルがサーバーから別のデバイスにフェッチされない場合があります。サーバー内のすべてのファイルが、別のスレッドを使用してすべてのクライアントデバイスに同期されていることを確認する必要があります。開発にはC++を使用し、クライアントからサーバーへの通信にはlibcurlを使用しています。

ここのクライアントデバイスには、SQLiteデータベースにダウンロードされたファイルのエントリがあります。同様にサーバーでも、サーバーデータベース（MySQL）でも同様の更新があります。クライアントデバイスから利用可能なすべてのファイルを一覧表示してサーバーに送信し、サーバーデータベースから取得した一覧と比較して、欠落しているファイルを見つける必要があります。

100万個のファイルリスト（フルパスのファイル名）の場合、サイズは約85MBであると概算しました。圧縮すると、最大10MBのサイズになります。したがって、このファイルリスト全体を（圧縮後でも）クライアントからサーバーに転送することはお勧めできません。私はこれのために以下のようにブルームフィルターを実装することを計画しました、

  1. クライアント側のデータベースからファイルリストを取得し、それらをブルームフィルターデータ構造に変換します。
  2. ブルームデータ構造のみをクライアントからサーバーに転送するだけです。
  3. サーバー側のデータベースからファイルリストを取得し、クライアントから受け取ったBloomデータ構造と比較して、不足しているファイルを見つけます。

クライアントから開始された上記のプロセスは、1時間程度ごとなど、定期的にスレッドで処理する必要があることに注意してください。

ブルームフィルターの問題は、たとえそれが非常に低くても、誤検知率です。1つのファイルでも見逃したくない。これを行う他のより良い方法はありますか？

4

2 に答える 2

2

お気づきのように、これはブルーム フィルターが適切な問題ではありません。ブルーム フィルターでは、ヒットを取得したら、信頼できるソースをチェックして、偽陽性と真陽性を区別する必要があります。これらは、フィルターに対するほとんどのクエリが否定的な結果をもたらすと予想される状況で役立ちます。あなたの場合とは逆です。

あなたができることは、それぞれの側に知られているすべてのファイル名のメモリに部分的なプレフィックス ツリーを構築させることです。それは完全なプレフィックス ツリーではありません。ノードの下のファイル名の数が特定のレベルを下回ったら、そのノードにそれらのファイル名の完全なリストを含めるだけです。次に、ツリーのルートから始まる再帰アルゴリズムを使用して、これらのプレフィックス ツリーを同期します。

  1. 各サイドは、現在のノードの下に並べ替えられ、連結されたすべてのファイル名のハッシュを作成します。
  2. ハッシュが等しい場合、このノードとすべての子孫が同期されます - 戻ります。
  3. 子ノードがない場合は、この端末ノードでファイル名の (短い) リストを一方から他方に送信して、同期して返します。
  4. それ以外の場合は、子ノードを再帰的に同期して戻ります。

ハッシュは少なくとも 128 ビットである必要があり、ハッシュのファイル名を連結するときは、可逆的な方法で連結するようにしてください (つまり、ファイル名に表示できない文字で区切る\0か、それぞれの前に を付けます)。その長さ)。

于 2012-11-01T07:13:03.657 に答える
0

ファイル/パス名の圧縮では、一般的な (bz2) 圧縮よりも単独でもプレフィックスとサフィックスの圧縮の方がうまく機能することがわかりました。組み合わせると、ファイル名リストをさらに減らすことができます。

トリックは、エスケープ コード (例: <32) を使用して前の行に共通する文字の数を示し、次に一意の部分に通常の文字を使用し、最後に (オプションで) 文字列の末尾に共通する文字の数をエンコードすることです。

于 2012-11-01T07:22:00.693 に答える