0

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

  1. 对于以 q 为模的哈希值，解释为什么使用 q 作为 2 的幂是一个坏主意。你能构造一个糟糕的例子，例如 q=64 和 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 的基因组）上运行算法并且没有明显的区别。

我尝试查看如何导出哈希的公式（我不擅长数学），试图找到一些对二次幂非常不利的共同因素，但一无所获。我觉得如果 q 是 2 的幂，它应该会导致很多哈希冲突，所以你需要更多地比较字符串，但我也没有找到任何类似的东西。

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

4

2 回答 2

3

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

这会更好，因为你得到的碰撞更少。

于 2015-09-07T15:28:30.473 回答
2

Thue-Morse 序列的特性之一是，当 2 的幂是散列模块时，它的多项式散列很快变为零，无论多项式基 ( d)。因此，如果您尝试在较长的序列中搜索较短的 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 中，这将调用大整数算术，这很慢，并且再次失去了算法的整体理念。

于 2015-09-07T15:49:30.497 回答