簡単なラティス構築とビタビアルゴリズム

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

はじめに

雑誌に簡単なラティス構築とビタビアルゴリズムについて書かれていたので、参考にしてc++で書いてみた。
実際のコスト値などはいれてない。。。

説明

  • 入力文に対し、部分文字列に対し辞書引きをして、ノードとする
    • エッジは文字列上で隣接している場合のみそのノード間をつなぐ
  • 文頭(BOS)、文末(EOS)という特殊なノードを追加し、グラフ(ラティス構造)を作成
  • 各ノードおよびエッジにはコストが定められており、BOSからEOSまでのパスで、通ったノード・エッジの総コストが最小なものを選ぶ
    • DP(ビタビアルゴリズム)で各頂点までの最小コストを保持すればいい

コード

  • 以下、[TODO]で変更すべき点をコメントしとく
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

const static int COST_MAX = 100000000;

//グラフの頂点を表す構造体([TODO]読み、品詞などの情報を追加)
struct NODE {
  int start_pos;
  std::string word;
  int score;
  NODE* prev;
  NODE(int start_pos, std::string word):start_pos(start_pos),word(word){
    score = 0;
    prev = NULL;
  }
};

//辞書引き([TODO]double arrayなどで探す)
std::vector<std::string> dic_lookup(const std::string & word){
  std::vector<std::string> ret; //[TODO]読みや品詞の情報付きで返すようにする
  if(word=="子猫") ret.push_back("子猫");
  if(word=="猫") ret.push_back("猫");
  if(word=="が") ret.push_back("が");
  if(word=="もふ") ret.push_back("もふ");
  if(word=="もふもふ") ret.push_back("もふもふ");
  if(word=="して") ret.push_back("して");
  if(word=="してい") ret.push_back("してい");
  if(word=="いる") ret.push_back("いる");
  return ret;
}

//ラティス構造を作成([TODO]common prefix searchなどで効率的に構築)
std::vector< std::vector<NODE> > graph_construct(const std::string& str){
  std::vector< std::vector<NODE> > graph(str.length()+2, std::vector<NODE>());
  graph[0].push_back(NODE(0,"BOS"));
  graph[str.length()+1].push_back(NODE(str.length()+1,"EOS"));
  
  for(int i=0; i<str.length(); i++){
    for(int j=i+1; j<str.length()+1; j++){
      std::string sbstr = str.substr(i,j-i);
      std::vector<std::string> hret = dic_lookup(sbstr);
      for(int k=0; k<hret.size(); k++){
	graph[j].push_back(NODE(i+1,hret[k]));
      }
    }
  }
  return graph;
}

//nodeの生起コスト
int get_node_cost(NODE &node){
  return 0; //[TODO]コストを与える
}

//node_aからnode_bへの連接コスト
int get_edge_cost(NODE &node_a, NODE &node_b){
  return 0; //[TODO]コストを与える
}

//ビタビアルゴリズムによるコスト最小法
std::vector<std::string> viterbi(std::vector< std::vector<NODE> > &graph){
  int n = graph.size();
  for(int i=1; i<n; i++){
    for(int j=0; j<graph[i].size(); j++){  
      int node_cost = get_node_cost(graph[i][j]);
      int cost = COST_MAX;
      NODE *shortest_prev = NULL;

      if(graph[graph[i][j].start_pos-1].size()==0) continue;
      for(int k=0; k<graph[graph[i][j].start_pos-1].size(); k++){
	int edge_cost = get_edge_cost(graph[graph[i][j].start_pos-1][k], graph[i][j]);
	//int tmp_cost = get_node_cost(graph[graph[i][j].start_pos-1][k]) + edge_cost + node_cost; //これは誤り
	int tmp_cost = graph[graph[i][j].start_pos-1][k].score + edge_cost + node_cost; //修正(2017/8/19): コメントを参照
	if(tmp_cost < cost){
	  cost = tmp_cost;
	  shortest_prev = &graph[graph[i][j].start_pos-1][k];
	}
      }
      graph[i][j].prev = shortest_prev;
      graph[i][j].score = cost;
    }
  }
  NODE *node = &graph[n-1][0]; //EOS
  std::vector<std::string> ret;
  while(node->word != "BOS"){
    ret.push_back(node->word);
    node = node->prev;
    if(node == NULL) return std::vector<std::string>(); //失敗
  }
  std::reverse(ret.begin(), ret.end());
  return ret;
}

int main(){
  using namespace std;

  //ラティスを作成
  vector< vector<NODE> > graph = graph_construct("猫がもふもふしている");

  //ビタビアルゴリズムでコストが最小となるパスを検索
  vector<string> ret = viterbi(graph);

  //結果の表示
  for(int i=0; i<ret.size(); i++){
    cout << ret[i] << endl;
  }

  return 0;
}

実行結果

$ ./a.out
猫
が
もふもふ
して
いる
EOS

参考文献

追記(2017/8/19)

作成されるグラフ(ラティス構造)は以下のようなもの。

viterbi()関数の最初の3重ループの中は以下のようになっている。

注目しているノードgraph[i][j](図の緑ノード)について、そのノードにつながっている一つ前の各ノードgraph[graph[i][j].start_pos-1][k](図の左側ノードのどれか)を通った場合の総コスト(tmp_cost)を計算し、最後にそのなかで最小の総コスト(cost)をノードgraph[i][j].scoreに保存しておく。

ひとつ前のノードでの最小の総コスト(graph[graph[i][j].start_pos-1][k].score)がわかっていれば、そのノードを通って注目しているノードgraph[i][j]に来た場合の総コスト(tmp_cost)は、それにgraph[i][j]へのエッジのコストとgraph[i][j]のノードのコストを足すことで計算することができる。

最後に、EOSのノードでの最小総コストを確認すれば、BOSからEOSまでの最小総コストがわかり、どこを通ったか(各ノードのprev)をEOSから逆にたどれば最小総コストになる経路を復元できる。