Adler32ローリングチェックサムの計算の違い - Python.

StackOverflow https://stackoverflow.com//questions/9699315

  •  13-12-2019
  •  | 
  •  

質問

実行中のチェックサムの計算を見ながら説明が必要です。

私はこのようなデータを持っているとします。

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のように信頼できるが、はるかに早く計算することができます。 値が存在し、チェックサムの開始値として使用されます。 それ以外の場合は、固定のデフォルト値が使用されます。これにより、Aをコンピューティングすることができます いくつかの入力を連結してチェックサムを実行します。 "

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

>>> 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機能のローリング性を正しく使用していますか？

役に立ちましたか？

解決

adler32()関数は「転がり」を提供しません。ドキュメントは正しく「実行中」という単語を使用しています（「ローリング」ではありません）、これは単にADLER32を一度に対照的に、チャンク内のADLER32を計算できることを意味します。あなたは、「ローリング」Adler32値を計算するために独自のコードを書く必要があります。これは、データの上のスライディングウィンドウのADLER32になります。

他のヒント

あなたの方法 "ローリング"、

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

は

であるべきです 
b = (b - (block_size * ord(removed)) + a - 1) % MOD_VALUE
. Adler332 アルゴリズムの説明に従って、

A = 1 + D1 + D2 + ... + Dn (mod 65521)
B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
  = n×D1 + (n−1)×D2 + (n−2)×D3 + ... + Dn + n (mod 65521)

Adler-32(D) = B × 65536 + A
.

チェックサムを圧倒すると、式があります。

A1 = (1 + D2 + D3 + … + Dn + Dn+1)(mod 65521)
= (1 + D1 + D2 + D3 + … + Dn) – D1 + Dn+1(mod 65521)
= A – D1 + Dn+1(mod 65521)
B1 = (1 + D2) + (1 + D2 + D3) + … + (1 + D2 + D3 + … + Dn + Dn+1)(mod 65521)
= (1 + D1) – D1 – 1 + (1 + D1 + D2) – D1 + ... +(1 + D1 + D2 + … + Dn) – D1 + (1 + D1 + D2 +      … + Dn + Dn+1) – D1(mod 65521)
= B – nD1 – 1 + A1 + D1 – D1(mod 65521)
= B – nD1 + A1 – 1(mod 65521)
.

ところで、あなたのDef Rolling（）は少なくともModulo結果の符号が除数の符号を持つPythonのために正しいです。それは他の言語では機能しないかもしれません、例えばcの結果の符号は、配当の符号または実装で定義されています。

各ステップを取得できるモジュロ65521からのどれだけかかわらず、％を交換することができ、65521の追加または減算を取得するか、またはそれを行くために十分なデータ型を使用することによって、アルゴリズムをより効率的にすることができます。あまり赦しを避けるために、あなたがどれほどあまり頻繁に払われてもらうことができます。繰り返しますが、マイナスの配当金の％に注意してください。

これは作業機能です。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
.

あなたがあなたのテストでAdler32の価値を誤って計算したと思います：

>>> import zlib
>>> zlib.adler32("helloworld")
389415997
>>> zlib.adler32("world",zlib.adler32("hello"))
389415997
.

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top