重複を見つけるアルゴリズム

Question

重複を効率的に見つける有名なアルゴリズムはありますか？

私が数千の写真を持っていて、写真に一意の名前が付けられているとします。異なるサブフォルダに重複が存在する可能性があります。 std :: mapやその他のハッシュマップを使用するのは良い考えですか？

Answer 1

ファイルを扱う場合は、最初にファイルの長さを確認してから、同じサイズのファイルだけのハッシュを生成することをお勧めします。

次に、ファイルのハッシュを比較してください。それらが同じであれば、重複ファイルがあります。

安全性と正確さの間にはトレードオフがあります。同一のハッシュを持つ異なるファイルを持つことは誰でも知ることができます。だからあなたはあなたのソリューションを改善することができます：dupsを見つけるためのシンプルで高速なハッシュを生成します。彼らが違っていたら、あなたは違うファイルを持っています。それらが等しい場合は、2番目のハッシュを生成します。 2番目のハッシュが異なる場合は、偽陽性になります。彼らが再び等しい場合、おそらくあなたは本当の重複を持っています。言い換えれば

：すべてのファイルのハッシュを行う

generate file sizes 
for each file, verify if there's some with the same size. 
if you have any, then generate a fast hash for them. 
compare the hashes. 
If different, ignore. 
If equal: generate a second hash. 
Compare. 
If different, ignore. 
If equal, you have two identical files. 

は、あまりにも多くの時間がかかりますし、あなたのファイルのほとんどが異なる場合は役に立たないだろう。

Answer 2

おそらく、各オブジェクトをハッシュし、ハッシュを何らかの種類のテーブルに格納したいのですか？重複をテストするには、テーブル内でクイックルックアップを実行するだけです。このタスクを達成するために、「有名なアルゴリズム」については

Mystery data structure???

、MD5を見てみましょう。