6

この質問にさらに：ファイルのアイデンティティを決定するためのアルゴリズム

要約: ほとんどの場合に機能するファイル ID を判別するための安価なアルゴリズムを探しています。

私は先に進み、ファイルごとに「非常にユニークな」ハッシュを提供するアルゴリズムを実装しました。

私のアルゴリズムの仕組みは次のとおりです。

  • 特定のしきい値より小さいファイルの場合、ID ハッシュに完全なファイル コンテンツを使用します。

  • しきい値より大きいファイルの場合、X サイズのランダムな N 個のサンプルを取得します。

  • ハッシュ化されたデータにファイルサイズを含めます。(サイズが異なるすべてのファイルが異なるハッシュになることを意味します)

質問:

  • N と X にどの値を選択する必要がありますか (どのサイズのランダム サンプルをいくつ取得する必要がありますか?)、それぞれ 8K の 4 つのサンプルを使用しましたが、アルゴリズムを切り詰めることができません。サンプルの量を増やすと、アルゴリズムの速度が急速に低下することがわかりました (シークはかなりコストがかかるため)。

  • 数学の問題: このアルゴリズムが爆発するためには、ファイルがどれだけ変わらない必要があるか。(同じ長さの 2 つの異なるファイルは、同じハッシュを持つことになります)

  • 最適化の 1: 具体的な実装を最適化してスループットを向上させる方法はありますか (私のシステムでは 1 秒あたり約 100 ファイルを処理できるようです)。

  • この実装は正常に見えますか? これが失敗する実世界の例を考えてみてください。（私の焦点はメディアファイルです）

関連情報:

実装したアルゴリズム

ご協力いただきありがとうございます！

4

3 に答える 3

1

このような解決策は避けたいと思います。私は、2 つのメディア ファイルが同じサイズで、圧縮形式の対応する位置に同じデータがあるということはほとんどあり得ないことだと思っています。ただし、圧縮されていない画像や wave ファイルを処理する必要がある場合は、ローカルの小さな変更が検出されない可能性が高くなります。

したがって、ファイル全体を実際にハッシュする必要があると思います。これはコストがかかるように見えますが、すべてのファイルにアクセスできる場合 (たとえば、ファイル サーバーなどを構築する場合) はそうではないかもしれません。ハッシュを段階的に構築できます。

一意のファイル長を持つ新しいファイルが表示された場合は、ファイルの長さを保存してください。同じ長さの別のファイルが追加された場合は、両方のファイルのハッシュが異なるまでブロックごとに計算します。ファイルの長さ、ハッシュ、およびハッシュに含まれるファイルのブロック数を保存します。一致するファイルの長さとハッシュを検出し、まだファイル全体をハッシュしていない場合は、ブロックを追加してハッシュを拡張します。

パフォーマンスについてのいくつかの考え。小さなファイルの場合、ファイルの長さが等しい可能性は非常に高く、小さなファイルの長さが異なることはあまりありません。ただし、小さなファイルをハッシュするのに費用はかかりません。

より大きなファイルの場合、可能なファイル長が増えるにつれて、ファイル長の衝突の可能性は低くなります。異なるメディア ファイルの場合、ヘッダーを超えて直接異なる可能性が非常に高いため、ファイルの先頭の短い部分のみをハッシュする必要があります。

最後に、必要に応じてファイル全体をハッシュするため、異なるファイル (ハッシュ衝突を除く) を確実に検出できます。

アップデート

映画の場合、ファイルの長さは実質的に一意であると考えますが、特定のメディアに収まるように再作成されたファイルは、おそらくこの考えを無効にします.(S)VCD映画はすべて、CD-ROM容量程度の小さな範囲のファイル長になります.

しかし、一般的なムービー ファイルの場合、ファイルの途中から 1 ブロック (おそらく 512 バイト) をハッシュするだけです。同じ位置で同じ画像と音声の 2 つの異なる映画? ファイルを操作してこのテストに失敗する以外は、事実上不可能です。ただし、すべての決定論的サンプリング戦略に失敗するファイルを簡単に生成できるため、これは実際には問題になりません。

于 2009-04-25T12:16:13.013 に答える
1
  • ファイルの最初と最後のブロックを常にハッシュに含めます。

これは、ファイルごとに異なる可能性が最も高いためです。BMP を検討する場合、かなり標準的なヘッダー (800x600 画像、24 ビット、ヌル レストなど) を持っている可能性があるため、差別化データに到達するためにヘッダーを少しオーバーシュートする必要がある場合があります。問題は、ヘッダーのサイズが大きく異なることです。

最後のブロックは、オリジナルにデータを追加するファイル形式用です。

  • 使用するファイルシステムに固有のサイズ、または少なくとも 512 で割り切れるサイズのブロックを読み取ります。
  • 常にブロックサイズで割り切れるオフセットでブロックを読み取ります。
  • 同じサイズのファイルが同じである場合は、そのファイルのディープ スキャン (すべてのデータをハッシュ) を実行し、ファイル パスを記憶して再度スキャンしないようにします。

それでも、運が良ければ、一部のファイルを同じものとして誤認することになります (たとえば、SQL Server データベース ファイルと、数回挿入しただけで 1:1 のバックアップ コピーになります。ただし、SS はタイムスタンプを書き込みます..)

于 2009-04-25T12:33:21.867 に答える
0
  1. 逆方向にシークせず、FILE_FLAG_SEQUENTIAL_SCAN でファイルを開きます (Windows の場合)。
    (X 個の乱数を選択して並べ替えます)。
  2. 遠くまでシークするには、通常、先読みキャッシュにいくつかのデータがあります。
  3. 大きなファイルがある場合は、パーティションを大きなセクター サイズにフォーマットします。
  4. Id の Guid を返します。ハッシュ アルゴリズムには 128 ビット以上が必要です。
于 2009-04-25T12:16:47.630 に答える