algorithm - 作业 : Implementing Karp-Rabin; For the hash values modulo q, 解释为什么用 q 作为 2 的幂是个坏主意？

Question

我有一个双重作业问题，实现 Karp-Rabin 并在测试文件上运行它，第二部分:

2. For the hash values modulo q, explain why it is a bad idea to use q as a power of 2. Can you construct a terrible example e.g. for q=64 and n=15?

这是我的算法实现:

def karp_rabin(text, pattern):
    # setup
    alphabet = 'ACGT'
    d = len(alphabet)
    n = len(pattern)
    d_n = d**n
    q = 2**32-1
    m = {char:i for i,char in enumerate(alphabet)}
    positions = []

    def kr_hash(s):
        return sum(d**(n-i-1) * m[s[i]] for i in range(n))

    def update_hash():
        return d*text_hash + m[text[i+n-1]] - d_n * m[text[i-1]]

    pattern_hash = kr_hash(pattern)
    for i in range(0, len(text) - n + 1):
        text_hash = update_hash() if i else kr_hash(text[i:n])
        if pattern_hash % q == text_hash % q and pattern == text[i:i+n]:
            positions.append(i)

    return ' '.join(map(str, positions))

...问题的第二部分是指代码/算法的这一部分:

    pattern_hash = kr_hash(pattern)
    for i in range(0, len(text) - n + 1):
        text_hash = update_hash() if i else kr_hash(text[i:n])
        # the modulo q used to check if the hashes are congruent
        if pattern_hash % q == text_hash % q and pattern == text[i:i+n]:
            positions.append(i)

我不明白为什么将 q 用作 2 的幂是个坏主意。我已经尝试在提供的测试文件(这是 ecoli 的基因组)上运行该算法并且没有明显的区别。

我试着查看如何推导哈希值的公式(我不擅长数学)，试图找到一些对 2 的幂非常不利的公因数，但一无所获。我觉得如果 q 是 2 的幂，它应该会导致很多哈希冲突，因此您需要更多地比较字符串，但我也没有发现任何类似的东西。

我真的很感激这方面的帮助，因为我很困惑。如果有人想指出我在第一部分中可以做得更好的地方(代码效率、可读性、正确性等)，我也很高兴听到您对此的意见。

Answer 1

如果 q 除以 d 的某个次方，就会出现问题，因为这样只有少数字符对散列有贡献。例如，在您的代码 d=4 中，如果您采用 q=64，则只有最后三个字符确定哈希值 (d**3 = 64)。

如果 q 是 2 的幂但 gcd(d,q) = 1，我真的看不出问题。

你的实现看起来有点奇怪，因为不是

if pattern_hash % q == text_hash % q and pattern == text[i:i+n]:

你也可以用

if pattern_hash == text_hash and pattern == text[i:i+n]:

这会更好，因为碰撞更少。