Python: Rabin-Karp算法哈希

Question

我正在实现拉宾-卡普算法，纯粹是为了好玩。然后我看到了这个伪代码：

    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

这里的结果是一个列表，里面包含了模式在文本中的索引。

我的代码没有找到“26”在“3141592653589793”中的位置，我怀疑这和伪代码第14行定义的哈希值有关。有没有人能帮我解决这个问题。

我传入了以下参数：

P = "26"

T = "3141592653589793"

d = 257

q = 11

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

Answer 1

好的，答案是你需要给“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，我想这就是你想要的结果吧。这个算法挺有意思的。

Answer 2

这是你代码的一个可运行版本：

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 可能有助于将误报的概率降低到一个可接受的水平。