Common Prefix Search

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

はじめに

先日作成したDoubleArrayに共通接頭辞検索機能を追加してみた。

共通接頭辞検索とは

  • ある文字列の接頭辞(「今日のご飯」という文字列なら「今」「今日」「今日の」...)について、それが辞書に含まれるかどうかを検索すること
  • Trie(DoubleArray)やAC法などでは効率的にこの検索を行うことができる
  • 形態素解析器やはてなのキーワードリンクに利用されている

コード

  //共通接頭辞検索
  std::vector<std::string> common_prefix_search(std::string X){
    X += "#"; //終端文字
    std::vector<std::string> ret;
    std::string prefix = "";
    int index = 1, pos = 0, t;
    while(true){
      if(forward(index, '#')!=0){ //今の位置までの文字列が見つかった
        ret.push_back(prefix);
      }
      if(X[pos]=='#') break; //文字列が終了したので終了
      prefix += X[pos];
      t = forward(index, X[pos]);
      if(t==0) break; //木がもう続いてないよ
      index = t;
      pos++;
    }
    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("アレはアレ");
  
  //共通接頭辞検索
  string str = "今日の天気はアレ"; //入力文
  string sp = ""; //位置合わせ用スペース
  cout << str << endl;
  cout << "================" << endl;

  for(int pos=0; pos<str.length(); pos+=3){ //UTF-8なので3byte分シフト
    vector<string> ret = da.common_prefix_search(str.substr(pos));
    for(int i=0; i<ret.size(); i++){
      cout << sp << ret[i] << endl;
    }
    sp += "　";
  }

  return 0;
}
  • 実行結果
    • なんかそれっぽい
$ ./a.exe
今日の天気はアレ
================
今
今日
今日の天気
　　　天気
　　　天気は
　　　　　　アレ

参考文献