Rabin-Karp法による複数文字列(パターン)検索を試す

はじめに

前から気になっていたRabin-Karp法による複数文字列検索を試しに書いてみた。

ここでいう問題は、「ある長い文字列の中に、複数の探したい部分文字列が含まれるかどうか、含まれる場合そのindexは？」を考える。

Rabin-Karp法

文字列探索するときに、ある部分の文字列が部分文字列と一致するかどうかにハッシュ値を使う方法
ハッシュ値には「ローリングハッシュ法」と呼ばれる、1文字ずらした時のハッシュ値を簡単・高速に求められる方法が使われる
単一の部分文字列検索の場合、他の探索手法(KMP法やBM法)の方が速かったりするので、あまり使われないが、複数の部分文字列検索の場合は効率的に探索できる

アルゴリズムは、
- 探したい長さmの文字列subのハッシュ値を計算
- 文字列strの先頭から長さm分だけハッシュ値を計算
- 一致している場合は見つかったということなので、探索を終了する
- もし一致していない場合は、上記で計算したstrの部分文字列を1文字ずらしたハッシュ値を計算し、一致しているかどうかを繰り返す

ローリングハッシュ法

文字列aについて、ハッシュ値を「( a[0] * B^{m-1} + a[1] * B^{m-2} + ... + a[m-1] * B^0 ) mod H」で計算する
何がよいかというと、文字列aの後ろに1文字追加した場合のハッシュ値が「文字列aのハッシュ値にBをかけて追加した文字の値を足す( ( Hash(a) * B + c ) mod H)」だけで求まる
同様に、「文字列の先頭から1文字消す」操作した場合などもO(1)で求められる

コード

ということで、複数文字列探索する例として、以下で試してみる

文字列str : 「a」が1000万回続いたもの
探す部分文字列集合 : 「a」が1万回続いたものの後ろに10文字適当な文字列が続いたものが1000個
mac book air, Mac OS X 10.7, 1.6GHz Intel Core i5, 2GB 1333MHz DDR3, g++ 4.2.1

#include <iostream>
#include <vector>
#include <map>
#include <string>

typedef unsigned long long ull;

class RabinKarp {
  //MODは2^64(unsigned long long を使えば桁あふれでmodと同じ)
  static const ull B = 100000007ULL;
public:
  //文字列strのハッシュ値を求める
  ull hash(const std::string& str){
    ull ret = 0;
    for(int i=0; i<str.length(); i++){
      ret = ret * B + (char)(str[i]);
    }
    return ret;
  }

  //文字列str中に文字列subが含まれているかどうか(見つかる場合はそのインデックスを返す)
  int find(const std::string& str, const std::string& sub){
    if(str.length() < sub.length()) return false;
    ull t = 1;
    for(int i=0; i<sub.length(); i++) t *= B; //t = B^{sub.length()}
    
    ull sub_hash = hash(sub);
    ull str_sub_hash = 0;
    for(int i=0; i<sub.length(); i++){
      str_sub_hash = str_sub_hash * B + (char)(str[i]);
    }
    
    for(int i=0; i<=str.length()-sub.length(); i++){
      //hash値が一致
      if(str_sub_hash == sub_hash){
	//念のため同じ文字列か確認
	bool issame = true;
	for(int j=0; j<sub.length(); j++){
	  if(sub[j] != str[i+j]){
	    issame = false;
	    break;
	  }
	}
	if(issame) return i; //最初に見つかったstrでのindex
      }
      
      //1文字分ずらしたhash値を計算
      if(i<str.length()-sub.length()){
	str_sub_hash = str_sub_hash * B + str[i+sub.length()] - str[i] * t;
      }
    }
    return -1; //見つからなかった
  }

  //文字列str中に長さmの文字列集合subsetが含まれているかどうか(見つかる場合はそのインデックスを返す)
  int findset(const std::string& str, const std::vector<std::string>& subset, int m){
    if(str.length() < m) return false;

    std::map<ull,std::string> hsubs; //文字列集合subsetのハッシュ値

    ull t = 1;
    for(int i=0; i<m; i++) t *= B; //t = B^m

    //subsetの文字列のハッシュ値を計算
    for(int i=0; i<subset.size(); i++){
      ull sub_hash = hash(subset[i]);
      if(hsubs.count(sub_hash) != 0){
	//簡単のため、subsetに同じハッシュ値を持つものがあったらエラーで終了
	std::cerr << "error: same hash value string exists." << std::endl;
	return -1;
      }
      hsubs[sub_hash] = subset[i];
    }

    ull str_sub_hash = 0;
    for(int i=0; i<m; i++){
      str_sub_hash = str_sub_hash * B + (char)(str[i]);
    }
    
    for(int i=0; i<=str.length()-m; i++){
      //hash値が一致するものがある
      if(hsubs.count(str_sub_hash) != 0){ //【注意】mapは探索O(log n)
	return i; //最初に見つかったstrでのindex
      }
      
      //1文字分ずらしたhash値を計算
      if(i<str.length()-m){
	str_sub_hash = str_sub_hash * B + str[i+m] - str[i] * t;
      }
    }
    return -1; //見つからなかった
  }

  //ナイーブな方法(1:1文字ずつ確認、2:find関数を使って探索)
  int NaiveSearchSet1(const std::string& str, const std::vector<std::string>& subset, int m){
    for(int i=0; i<subset.size(); i++){
      for(int j=0; j<str.length(); j++){
	bool issame = true;
	for(int k=0; k<subset[i].length(); k++){
	  if(str[j+k-1] != subset[i][k]){
	    issame = false;
	    break;
	  }
	}
	if(issame) return j;
      }
    }
    return -1;
  }
  int NaiveSearchSet2(const std::string& str, const std::vector<std::string>& subset, int m){
    int first_find_index = str.length() + 1;

    for(int i=0; i<subset.size(); i++){

      std::string::size_type idx = str.find(subset[i]);
      if(idx != std::string::npos){
	if(first_find_index > (int)(idx)){
	  first_find_index = (int)(idx);
	}
      }
    }
    if(first_find_index > str.length()) return -1;
    return first_find_index;
  }

};


//乱数
// 注意: longではなくint(32bit)にすべき
unsigned long xor128(){
  static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
  unsigned long t;
  t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
//適当な文字列を返す
std::string get_random_text(){
  std::string ret = "";
  for(int i=0; i<10; i++){
    ret += 'a' + xor128() % 26;
  }
  return ret;
}

int main(){

  RabinKarp rk;
  
  //文字列str
  std::string text = "";
  for(int i=0; i<10000000; i++) text += "a";

  //探したい文字列subとその集合
  std::string sub_base = "";
  for(int i=0; i<10000; i++) text += "a";
  std::vector<std::string> subset;

  int add_i = 0;
  while(add_i<1000){
    std::string sub_add = get_random_text(); //10文字追加
    if(sub_add != "aaaaaaaaaa"){
      subset.push_back(sub_base + sub_add);
      add_i++;
    }
  }

  //RabinKarp法で探索
  std::cout << rk.findset(text, subset, 10010) << std::endl;

  //1文字ずつ探索
  //std::cout << rk.NaiveSearchSet1(text, subset, 10010) << std::endl;

  //std::stringのfind関数を使って探索
  //std::cout << rk.NaiveSearchSet2(text, subset, 10010) << std::endl;
  
  return 0;
}

実行結果

実行

$ g++ prog.cc -O2
$ time ./a.out
-1

結果
- RabinKarp(map) : 0.58s
- RabinKarp(unordered_map) : 0.38s
- 1文字ずつ確認 : 2m39s
- find関数を使用 : 11.82s

確かに速いっぽい。。。
まあ、文字列の比較と整数比較なんだから速いのは当たり前だけれども、、
普通に適当にやろうと思うと「find関数で全部チェック」とかだと思うので、それに比べてこれだけ顕著に差がでるならば実装する意義が十分ありそう。

Negative/Positive Thinking

Rabin-Karp法による複数文字列(パターン)検索を試す

はじめに

Rabin-Karp法

ローリングハッシュ法

コード

実行結果

参考文献