は、Javaでハッシングを使用してパターンを一致させます

Question

私は、複数のハッシュを使用して、指定されたテキスト文字列内のパターンを照合する方法を学習しようとしていました。私は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? 
     } 

    } 
} 

問題がある：私は私がコードでコメントアウトしている上記のコードでは、いくつかの行を理解することはできません。実際にその行で何が行われていますか？

Answer 1

これはRabin-Karp文字列検索アルゴリズムです。パターンをテキストの各部分と比較する代わりに、このアルゴリズムはハッシュされた値を比較して計算を減らそうとします。

ハッシュ値の計算では、テキストの固定幅ウィンドウ（この場合はwidth = length of pattern）を維持し、そのウィンドウを1文字ずつ1文字ずつ移動して更新する、rolling hashを使用します。前処理段階では

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 A = 97、B = 98、R = 114

ハッシュ（ "ABR"）=（97×1012）+（98×1011 ）+（114×1010）=テキストのs番目のウィンドウにパターンを比較した後、相を合わせて999509

（場合ハッシュPの値とTのs番目のウィンドウが等しい）、我々はハッシュを更新する必要がTのの（s + 1）番目のウィンドウを表す値は、最初にlasの最初の文字のハッシュ値を減算します次の文字のハッシュ値を加算し、その結果、1文字分先に移動させます。ウィキペディアから

：

は、ハッシュ関数を転がすだけ ストリング内の各文字の値を追加します。数を減算することによって、「ABR」のハッシュから、我々は、その後、次のサブストリング、「ブラ」のハッシュを計算することができるs[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

：このローリングハッシュ式は、一定時間内の前の値から次のハッシュ値 を計算することができます「（

  base old hash old 'a'  new 'a' 

ハッシュ：そう同様すなわち97×1010、ベースを掛けると「ブラ」の最後のために添加すること、すなわち、97×1012「ABR」の最初の「A」のために添加ブラジャー）= [101×（999,509 - （97×1012））] +（97×1010）= 1,011,309

の

備考：

(int)text.charAt(s) - 97：97文字のASCIIコードである ''、そう等、この操作の変更 '' 0、1 'B'