1

サイズ N とサイズ M の 2 つの順序付けられていないチェックサムのセットがあるとします。それらを比較するアルゴリズムによっては、サイズがわからない場合もありますが、N != M を比較して迅速に中止することができます。

チェックサムに使用されるハッシュ関数には衝突の可能性があり、素人として私は愚かにも「強度」と呼んでいます。すべて同じハッシュ関数から作成された2セットのチェックサムを取得し、2つの個々のチェックサム間にあるのと同じように、2つのセット間の衝突の同じ基本的な可能性を使用してそれらをすばやく比較する方法はありますか? ?

たとえば、1 つの方法は、セット内のすべてのチェックサムを XOR して「セット チェックサム」を計算することです。この新しい単一のハッシュは、他のセットのハッシュと比較するために使用されます。つまり、サイズのストレージは不要になりました。特に、全体を再計算することなく、セットのチェックサムと XOR することにより、要素のチェックサムの追加/削除のために変更できるためです。しかし、それはすべての元のものの強引な比較と比較して、セットのチェックサムの「強度」を低下させますか? セット要素のチェックサムを直接比較するよりも「強度」を低下させずに（それほど）複雑ではないセットのチェックサムをまとめる方法はありますか？

4

1 に答える 1

1

最初のコメントの後、その背後にある数学について考え始めました。これが私が思いついたものです。私は専門家ではないので、お気軽に訂正してください。注：これはすべて、ハッシュ関数が均一に分散されていることを前提としています。

基本的に、チェックサムのビット数が多いほど、衝突の可能性が低くなります。ファイル数が多いほど高くなります。

まず、1 組のファイルが XOR された場合に衝突が発生する可能性を見つけてみましょう。最初は小さい数値で作業するので、チェックサムが 4 ビット (0 ～ 15) であると仮定し、それを と呼びますn。

2 つの合計で、合計ビット数2n(8) であるため、2^(2n)合計 (256) の可能性があります。ただし、衝突だけに関心があります。XOR を衝突させるには、両方の合計で同じビットを反転する必要があります。ビット2^nを使用しているため、これを行う方法は (16)しかありません。n

したがって、衝突の全体的な確率16/256は(2^n) / (2^(2n))、または単純に1/(n^2)です。つまり、衝突しない確率は です1 - (1/(n^2))。したがって、このサンプルの場合、これは安全である、つまり 93.75% でnあることを意味します。15/16もちろん、チェックサムが大きいほど良いです。ちっぽけな の場合でも、n=1699.998% を取得します

もちろん、それは単一の比較のためです。それらをすべて一緒にローリングしているので、f-1比較を行っていfます。ファイルの数はどこですか。この方法で衝突の確率を合計するにf-1は、最初のステップで得た確率を乗じます。

したがって、4 ビットのチェックサムを持つ 10 個のファイルの場合、かなりひどい結果が得られます。

(15/16) ^ 9 =衝突しない確率 55.92%

ファイルの数を増やしても、ビットを追加すると、これは急速に改善されます。

8 ビットのチェックサムを持つ 10 個のファイルの場合:

(255/256) ^ 9 = 96.54%

16 ビットの 100/1000 ファイルの場合:

(65536/65536) ^ 99 = 99.85%

(65536/65536) ^ 999 = 98.49%

ご覧のとおり、まだ小さいチェックサムで作業しています。>= 32ビットのものを使用している場合、計算をしようとすると、計算機で浮動小数点の丸めエラーが発生します。

TL、DR:

はチェックサムnビットfの数で、 は各セット内のファイルの数です。

nonCollisionChance = ( ((2^n)-1) / (2^n) ) ^ (f-1)
collisionChance = 1 - ( ((2^n)-1) / (2^n) ) ^ (f-1)

一連のチェックサムを XOR する方法は、おそらく問題ありません。

于 2013-10-02T21:39:30.270 に答える