家庭作业：实施 Karp-Rabin；对于以 q 为模的散列值，请解释为什么将 q 用作 2 的幂是个坏主意？

Question

我有两个家庭作业问题，实施 Karp-Rabin 并将其运行放在测试文件和第二部分：

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))

...问题的第二部分是指code/algo的这一部分：

    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]:

哪个更好，因为碰撞更少。

Answer 2

Thue–Morse sequence 的特性之一是，对于任何多项式基数 (d)，当哈希模块为 2 的幂时，其多项式哈希很快变为零。因此，如果您尝试在较长的 Thue-Morse 序列中搜索较短的 Thue-Morse 序列，将会遇到大量哈希冲突。

比如你的代码，稍作改编：

def karp_rabin(text, pattern):
    # setup
    alphabet = '01'
    d = 15
    n = len(pattern)
    d_n = d**n
    q = 32
    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))

print(karp_rabin('0110100110010110100101100110100110010110011010010110100110010110', '0110100110010110'))

输出了很多位置，虽然只有三个是正确的匹配。

请注意，我已删除 and pattern == text[i:i+n] 检查。显然，如果你恢复它，结果将是正确的，但也很明显，算法将比其他 q 做更多的工作来检查这个附加条件。事实上，因为有太多的碰撞，整个算法的想法变得不起作用：你几乎可以同样有效地编写一个简单的算法来检查每个位置是否匹配。

另请注意，您的实现很奇怪。多项式散列的整个思想是每次计算散列时都进行取模运算。否则你的 pattern_hash 和 text_hash 是非常大的数字。在其他语言中，这可能意味着算术溢出，但在 Python 中，这将调用大整数算术，这很慢并且再次失去了整个算法的概念。

家庭作业：实施 Karp-Rabin；对于以 q 为模的散列值，请解释为什么将 q 用作 2 的幂是个坏主意？

Homework: Implementing Karp-Rabin; For the hash values modulo q, explain why it is a bad idea to use q as a power of 2?

algorithm

hash

bioinformatics

biopython

rabin-karp