構築した辞書を元にAho Corasick法を使ってキーワードを探す

どのようなときにAho Corasick法が必要か

辞書構築した後の応用先(?)の一つとして、辞書を元にした転置インデックスを作ることがあげられる。「どのキーワードがどの文章に登場したか」が一番簡単な転置インデックスだと思うんだけど、今回は登場した文章のどの位置にあったかまで記録したい(例えばリンクを張る時に使いたいから)。転置インデックス作るときは、通常

形態素解析ベース
N-gramベース

の2種類が主な手法だと思うんだけど、今回はせっかく構築した辞書をもとに転置インデックスを作りたいので、上の2つではうまくできない。かといって、文章とキーワード総当たりとかやっていたら死ぬので、効率のよい方法が必要。そこでAho Corasick法ですよ、奥さん。はてなキーワードへのリンク処理とかに使われたりします。

入力と出力

入力と出力を先に紹介しよう。入力は辞書とこんな感じの文章。

<総説誌名>蛋白質核酸酵素　2002年6月号増刊　構造プロテオミクス　蛋白質ネットワークの構造生物学</総説誌名>
<巻>47</巻>
<号>8</号>
<年>2002</年>
<ページ数>1003-1008</ページ数>
<論文種別>Review</論文種別>
<日本語タイトル>植物cDNAからの無細胞蛋白質合成 コムギ胚芽系を用いたシロイヌナズナ蛋白質の網羅的発現 : 第II部 構造プロテオミクスにおける最新技術 1. 網羅的な蛋白質発現</日本語タイトル>
(中略)
15) Netzer, W. J., Harti, U.: Nature, 388, 343 (1997)
16) Alam, S. L., Atkins, J. F., Gestiland, R. F.: Proc. Natl.Acad. Sci. USA, 96, 14177-14179 (1999)
</参考文献>

出力はこんな感じのもの。出現位置(開始オフセットと終了オフセット)と単語自身。

/Users/syou6162/cpp% ./a.out | head -n 20
(14, 19) => 蛋白
(14, 22) => 蛋白質
(23, 28) => 核酸
(26, 28) => 酸
(29, 34) => 酵素
(46, 48) => 月
(67, 87) => プロテオミクス
(82, 87) => クス
(91, 96) => 蛋白
(91, 99) => 蛋白質
(127, 135) => 生物学
(230, 235) => 論文
(243, 248) => Review
(251, 256) => 論文
(265, 270) => 日本
(268, 270) => 本
(287, 292) => 植物
(309, 314) => 細胞
(315, 320) => 蛋白
(315, 323) => 蛋白質

転置インデックスにはなってないけど、この出力があれば転置インデックスはすぐ作れる。

プログラム

プログラム自体はid:naoyaさんのところを参考にしました。まあ、インターンで一回作ってるんだが、そのときの自分のコードは参考にできないくらい汚な(ry。

Aho Corasick 法 - naoyaのはてなダイアリー

C++の例は以下のところにもあったけど、なんとなくshared_ptrを使って自分で書いてみたくなったのでした。

Spaghetti Source - 複数パターン検索 (Aho-Corasick)

#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <queue>
#include <boost/foreach.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/algorithm/string.hpp>

class MachineAC { 
public:
  class State {
  public:
	int id;
	std::map<char, boost::shared_ptr<State> > next_state;
	State(int id) {
	  this->id = id;
	};
	bool has_key(int x) {
	  if (next_state.find(x) != next_state.end()) {
		return true;
	  } else {
		return false;
	  }
	};
  };

  std::vector<boost::shared_ptr<State> > states;
  std::vector<int> failure_link;
  std::vector<std::vector<std::string> > output;
  MachineAC(std::set<std::string> terms) {
	states.push_back(boost::shared_ptr<State>(new State(0)));
	std::vector<std::string> tmp; 
	output.push_back(tmp); // 空vectorを追加
	make_goto(terms);
	make_failure();
  };

  // Trieを構築
  void make_goto(std::set<std::string> terms) {
	BOOST_FOREACH(std::string term, terms) {
	  boost::shared_ptr<State> current(states.at(0));
	  BOOST_FOREACH(char c, term) {
		if(!current->has_key(c)) {
		  boost::shared_ptr<State> new_state(new State(states.size()));
		  current->next_state.insert(std::make_pair(c, new_state));
		  states.push_back(new_state);
		  std::vector<std::string> tmp;
		  output.push_back(tmp);
		}
		current = current->next_state[c];
	  }
	  int s = current->id;
	  output.at(s).push_back(term);
	}
  };
  
  // failure linkを構築
  void make_failure() {
	std::vector<int> failure;
	for(unsigned int i = 0; i < states.size(); i++) {
	  failure.push_back(0); // 全ての状態において、rootにfailure linkを張る
	}
	std::queue<int> queue;
	queue.push(0);

	while(!queue.empty()) {
	  int s = queue.front();
	  queue.pop();

	  std::pair<char, boost::shared_ptr<State> > p;
	  BOOST_FOREACH(p, states[s]->next_state) {
		char c = p.first;
		int next_node_id = g(s, c);
		if (next_node_id != -1) {
		  queue.push(next_node_id);
		}
		if (s != 0) {
		  int f = failure[s];
		  while(g(f, c) == -1) {
			f = failure[f];
		  }
		  failure[next_node_id] = g(f, c);
		  output[next_node_id].insert(output[next_node_id].end(),
							   output[failure[next_node_id]].begin(), 
							   output[failure[next_node_id]].end());
		}
	  }
	}
	failure_link = failure;
  };
  
  int g(int s, char c) {
	if(states[s]->next_state.count(c) != 0) {
	  return states[s]->next_state[c]->id;
	} else {
	  if (s == 0) {
		return 0;
	  } else {
		return -1;
	  }
	}
  };

  void match(std::string query) {
	int s = 0;
	for(unsigned int i = 0; i < query.size(); i++) {
	  while(g(s, query[i]) == -1) {
		s = failure_link[s];
	  }
	  s = g(s, query[i]);
	  BOOST_FOREACH(std::string x, output[s]) {
		std::cout << "(" << i - x.size() + 1 << ", " << i << ") => " << x << std::endl;
	  }
	}
  };
};

int main(int argc, char *argv[]) {
  std::set<std::string> dic;
  std::ifstream umls_file("/Users/syou6162/dbcls/umls/umls.txt");
  std::string umls_word;
  while (getline(umls_file, umls_word)) {
	umls_word = boost::algorithm::trim_right_copy(umls_word); // 右側の空白除去
	dic.insert(umls_word);
  }
  
  MachineAC ac(dic);

  std::ifstream pne_file("/Users/syou6162/dbcls/pne2/2002/1003_47_2002.txt");
  std::string pne;
  std::string line;
  while (getline(pne_file, line)) {
	pne += line;
  }

  ac.match(pne);

  return 0;
}