1000万件程度のコンテンツ(画像(jpg,png,gifなど)・動画(mpg,avi,movなど)・ドキュメント(pdf,txtなど))があって、

そこに新たにコンテンツを追加しようとしています。
その際に既に同じコンテンツ(バイナリレベルで完全に一致)が存在するか否かを判定して、存在しない場合のみ追加したいです。
その場合の判定方法として確実且つ最速な方法を教えてください。

各コンテンツのSHA-512ハッシュを作成しておき、それによる比較などでしょうか?
ただMD5などでの懸念もあるように、違うバイナリで同一のハッシュが作られる懸念は無いでしょうか?

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2009/09/06 16:16:36
  • 終了:2009/09/13 16:20:03

回答(3件)

id:dev_zer0 No.1

dev_zer0回答回数332ベストアンサー獲得回数252009/09/06 17:10:17

ポイント27pt

> 違うバイナリで同一のハッシュが作られる懸念は無いでしょうか?

あります。(確率はかなり低いですが)


> その場合の判定方法として確実且つ最速な方法を教えてください。

予め、ツールなどでハッシュのリストを作っておきます。

(下記URL参照)

http://www.atmarkit.co.jp/fwin2k/win2ktips/597fciv/fciv.html

次にハッシュリストをソートして二分木探索でハッシュの検索を行わせます。

そして、ハッシュが一致した場合、バイナリでの比較を行います。

# ハッシュが一致しなければバイナリ比較はする必要がありません


最後に、追加を行ったファイルのハッシュを追加して、ソートしておくと

次回に追加するときの比較元として流用できます。

id:kunitz

回答ありがとうございます!

最後はバイナリ比較なわけですね。それなら確実ですね。

あれ、、、質問して回答を読んでたりする課程で色々考えていて気づいたのですが、

ハッシュが一致しない場合に、バイナリが一致してしまうというケース。。。とかってあり得るのかな。。。

2009/09/06 17:35:07
id:pochi-p No.2

pochi-p回答回数10ベストアンサー獲得回数02009/09/06 19:35:29

ポイント27pt

> ハッシュが一致しない場合に、バイナリが一致

これは無いです。有ったらハッシュ計算プログラムがバグってます。

100÷20が4になるような話です。

http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A...

手順的には先に「ファイルサイズの比較」を入れておくと良いですね。

ファイルの中身を読まずにファイルシステム等から高速に得られる情報ですし。

次にハッシュの比較、そしてバイナリ比較の流れでしょう。

id:babydaemons No.3

babydaemons回答回数26ベストアンサー獲得回数42009/09/07 20:12:45

ポイント26pt

>各コンテンツのSHA-512ハッシュを作成しておき、それによる比較などでしょうか?

>ただMD5などでの懸念もあるように、違うバイナリで同一のハッシュが作られる懸念は無いでしょうか?

基本的にないはずですが、念には念を入れて、

http://ja.wikipedia.org/wiki/%E6%9A%97%E5%8F%B7%E5%AD%A6%E7%9A%8...

例えば、SSLはMD5とSHA-1を連結して利用している。これにより、どちらか一方が破られても全体としてはセキュリティを保てるようにしている。

のように複数の暗号化ハッシュ関数を併用するというアプローチはいかがでしょうか?

ただし、暗号化ハッシュ関数の種類が増えると当然計算コストも増えるので、

既出ですがハッシュ計算の前にファイルサイズや拡張子であらかじめ判定するのがよいと思います。

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません