在java中使用散列匹配模式

我试图学习如何使用多个散列匹配给定文本字符串中的模式。我发现下面的实现在Java中：在java中使用散列匹配模式

void multiHashing() { 
    int counter = 0; 
    int d = 26; 
    int r = 10; 
    int [] qP = qPrimes(d,r); // stores 10 prime numbers 
    long [] P = new long[r]; 
    long [] T = new long[r]; 
    long [] H = new long[r]; 
    for (int k=0;k<r;k++) { 
     H[k] = mod(((long) Math.pow(d, m-1)), qP[k]); 
     for (int i=0;i<m;i++) { 
      P[k] = mod((d*P[k] + ((int)pattern.charAt(i) - 97)), qP[k]); //what has been done here 
      T[k] = mod((d*T[k] + ((int)text.charAt(i) - 97)), qP[k]); 
     }   
    } 
    for (int s=0;s<=n-m;s++) { 
     if (isEqual(P,T)) { 
      out.println(s); 
      counter++; 
     } 
     if (s < n-m) { 
      for (int k=0;k<r;k++) 
       T[k] = mod(d*(T[k] - ((int)text.charAt(s) - 97)*H[k]) + ((int)text.charAt(s+m) - 97), qP[k]);  // what has been done here? 
     } 

    } 
}

的问题是：我不明白在我已经在代码注释掉上面的一些代码行。实际上在这些方面做了什么？

来源

2016-12-11 user6216509

这是Rabin-Karp字符串搜索算法。该算法不是将模式与文本的每个部分进行比较，而是尝试比较散列值以减少计算。

为了计算散列值，它使用rolling hash，它维护文本的固定宽度窗口（在本例中为width = length of pattern），并通过一次移动该窗口一个字符来更新它。

Input: pattern P, text T, d, prime number q 

m = P.length 
n = T.length 
p = 0 // hash of pattern P 
t = 0 // hash of text T 
h = (d^(m-1)) % q 

// preprocessing: hashing P[1..m] and T[1..m] (first window of T) 
for i = 1 to m 
    p = (d * p + P[i]) % q //(1) 
    t = (d * t + T[i]) % q 

// matching 
for s = 0 to n-m 
    if(p == t) 
     if(P[1..m] == T[s+1..s+m] 
      print "matched" 
    // update the rolling hash 
    if(s < n-m) 
     t = (d * (t - T[s+1] * h) + T[s+m+1]) % q // (2)

在预处理阶段，它计算模式P和文本T的第一个窗口的哈希为了计算，我们需要计算出每个人物的阴影线图案的哈希值。 (1) p = (d * p + P[i]) % q实际上会计算第i个字符的散列值。维基百科

实施例：

// ASCII一个= 97，B = 98，R = 114

散列（ “ABR”）=（97×1012）+（98×1011 ）+（114×1010）= 999509

在T中的第s个窗口P的情况下，散列值和图案（文本的第s个窗口上比较之后匹配的相位是相等的），我们需要更新散列值代表T的第（s + 1）个窗口。(2) t = (d * (t - T[s+1] * h) + T[s+m+1]) % q首先减去las的第一个字符的散列值t窗口，然后添加下一个字符的散列值，并因此将窗口向前移动一个字符。

维基百科：

滚动哈希函数只是增加了在串每个字符的值。 s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

然后我们就可以计算下一子，“胸罩”的哈希值减去数，从“ABR”哈希：此滚动散列公式可以从在固定时间的前一个值计算下一个哈希值添加的“ABR”第一“A”，即，97×1012，由碱增殖和增加最后的“胸罩”一个，即，97×1010像这样：
  base old hash old 'a'  new 'a' 
散列（”文胸“）= [101×（999,509-（97×1012））] +（97×1010）= 1,011,309

名

备注：

(int)text.charAt(s) - 97：97是字符的 'A'，所以这种操作的变化 'A' 的ASCII码为0， 'B' 为1，等等

来源

2016-12-12 05:58:20 Omid

在java中使用散列匹配模式

回答

相关问题