Python：Rabin-Karp算法哈希

一尘不染

Python：Rabin-Karp算法哈希

algorithm

我正在实现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是一个列表，其中包含模式文本的索引。

我的代码未能在3141592653589793中找到26，我怀疑它与伪代码第14行定义的哈希码有关。任何人都可以帮忙。

我传递了以下参数：

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

P和T必须是字符的字符串/数组

阅读 540

2020-07-28

共1个答案

一尘不染

这是您的代码的有效版本：

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”）。

另外值得注意的是：

h = pow(d,m-1)%q如果太大，线可能太慢m。最好q在每个m-2乘法之后对结果取模。
在最坏的情况下，该算法仍为O（nm）。使用text="a"*100000和pattern="a"*50000，它将找到50001个文本子字符串与模式匹配的位置，并将逐个字符地检查它们。如果您希望代码在这样的极端情况下可以快速运行，则应跳过逐个字符的比较，并找到一种处理误报的方法（即，哈希值相等而字符串不相等）。选择大质数q可能有助于将误报的可能性降低到可接受的水平。

2020-07-28