Python：Rabin-Karp算法哈希

Question

Python：Rabin-Karp算法哈希

6

我想玩一下实现Rabin-Karp算法。我看到了这段伪代码：

    RABIN -KARP -MATCHER (T, P, d, q)
    1 n = T.length
    2 m = P.length
    3 h = d^(m-1) mod q
    4 p=0
    5 t= 0
    6 for i = 1 to m
    / preprocessing
    /
    7 p = (dp + P [i]) mod q
    8 t = (dt + T [i]) mod q
    9 for s = 0 to n-m
    / matching
    /
    10     if p == t
    11         if P [1... m] == T [s + 1...s + m]
    12             print “Pattern occurs with shift” s
    13     if s < n-m
    14         t  = (d(t-T[s + 1]h) + T [s + m + 1]) mod q

我使用Python 2.7实现的代码如下：

def Rabin_Karp_Matcher(text, pattern, d, q):
    n = len(text)
    m = len(pattern)
    h = pow(d,m-1)%q
    p = 0
    t =0
    result = []
    for i in range(m): # preprocessing
        p = (d*p+ord(pattern[i]))%q
        t = (d*t+ord(text[i]))%q
    for s in range(n-m):
        if p == t: # check character by character
            match = True
            for i in range(m):
                if pattern[i] != text[s+i]:
                    match = False
                    break
            if match:
                result = result + [s]
        if s < n-m:
                t = (d*(t-ord(text[s+1])*h)+ord(text[s+m]))%q #index out of bounds here
    return result

结果(result)是一个列表，其中包含模式(pattern)在文本(text)中的索引。

我的代码无法在3141592653589793中找到26，我怀疑这与伪代码第14行定义的哈希码有关。请有人能帮帮我吗？

我传入了以下参数：

P =“26” T =“3141592653589793” d = 257 q = 11

P和T必须是字符(数组)串。

- SeekingAlpha

2个回答

0

好的，答案是你需要缩进“for s”循环：

def Rabin_Karp_Matcher(text, pattern, d, q):
    n = len(text)
    m = len(pattern)
    h = pow(d,m-1)%q
    p = 0
    t =0
    result = []
    for i in range(m): # preprocessing
        p = (d*p+ord(pattern[i]))%q
        t = (d*t+ord(text[i]))%q

        for s in range(n-m):
            if p == t: # check character by character
                match = True
                for i in range(m):
                    if pattern[i] != text[s+i]:
                        match = False
                        break
                if match:
                    result = result + [s]
            if s < n-m:
                    t = (d*(t-ord(text[s+1])*h)+ord(text[s+m]))%q #index out of bounds here


    return result

这给了我答案6，我想这就是你要找的。有趣的算法。

- davo36

感谢您的输入。然而，我认为这只是一次偶然的正确输出。请查看修订后的伪代码，其中包含正确的缩进。此外，我已经尝试了不同的P值，但并没有得到正确的结果。另外，我期望得到一个索引列表，而不仅仅是第一次出现的位置。我确定错误在第14行的哈希码中，但我无法理解那部分的作用。 - SeekingAlpha

@SeekingAlpha 哦，没关系，即使我错了，我也很高兴能够“帮助” :) - davo36

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

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

- Gassa · Accepted Answer

这是您代码的可运行版本。

def Rabin_Karp_Matcher(text, pattern, d, q):
    n = len(text)
    m = len(pattern)
    h = pow(d,m-1)%q
    p = 0
    t = 0
    result = []
    for i in range(m): # preprocessing
        p = (d*p+ord(pattern[i]))%q
        t = (d*t+ord(text[i]))%q
    for s in range(n-m+1): # note the +1
        if p == t: # check character by character
            match = True
            for i in range(m):
                if pattern[i] != text[s+i]:
                    match = False
                    break
            if match:
                result = result + [s]
        if s < n-m:
            t = (t-h*ord(text[s]))%q # remove letter s
            t = (t*d+ord(text[s+m]))%q # add letter s+m
            t = (t+q)%q # make sure that t >= 0
    return result
print (Rabin_Karp_Matcher ("3141592653589793", "26", 257, 11))
print (Rabin_Karp_Matcher ("xxxxx", "xx", 40999999, 999999937))

输出为：

[6]
[0, 1, 2, 3]

在第一步中，你要检查是否text[0..m] == pattern。在第二步中，你想要检查是否text[1..m+1] == pattern。因此，你要从哈希中移除text[0]（此时它被预先计算的h乘以）：t = (t-h*ord(text[s]))%q。然后，将text[m]添加到其中：t = (t*d+ord(text[s+m]))%q。在下一步中，你要移除text[1]并添加text[m+1]，依此类推。t = (t+q)%q这一行存在的原因是因为负数对q取模的结果在范围(-q; 0]内，而我们希望它在范围[0; q)内。

请注意，你要检查的总共有n-m+1个子字符串，而不是n-m个，因此正确的循环应该是for s in range(n-m+1)。通过第二个例子（在"xxxxx"中查找"xx"）进行验证。

值得注意的是：

1. 如果m很大，那么代码行`h = pow(d,m-1)%q`可能会很慢。在每次进行m-2次乘法后，最好对结果取模q。或者可以使用内置的方式`h = pow(d,m-1,q)`，正如评论中@oBrstisf8o所建议的那样。

2. 在最坏情况下，这个算法的时间复杂度仍然是O(nm)。当`text="a"*100000`和`pattern="a"*50000`时，它将找到50001个位置，其中文本的子串与模式匹配，并且它将逐个字符地检查它们。如果你希望你的代码在这种极端情况下能够快速运行，你应该跳过逐个字符的比较，并找到一种处理误报（即哈希相等但字符串不等）的方法。选择一个大的素数q可能有助于将误报的概率降低到可接受的水平。