11

摘要：有没有办法做到这一点？这就是我的意思：假设我有一个无符号整数。然后我将它乘以几次（并且有溢出，这是预期的）。那么是否可以“恢复”原始值呢？

详细说明：

这都是关于Rabin-Karp rolling hash 的。我需要做的是：我有一个长字符串的散列 - 例如：“abcd”。然后我有一个较短的子字符串的哈希 - 例如“cd”。如何使用两个给定的哈希计算 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-光盘

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是 p^2 模 2^32 的模乘逆，b * p^2 = 1 (mod 2^32). 计算后G，除以p^2即可ab。

我希望我没有犯任何错误...

于 2011-05-07T13:11:08.440 回答
3

扩展欧几里得算法是一个很好的解决方案，但它过于复杂且难以实现。有一个更好的。

还有另一种方法可以做到这一点（感谢我的朋友（：）

维基百科中有一篇不错的文章-在这种情况下使用欧拉定理的模乘逆m，当和a互质时：

互质数和模的欧拉定理

欧拉的总函数φ(m)在哪里。

在我的例子中，m(modulo) 是散列类型的大小 - 2^32,2^64等（在我的例子中是 64 位）。
嗯，这意味着，我们应该只找到 的值φ(m)。但是想一想——m == 2 ^ 64所以，这给了我们保证所有奇数m 互质而不是任何偶数互质。所以，我们需要做的是获取所有值的个数并将它们除以 2。

此外，我们知道这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 （或 mod 其他东西，取决于你如何做你的哈希）。如果你能找到 d 使得 b * d = 1 mod 2^32（或 mod 其他），那么你可以计算 a * b * d = a 并检索 a。如果 gcd(b, mod 2^32) = 1 那么你可以使用http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm来找到 x 和 y 使得 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，因为 171*3=513=2*256+1。如果 p 和模值互质，则存在乘法逆元。

于 2011-05-07T13:35:54.757 回答
1

这里只是一个部分的侧面答案：我相信使用无符号整数并不是绝对必要的。你可以使用一个补码。

但请注意，这将对 -0 和 +0 有单独的表示，并且您可能必须在此过程中手动编码算术运算。

一些处理器指令与整数表示无关，但不是全部。

于 2011-05-07T14:55:00.113 回答
0

所以溢出实际上只是你的编译器对你很好；C/++ 标准实际上表明溢出是未定义的行为。因此，一旦您溢出，实际上您无能为力，因为您的程序不再具有确定性。

您可能需要重新考虑算法，或使用模运算/减法来修复您的算法。

于 2011-05-07T12:37:45.063 回答