CRCが一致する確率

締切済

質問者：kokonkokon
質問日時：2015/04/20 10:26
回答数：3件

http://oshiete.goo.ne.jp/qa/5000059.html

このページに
CRC32が一致する確立は16の8乗。MD5が一致する確立は16の32乗。

この意味するところは
【16^8】
4294967296

4294967296個のファイルを比較した際に異なるファイルであっても
同じファイルで判断されることがある。
という意味ですよね？

つまり、極めて小さな確率なので
二つのファイルが同一であるか調べるためには
MD5ではなくCRC32で十分ということでしょうか？

それと、10000個に一度くらいは異なるファイルであっても同じだと認識されても構わないので
もっと認証が粗く、計算速度の速いアルゴリズムがあれば教えてください。

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (3件)

最新から表示
回答順に表示

No.3

回答者： tknakamuri
回答日時：2015/05/02 09:03

話の前提がわかりません。

予めCRCが計算されてファイルに付与されているのでしょうか？

ファイルを比較するだけなら、ファイルを読んでバイト単位で
比較した方が早い。

要は何がやりたいのかよくわからないということです。

- 0
- 件

通報する

No.2

回答者： SortaNerd
回答日時：2015/04/26 19:23

前半は特に付け加えることはありません。

> もっと認証が粗く、計算速度の速いアルゴリズムがあれば教えてください。
こっちについて。
CRCの計算よりファイルの読み出しの方が遅いので、これ以上の計算速度は無意味です。
ハッシュアルゴリズム側ではなく、ファイルサイズを見るとか、ファイルの一部分を見るとかの工夫が必要です。

- 0
- 件

通報する

参考程度に

No.1

回答者： rinkun
回答日時：2015/04/20 13:43

普通、同一性チェックをするなら、CRCだけで済ませたりはしないでしょう。

前処理で使って、CRCが一緒ならバイナリ比較で一致を確認するのが基本かと。
CRC32で4294967296=2^32というならCRC16なら2^16通りなので誤一致率は数万分の1程度になるのでは?

ただ上の数値はCRCの生成確率に偏りがないという(おそらく正しくない)仮定があるし、特定のファイルとの一致確率でなく任意に取ってきた2つの一致確率だと誕生日のパラドックスで言われるように、CRC32で1/2^16になるので、10000個に一個くらいは間違っても良いという条件だとCRC32くらいは必要なんじゃないかな。
# 誕生日のパラドックス http://ja.wikipedia.org/wiki/%E8%AA%95%E7%94%9F% …