11

要約：それを行う方法はありますか？これが私が言いたいことです: unsigned int番号があるとします。次に、それを数回乗算します（予想されるオーバーフローがあります）。それでは、元の値を「元に戻す」ことは可能ですか?

詳細に：

Rabin-Karp ローリング ハッシュがすべてです。私がする必要があるのは、長い文字列のハッシュを持っていることです。たとえば、「abcd」です。次に、「cd」などの短い部分文字列のハッシュを取得します。与えられた2つのハッシュを使用して、O(1)で「ab」ハッシュを計算する方法は?

私が今アルゴリズムとして持っているもの：

  • 「abcd」ハッシュから「cd」ハッシュを減算します（多項式から最後の要素を削除します）
  • 「abcd」ハッシュをp ^ len( "cd" )で割ります。ここpで、 は基数 (素数) です。

これは次のとおりです。

a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0-abcd _

c * p ^ 1 + d * p ^ 0- CD

abは次を取得します。

(
  ( a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0 ) -
  ( c * p ^ 1 + d * p ^ 0 )
)
/ ( p ^ 2 )
= a * p ^ 1 + b * p ^ 0

そして、オーバーフローがない場合p（小さい場合）、これは機能します。しかし、そうでない場合は機能していません。

何か裏技とかありますか？

PSc++タグは、特定のものであるため、番号のオーバーフローが原因です（そして、python、scheme、またはsthとは異なります）

4

6 に答える 6

5

オーバーフローの部分はわかりませんが、元の値に戻す方法はあります。

中国剰余定理は大いに役立ちます。に電話しましょうh = abcd - cd。G はhオーバーフローなしの値 でありG = h + k*2^32、オーバーフローが単純に であると仮定し%2^32ます。そしてこうしてab = G / p^2。

G = h (mod 2^32)
G = 0 (mod p^2)

p^2 と 2^32 が互いに素の場合。中国剰余定理に関するこのページでは、

G = h * b * p^2 (mod 2^32 * p^2)

bモジュロ 2^32 を法とする p^2 のモジュラ乗法逆数はどこにありますかb * p^2 = 1 (mod 2^32)。を計算したらG、 で割りp^2ますab。

私は間違いを犯さなかったことを願っています...

于 2011-05-07T13:11:08.440 に答える
3

拡張ユークリッドアルゴリズムはこれに対する優れたソリューションですが、複雑すぎて実装が困難です。より良いものがあります。

そして、これを行う別の方法があります（私の友人のおかげで（:)

ウィキペディアに素晴らしい記事があります-互いに素である場合、オイラーの定理を使用したモジュラ逆数：ma

互いに素な数とモジュロに関するオイラーの定理

ここφ(m)で、オイラーのトーティエント関数はです。

私の場合、m（モジュロ）はハッシュタイプのサイズです- 2^32、、2^64など（私の場合は64ビット）。
つまり、これは、の値のみを見つける必要があることを意味しますφ(m)。しかし、それについて考えてみてください。つまり、すべての奇数と互いに素であり、偶数と互いに素ではないm == 2 ^ 64という保証が得られます。したがって、必要なのは、すべての値の数を取得し、それらを2で割ることです。 m

mまた、署名されていないこともわかっています。そうでない場合は、いくつかの問題が発生します。これよりも、これを行う機会があります。

hash_t x = -1;
x /= 2;
hash_t a_reverse = fast_pow( a, x );

さて、約64ビットの数値xは、実際には大きな数値（19桁:)です9 223 372 036 854 775 807が、fast_pow非常に高速であり、複数のクエリが必要な場合に備えて、逆の数値をキャッシュできます。

fast_powよく知られているアルゴリズムです：

hash_t fast_pow( hash_t source, hash_t pow )
{
    if( 0 == pow )
    {
        return 1;
    }

    if( 0 != pow % 2 )
    {
        return source * fast_pow( source, pow - 1 );
    }
    else
    {
        return fast_pow( source * source, pow / 2  );    
    }

}

追加：例：

    hash_t base = 2305843009213693951;  // 9th mersenne prime
    hash_t x = 1234567890987654321;

    x *= fast_pow( base, 123456789 );   // x * ( base ^ 123456789 )

    hash_t y = -1;
    y /= 2;
    hash_t base_reverse = fast_pow( base, y );

    x *= fast_pow( base_reverse, 123456789 );   // x * ( base_reverse ^ 123456789 )
    assert( x == 1234567890987654321 ) ;

完璧で非常に高速に動作します。

于 2011-05-08T12:26:01.207 に答える
2

a * b = c mod 2^32 (または、ハッシュの実行方法に応じて他の何かを変更) があります。b * d = 1 mod 2^32 (または何でも mod ) のような d を見つけることができれば、a * b * d = a を計算して a を取得できます。gcd(b, mod 2^32) = 1 の場合、http://en.wikipedia.org/wiki/Extended_Euclidean_algorithmを使用して、b * x + 2^32 * y = 1、またはb * x = 1 - y * 2^32、または b * x = 1 mod 2^32 なので、x は掛けたい数値です。

于 2011-05-08T04:23:11.750 に答える
1

定義されたオーバーフロー動作（モジュロ2 ^ N）を取得するには、符号なし整数を使用する必要があります。符号付き整数のオーバーフローは未定義です。

また、除算する代わりに、適切な値を法としてpの逆数を乗算する必要があります。たとえば、p = 3でハッシュ値が8ビットの場合、171 * 3 = 513 = 2 * 256 + 1であるため、171を掛けます。pとモジュロ値が互いに素である場合、逆数が存在します。

于 2011-05-07T13:35:54.757 に答える
0

したがって、オーバーフローは実際にはコンパイラがあなたに親切にしているだけです。C/++ 標準では、オーバーフローは未定義の動作であることが実際に示唆されています。したがって、オーバーフローすると、プログラムが決定論的でなくなるため、実際には何もできなくなります。

アルゴリズムを再考するか、アルゴリズムを修正するためにモジュロ演算/減算に取り組む必要があるかもしれません。

于 2011-05-07T12:37:45.063 に答える