Negative/Positive Thinking

2011-10-25

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

はじめに

雑誌に簡単なラティス構築とビタビアルゴリズムについて書かれていたので、参考にして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;
	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

参考文献

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/jetbead/20111025/1319499732