5

オープンソースプロジェクトの場合、ファイルシステムの上に抽象化レイヤーを作成しています。

このレイヤーを使用すると、メタデータと関係を各ファイルに添付できます。

ファイルの名前変更を適切に処理し、ファイルの名前変更/移動またはコピーが行われた場合にメタデータを維持するレイヤーが必要です。

これを行うには、ファイルのIDを計算するためのメカニズムが必要になります。明らかな解決策は、ファイルごとにSHA1ハッシュを計算してから、そのハッシュに対してメタデータを割り当てることです。しかし...それは特に映画にとっては本当に高価です。

ですから、100％正確ではありませんが、ほとんどの場合正しく、安価なアルゴリズムを考えていました。

そのようなアルゴリズムの1つは、ファイルサイズとそのファイルのバイトのサンプルを使用してハッシュを計算することです。

サンプルにはどのバイトを選択する必要がありますか？計算を安価で適度に正確に保つにはどうすればよいですか？ここにはトレードオフがあることは理解していますが、パフォーマンスは重要です。また、ユーザーはシステムがミスを犯した状況に対処できるようになります。

非常に大きなファイル（1GB以上および小さなファイル5K）で機能するには、このアルゴリズムが必要です。

編集

NTFSおよびすべてのSMB共有（LinuxまたはWindowsベース）で機能するには、このアルゴリズムが必要です。ファイルが1つの場所から別の場所にコピーされる状況をサポートしたいと思います（2つの物理コピーが存在する場合は1つのIDとして扱われます）。MP3が再タグ付けされている状況でこれを機能させることを検討することもできます（物理ファイルが変更されているため、ファイルタイプごとにIDプロバイダーがある場合があります）。

編集2

関連する質問：ファイルのIDを決定するためのアルゴリズム（最適化）

4

8 に答える 8

5

バケット化すると、複数の比較レイヤーは、議論しているファイルの範囲全体で最速かつスケーラブルである必要があります。

インデックス作成の第1レベルは、ファイルの長さだけです。

2番目のレベルはハッシュです。特定のサイズを下回ると、ファイル全体のハッシュになります。それを超えて、はい、私はサンプリングアルゴリズムのあなたの考えに同意します。サンプリング速度に影響を与える可能性があると思われる問題：

  1. 非常に類似または同一である可能性のある規則的な間隔のヘッダーにぶつからないようにするには、不適合な数（たとえば、素数の倍数または連続する素数）をステップインする必要があります。
  2. 通常のレコードヘッダーが発生する可能性のある手順は避けてください。場所が異なっていてもサンプルバイトから同じ値を取得している場合は、別の素数で手順を調整してみてください。
  3. エンコードされていない画像であるか、nullで埋められているために、同じ値が大きく広がっている異常なファイルに対処します。
于 2009-01-19T16:36:58.467 に答える
4

最初の 128k、1mb マークで別の 128k、10mb マークで別の 128k、100mb マークで別の 128k、1000mb マークで別の 128k などを行います。サイズのみに基づいて 2 つのファイルを区別できるようになり、データのより小さい部分をハッシュします。128k 未満のものはすべて完全に処理されます。

于 2009-01-19T01:11:07.680 に答える
2

信じられないかもしれませんが、私はファイルの最後の書き込み時間にティックを使用します。それはそれが得るのと同じくらい安いです、そして私はまだ異なるファイル間の衝突を見ています。

于 2009-01-19T00:09:19.913 に答える
2

Linux 共有要件を削除して NTFS に限定できる場合、NTFS 代替データ ストリームは次のような完璧なソリューションになります。

  • いかなる種類のハッシュも必要としません。
  • 名前を変更しても存続します。と
  • 移動に耐えます (異なる NTFS ボリューム間でも)。

詳細については、こちらをご覧ください。基本的には、ストリームにコロンと名前 (例: ":meta") を追加し、好きなように書き込みます。したがって、「D:\Movies\Terminator」というディレクトリがある場合は、通常のファイル I/O を使用してメタデータを「D:\Movies\Terminator:meta」に書き込みます。(フォルダー全体ではなく) 特定のファイルのメタデータを保存する場合も、同じことができます。

メタデータを別の場所に保存し、同じ NTFS ボリュームで移動/名前変更を検出できるようにする場合は、GetFileInformationByHandle API 呼び出しを使用できます (MSDN /en-us/library/aa364952(VS.85) を参照)。 aspx) を使用して、フォルダーの一意の ID を取得します (VolumeSerialNumber メンバーと FileIndex メンバーを組み合わせます)。ファイル/フォルダーが同じボリューム上で移動/名前変更された場合、この ID は変更されません。

于 2009-08-14T22:42:31.053 に答える
1

いくつかのランダムな整数 r iを格納し、バイト (r i mod n) を検索するのはどうでしょうか。ここで、n はファイルのサイズです。ヘッダーを含むファイルの場合、最初にヘッダーを無視してから、残りのバイトに対してこのプロセスを実行できます。

ファイルが実際にかなり異なる場合 (どこかの 1 バイトの違いだけでなく、少なくとも 1% の違いがあるとします)、バイトをランダムに選択すると、それに気付くでしょう。たとえば、バイトの差が 1% の場合、ランダムな 100 バイトは 1/e ~ 37% の確率で気付かないでしょう。見るバイト数を増やすと、この確率は指数関数的に低下します。

ランダムなバイトを使用する背後にある考え方は、他のシーケンスの問題の影響を受けにくいことを除いて、他のバイトのシーケンスと同じくらい良いことが本質的に保証されている (確率論的に言えば) ということです (たとえば、すべてのそのバイトが 0 または何かである必要があるファイル形式の 256 番目のバイト)。

さらにアドバイス：

  • バイトを取得する代わりに、より大きなチャンクを取得して、シークのコストを正当化します。
  • ファイルの最初のブロックかそこらを常に見ることをお勧めします。これから、ファイルタイプなどを判断できます。(たとえば、fileプログラムを使用できます。)
  • 少なくとも、ファイル全体の CRC などの費用対効果を比較検討してください。実際の暗号化ハッシュ関数ほど高価ではありませんが、ファイル全体を読み取る必要があります。利点は、シングルバイトの違いに気付くことです。
于 2009-01-19T00:57:50.127 に答える
0

まず、ファイルシステムがどのように機能するかをより深く調べる必要があります。どのファイルシステムを使用しますか？ほとんどのファイルシステムはハードリンクやソフトリンクなどをサポートしているため、「ファイル名」情報は必ずしもファイル自体のメタデータに格納されているとは限りません。

実際、これはスタック可能な階層化ファイルシステムの要点であり、圧縮や暗号化をサポートするなど、さまざまな方法で拡張できます。これが「vnodes」のすべてです。実際には、いくつかの方法でこれを行うことができます。これのいくつかはあなたが見ているプラ​​ットフォームに非常に依存しています。これは、VFSの概念を使用するUNIX/Linuxシステムでははるかに簡単です。たとえば、ext3のトップに独自のレイヤーを実装することもできます。

**あなたの編集を読んだ後、さらに多くのものを結合します。前述のように、ファイルシステムはすでにiノードなどを使用してこれを実行しています。ハッシュは、高価であるだけでなく、2つ以上のプレイメージが同じイメージを共有できるため、おそらく悪い考えになるでしょう。つまり、2つのまったく異なるファイルが同じハッシュ値を持つことができます。あなたが本当にやりたいのは、ファイルシステムがすでに公開しているメタデータを利用することだと思います。もちろん、これはオープンソースシステムの方が簡単です。:)

于 2009-01-19T00:09:50.037 に答える
0

この作業は、ファイルシステムレベルで、またはバージョン管理システムの大まかな概算（両方？）を使用して、より効果的に実装できるように思われます。

元の質問に対処するために、各ファイルの（ファイルサイズ、ハッシュされたバイト数、ハッシュ）のデータベースを保持し、各ファイルサイズに対してハッシュされたバイト数を最小限に抑えるようにすることができます。衝突を検出するたびに、同じファイルを使用するか、ハッシュの長さを増やして最初の違いを超えます。

間違いなく最適化が行われ、CPUとI / Oのトレードオフもありますが、誤検知が発生しないものにとっては良いスタートです。

于 2009-01-19T03:49:50.637 に答える
0

サンプルにはどのバイトを選択すればよいですか?

フィボナッチ数列のような数列を使ってみようと思います。これらは計算が簡単で、密度が減少します。小さなファイルは大きなファイルよりも高いサンプル比率を持ち、サンプルはファイル全体のスポットを超えます。

于 2009-01-19T00:57:01.393 に答える