在 Rabin-Karp 滚动哈希算法中选择基数和模质数的问题

Question

在 Rabin-Karp 滚动哈希算法中选择基数和模质数的问题

algorithmlanguage-agnostic

6

哈希函数在维基百科上有解释。

它说：“选择a和n对于获得良好的哈希至关重要；”并参考了一个似乎不相关的线性同余发生器文章。我无法弄清楚如何选择这些值。有什么建议吗？

- Aks

真的没有固定的配方。你必须进行实验，或者使用其他人已经证明在一般情况下或特定情况下工作良好的方法。 - IVlad

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

该算法的基础是，次数不超过d的非零多项式最多有d个零点。每个长度为k的字符串都有一个关联的次数为k-1的多项式，并通过减去相关字符串的多项式并在a处求值来筛选可能的匹配项。如果字符串相等，则结果始终为零。如果字符串不相等，则结果为零当且仅当a是多项式差的零点之一（这就是将素性要求放在n上的事实，因为模n的整数否则将不是一个域）。

在理论上，至少我们希望a是随机的，这样一个无意识的对手就不能频繁地制造假阳性。如果我们不期望出现问题，那么最好选择a，使得乘以a变得便宜（例如，a的二进制展开具有较少的一位）。然而，在典型的字符串集上，有些选择是不好的（例如，a=1）。我们希望n足够大，以避免假阳性（概率为(k-1)/n）通过随机机会，但足够小并且最好具有特殊形式，以使模运算高效。