人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

1000万件程度のコンテンツ(画像(jpg,png,gifなど)・動画(mpg,avi,movなど)・ドキュメント(pdf,txtなど))があって、
そこに新たにコンテンツを追加しようとしています。
その際に既に同じコンテンツ(バイナリレベルで完全に一致)が存在するか否かを判定して、存在しない場合のみ追加したいです。
その場合の判定方法として確実且つ最速な方法を教えてください。

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


●質問者: kunitz
●カテゴリ:コンピュータ インターネット
✍キーワード:GIF jpg md5 PDF PNG
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

1 ● dev_zer0
●27ポイント

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

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


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

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

(下記URL参照)

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

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

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

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


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

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

◎質問者からの返答

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

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

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

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


2 ● pochi-p
●27ポイント

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

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

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

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

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

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

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


3 ● babydaemons
●26ポイント

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

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

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

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

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

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

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

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ