0

複数のハッシュを使用して、特定のテキスト文字列のパターンを一致させる方法を学ぼうとしていました。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? 
        }

    }
}

問題は次のとおりです。コードでコメントアウトした上記のコードの一部の行を理解できません。それらの行で実際に何が行われたのでしょうか?

4

1 に答える 1

2

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

ハッシュ値を計算するために、テキストの固定幅ウィンドウ (この場合は ) を維持するローリング ハッシュwidth = length of patternを使用し、そのウィンドウを一度に 1 文字ずつ移動して更新します。

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 番目の文字のハッシュ値を計算します。

ウィキペディアの例:

// アスキー a = 97、b = 98、r = 114。

hash("abr") = (97 × 1012) + (98 × 1011) + (114 × 1010) = 999,509

パターンをテキストの s 番目のウィンドウと比較した後のマッチング フェーズでは (P のハッシュ値と T の s 番目のウィンドウが等しい場合)、T の (s+1) 番目のウィンドウを表すようにハッシュ値を更新する必要があります(2) t = (d * (t - T[s+1] * h) + T[s+m+1]) % q。最後のウィンドウの最初の文字のハッシュ値を減算し、次の文字のハッシュ値を加算して、ウィンドウを 1 文字進めます。

ウィキペディアから:

ローリング ハッシュ関数は、部分文字列の各文字の値を追加するだけです。このローリング ハッシュ式は、一定時間内に前の値から次のハッシュ値を計算できます。s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

次に、「abr」の最初の「a」に加算された数値、つまり 97 × 1012 を減算し、基数を掛けて加算することにより、「abr」のハッシュから次の部分文字列「bra」のハッシュを計算できます。 「bra」の最後の a、つまり 97 × 1010。

           base  old hash  old 'a'     new 'a'

hash("ブラジャー") = [101 × (999,509 - (97 × 1012))] + (97 × 1010) = 1,011,309

備考:

(int)text.charAt(s) - 97: 97 は文字 'a' の ASCII コードであるため、この操作は 'a' を 0 に、'b' を 1 に、というように変更します。

于 2016-12-12T05:58:20.117 に答える