Predictive Search

自然言語処理 プログラミング

はじめに

先日作ったDouble ArrayにPredictive Searchを追加してみた。

Predictive Searchとは

  • Common Prefix Searchは、入力文の長さまでで共通の接頭辞を持つ部分文字列を列挙した
    • 入力文が「今日は晴れ」なら「今」「今日」「今日は」...が登録されているかを探す
  • Predictive Searchは、入力文を接頭辞に持つ登録されている文字列を列挙する
    • 入力文が「今日は」なら「今日は晴れ」「今日は終わり」など登録されているものを探す
  • Trieで入力文の最後までたどったら、そのノードの子ノードを巡って登録されている文字列を探す

コード

  #include <queue> //追加

  //predictive search
  std::vector<std::string> predictive_search(std::string X){
    X += "#"; //終端文字
    std::vector<std::string> ret;
    std::string prefix = "";
    int index = 1, pos = 0, t;
    while(true){
      if(X[pos]=='#') break; //文字列が終了したので終了
      prefix += X[pos];
      t = forward(index, X[pos]);
      if(t==0) return ret; //木がもう続いてないよ
      index = t;
      pos++;
    }
    //幅優先探索で探す
    std::queue< std::pair<int,std::string> > que;
    que.push(std::make_pair(index,prefix));
    while(!que.empty()){
      std::pair<int,std::string> q = que.front(); que.pop();
      std::vector<char> A = get_label(q.first);
      for(int i=0; i<A.size(); i++){
	int next_index = forward(q.first, A[i]);
	if(next_index != 0){
	  if(A[i] == '#'){
	    ret.push_back(q.second);
	  }else{
	    que.push(std::make_pair(next_index, q.second+A[i]));
	  }
	}
      }
    }
    return ret;
  }

実験

  • 検索サイトのように途中までの入力で候補を出すように試してみる
int main(){
  using namespace std;
  double_array da;

  //辞書
  da.add("のび太の恐竜");
  da.add("のび太の宇宙開拓史");
  da.add("のび太の大魔境");
  da.add("のび太の海底鬼岩城");
  da.add("のび太とアニマル惑星");
  da.add("のび太と雲の王国");
  da.add("のび太とブリキの迷宮");
  da.add("のび太と翼の勇者たち");
  
  //predictive_search
  string str = "のび太と"; //入力文
  
  vector<string> ret = da.predictive_search(str);
  for(int i=0; i<ret.size(); i++){
    cout << ret[i] << endl;
  }
  return 0;
}
  • 結果
    • なんかそれっぽい
$ ./a.out
のび太と雲の王国
のび太とアニマル惑星
のび太とブリキの迷宮
のび太と翼の勇者たち

参考文献