最近、Rsync アルゴリズムに出会い、Java を使用して実装することを考えました。このアルゴリズムの重要な部分の 1 つは、送信者側のローリング チェックサムです。
http://en.wikipedia.org/wiki/Rsyncで、その説明
「バイト 1 ～ 25 のローリング チェックサムをすでに計算している場合は、前のチェックサム (R)、バイト 1 (n)、およびバイト 26 (n+S ）」
MD5 または SHA を使用して、ファイルまたは文字列のチェックサムを生成できます。
質問する
695 次
1 に答える
4
ローリング ウィンドウが 3 バイトをカバーし、入力文字列が 5 バイトであると仮定しましょう。文字列 23456 を考えてみましょう。単純なハッシュ関数を使用します。ウィンドウがバイト a、b、c をカバーする場合、ハッシュは ax 100 + bx 10 + c です。
したがって、入力文字列 2345 の場合、最初の 3 バイトのチェックサムは 2 x 100 + 3 x 10 + 4 = 234 です。
次に、ウィンドウが 1 ステップ左に移動し、3、4、5 がカバーされます。3 x 100 + 4 x 10 + 5 を計算する代わりに、以前のチェックサムと、ウィンドウに出入りしたばかりの数値 (それぞれ 5 と 2) の知識を使用できます。
234 から 2 x 100 を引くと 34 になります。34 を 10 倍して 5 を足すと、新しいハッシュ 345 が得られます。新しいウィンドウ。次のバイト シーケンスについては、同じ方法を使用して、ウィンドウ内のすべてのバイトを反復処理することでハッシュ値の計算を回避できます。
于 2012-09-17T13:45:51.343 に答える