1

実行中のチェックサムの計算を検討する際には、説明が必要です。

このようなデータがあると仮定します。

data = 'helloworld'

ブロックサイズを5とすると、実行中のチェックサムを計算する必要があります。

>>> zlib.adler32('hello')
103547413
>>> zlib.adler32('ellow')
105316900

Pythonのドキュメントによると（Pythonバージョン2.7.2）

zlib.adler32(data[, value])

「データのAdler-32チェックサムを計算します。（Adler-32チェックサムはCRC32とほぼ同じくらい信頼性がありますが、はるかに高速に計算できます。）値が存在する場合は、チェックサムの開始値として使用されます。それ以外の場合は、固定のデフォルト値が使用されます。これにより、複数の入力の連結に対して実行中のチェックサムを計算できます。」

しかし、私がこのようなものを提供するとき、

>>> zlib.adler32('ellow', zlib.adler32('hello'))
383190072

出力は完全に異なります。

rsyncアルゴリズムで定義されているローリングチェックサムを生成するカスタム関数を作成してみました。

def weakchecksum(data):
    a = 1
    b = 0

    for char in data:
        a += (ord(char)) % MOD_VALUE
        b += a % MOD_VALUE



    return (b << 16) | a



def rolling(checksum, removed, added, block_size):
    a = checksum
    b = (a >> 16) & 0xffff
    a &= 0xffff

    a = (a - ord(removed) + ord(added)) % MOD_VALUE
    b = (b - (block_size * ord(removed)) + a) % MOD_VALUE

    return (b << 16) | a

これらの関数を実行して得られる値は次のとおりです

Weak for hello: 103547413
Rolling for ellow: 105382436
Weak for ellow: 105316900

ご覧のとおり、ローリングチェックサムとPythonの実装には、価値の点で大きな違いがあります。

ローリングチェックサムの計算でどこが間違っているのですか？Pythonのadler32関数のローリングプロパティを正しく利用していますか？

4

5 に答える 5

7

このadler32()機能は「ローリング」を提供しません。ドキュメントでは、「実行中」(「ローリング」ではなく) という言葉が正しく使用されています。これは、adler32 を一度に計算するのではなく、チャンクで計算できることを意味します。「ローリング」adler32 値を計算するには、独自のコードを記述する必要があります。これは、データ上のスライディング ウィンドウの adler32 になります。

于 2012-03-14T19:17:33.460 に答える
4

ちなみに、少なくともモジュロ結果の符号に除数の符号があるPythonの場合、def roller()は正しいです。他の言語では機能しない可能性があります。たとえば C では、% の結果の符号は被除数の符号であるか、実装定義です。

各ステップでモジュロ 65521 からどれだけ離れているかを検討し、% を if と 65521 の加算または減算に置き換えるか、十分な大きさのデータ型を使用してしばらく放置して計算することで、アルゴリズムをより効率的にすることができます。オーバーフローを避けるために、合計の % を使用して回避できる頻度を調べます。繰り返しますが、負の配当の % には注意してください。

于 2012-03-15T18:32:45.453 に答える
1

ここに作業機能があります。MOD がどの段階で計算されるかに注目してください。

def myadler32(data):
  a = 1
  b = 0
  for c in data:
      a += c
      b += a
  a %= MOD_ADLER
  b %= MOD_ADLER
  return b<<16 | a
于 2013-10-20T12:59:19.007 に答える
0

テストでadler32値を誤って計算したと思います。

>>> import zlib
>>> zlib.adler32("helloworld")
389415997
>>> zlib.adler32("world",zlib.adler32("hello"))
389415997
于 2012-03-14T09:45:03.803 に答える