Karp-Rabin Algorithm

今日はKarp-Rabinの文字列アルゴリズム（通称KR法）について。

Karp-Rabin法は、大量のテキストデータから対象の文字列を検索するアルゴリズムである。

1,000,000文字のテキストから、1,000文字のキーワードを抽出したいシチュエーションを考えよう。

以下のbrute-forceな解法では、1,000,000 * 1,000 = 10^9の計算時間がかかってしまう。

実際に下のコードを実行すると、10秒くらいかかった。

view plainprint?

1. string text;  
2. string target;  
3.   
4. bool doit1() {  
5.   int L = text.length();  
6.   int l = target.length();  
7.   
8.   REP(i, L-l+1) {  
9.       bool ck = true;  
10.       REP(j, l) {  
11.           if (text[i+j] != target[j]) {  
12.               ck = false;  
13.               break;  
14.           }  
15.       }  
16.       if (ck) return true;  
17.   }  
18.   return false;  
19. }  
20.   
21. int main() {  
22.   // case 1  
23.   text.assign(1000000, 'a');  
24.   target.assign(999, 'a');  
25.   target.append("b");  
26.   
27.   cout << doit1() << endl;  
28. }  

string text;
string target;

bool doit1() {
  int L = text.length();
  int l = target.length();

  REP(i, L-l+1) {
      bool ck = true;
      REP(j, l) {
          if (text[i+j] != target[j]) {
              ck = false;
              break;
          }
      }
      if (ck) return true;
  }
  return false;
}

int main() {
  // case 1
  text.assign(1000000, 'a');
  target.assign(999, 'a');
  target.append("b");

  cout << doit1() << endl;
}

Karp-Rabin法では、比較文字列をハッシュ値に変更することで、文字列の比較をO(1)で実施するようにしている。

ここでポイントとなるのは、ハッシュ値の算出方法である。通常、長さlの文字列のハッシュ値を計算するためにはO(l)必要だが、「ローリングハッシュ」とよばれる窓関数のような特性をもったハッシュ関数を用いることでハッシュ値の計算をO(1)で実施することができる。

まずは、簡単なハッシュ関数として文字列内の文字のアスキーコードをすべて足す関数を用いてみる。

view plainprint?

1. bool doit2() {  
2.   int L = text.length();  
3.   int l = target.length();  
4.   
5.   int textH = 0, tarH = 0;  
6.   REP(i, l) {  
7.       textH += text[i];  
8.       tarH += target[i];  
9.   }  
10.   
11.   REP(i, L-l+1) {  
12.       if (textH == tarH) {  
13.           bool ck = true;  
14.           REP(j, l) {  
15.               if (text[i+j] != target[j]) {  
16.                   ck = false;  
17.                   break;  
18.               }  
19.           }  
20.           if (ck) return true;  
21.       }  
22.       textH = textH - text[i] + text[i+l];  
23.   }  
24.   return false;  
25. }  

bool doit2() {
  int L = text.length();
  int l = target.length();

  int textH = 0, tarH = 0;
  REP(i, l) {
      textH += text[i];
      tarH += target[i];
  }

  REP(i, L-l+1) {
      if (textH == tarH) {
          bool ck = true;
          REP(j, l) {
              if (text[i+j] != target[j]) {
                  ck = false;
                  break;
              }
          }
          if (ck) return true;
      }
      textH = textH - text[i] + text[i+l];
  }
  return false;
}

これで、先ほどの例題は、1秒以下で解くことができる。

Karp-Rabin法の弱点は、ハッシュ値の衝突が起きた際に文字列の比較をしなければいけないという点にある。つまり、最悪の場合（ほとんどの場合衝突が起こる場合）の計算量は、brute-forceの場合と変わらない。

例えば、このようなインプットに対しては、先ほどのハッシュ値ではほぼ毎回衝突が起きてしまう。計算時間も約10秒かかってしまった。

view plainprint?

1. int main() {  
2.   // case 2  
3.   text.assign(1000000, 'b');  
4.   target.assign(998, 'b');  
5.   target.append("ac");  
6.   
7.   cout << doit2() << endl;  
8. }  

int main() {
  // case 2
  text.assign(1000000, 'b');
  target.assign(998, 'b');
  target.append("ac");

  cout << doit2() << endl;
}

Karp-Rabin法では、如何にローリングハッシュ関数を決めるかが重要である。例えば、アスキーコードを掛け合わせてハッシュ値を作るというのはいいかもしれない。但し、個の場合、値が非常に大きくなるため適当な素数のMODをハッシュ値として用いなければならない。（また、次の部分文字列のハッシュ値を計算する際、割り算が必要だが割り算は合同式の分配法則は成り立たないので工夫が必要である。）以下にサンプルソースを記載する。この場合は、上記のサンプルでも1秒程度で計算できた。

view plainprint?

1. bool doit3() {  
2.    const int MOD = 1000007;  
3.    int L = text.length();  
4.    int l = target.length();  
5.   
6.    int textH = 1, tarH = 1;  
7.    REP (i, l) {  
8.        textH = textH*text[i]%MOD;  
9.        tarH = tarH*target[i]%MOD;  
10.    }  
11.   
12.    REP(i, L-l+1) {  
13.        if (textH == tarH) {  
14.            bool ck = true;  
15.            REP(j, l) {  
16.                if (text[i+j] != target[j]) {  
17.                    ck = false;  
18.                    break;  
19.                }  
20.            }  
21.            if (ck) return true;  
22.        }  
23.        while (textH % text[i])  
24.            textH += MOD;  
25.        textH = (textH/text[i]*text[i+l]) % MOD;  
26.    }  
27.    return false;  
28. }  

bool doit3() {
   const int MOD = 1000007;
   int L = text.length();
   int l = target.length();

   int textH = 1, tarH = 1;
   REP (i, l) {
       textH = textH*text[i]%MOD;
       tarH = tarH*target[i]%MOD;
   }

   REP(i, L-l+1) {
       if (textH == tarH) {
           bool ck = true;
           REP(j, l) {
               if (text[i+j] != target[j]) {
                   ck = false;
                   break;
               }
           }
           if (ck) return true;
       }
       while (textH % text[i])
           textH += MOD;
       textH = (textH/text[i]*text[i+l]) % MOD;
   }
   return false;
}

※合同式の割り算の部分のwhile()が何回くらい実行されるのか気になるが、最大でもtext[i]回である。ほぼ定数オーダーと考えていいと思う。