ルートディレクトリが指定されているファイルシステム内のすべての重複ファイルをリストします。

Question

ファイルシステム内のすべての重複ファイルを一覧表示するアルゴリズムの設計についてどう思いますか？私の最初の考えではハッシュを使用すると思っていましたが、もっと良い方法があるのだろうかと思っています。心に留めておくべき可能性のあるデザインのトレードオフは何ですか？

Answer 1

すべてのファイルの内容を読み取る必要があるため、すべてのファイルをハッシュするには非常に時間がかかります。

私は、3ステップのアルゴリズムをお勧めします：

1. がいる場合にのみ、あなたのディレクトリをスキャンし、パスファイルの&サイズ
2. ハッシュ他のファイルと同じサイズを持つファイルのみを書き留め同じサイズのファイルが2つ以上あります。ファイルのサイズが他のファイルと同じであれば、ハッシングは必要なく、内容を1対1で比較するだけです（ハッシュ時間を節約します。後でハッシュ値が必要）
3. ハッシュが同じであっても、バイト単位でファイルを比較する必要があります。なぜなら、haファイルのサイズが同じで、ファイルシステムが（）のファイルシステムの場合、shは異なるファイルで同じになることがあります。

可能であれば、すべてのファイルを同時に開いて内容を比較することもできます。それは大きなファイルの複数の読み込みを節約します。データの種類に応じて時間を節約するために実装することができる調整がたくさんあります（例：2つの圧縮/ tarファイルが同じサイズ> x Ggigabytesのサイズ（および同じ名前）の場合、内容を読み込まないでくださいプロセスがあれば、ファイルは重複している可能性が非常に高いです）。

このようにして、システム内で一意のサイズのファイルをハッシュしないようにします。多くの時間を節約します。

注：名前は異なる可能性があるため、ここでは名前を考慮しません。

編集：私は研究のビット（遅すぎる）を行い、fdupesあなたはUN * Xのようなシステムを使用している場合ことを正確に行うように見えることが判明しました：で見

https://linux.die.net/man/1/fdupes

をその質問：List duplicate files in a directory in Unix