[B! algorithm][matching] mogwaingのブックマーク

mogwaing id:mogwaing

algorithmとmatchingに関するmogwaingのブックマーク (2)

Spaghetti Source - 複数パターン検索 (Aho-Corasick)
説明複数のパターン文字列からなる集合と長い文字列が与えられる．長い文字列に対してマッチするパターン文字列をすべて求めるアルゴリズムが Aho Corasick である．これは複数パターン文字列をあらかじめ trie に変換してから KMP を実行し，パターンマッチング・オートマトンを構成していることになる．詳しくは適当な成書や http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf などを参考のこと．計算量構築 O(m)．検索 O(n + m)．ただし m はパターンの文字列長の総和，n は検索テキスト長．使い方 struct PMA; を適宜設定のこと． build PMA(char *p[], int m) 0 ... m-1 の複数の検索パターンから，パターンマッチング・オートマトンを構築する． match(c
mogwaing 2009/04/07
algorithm

ac

matching
リンク
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
mogwaing 2009/04/07
ちょうどAhoさんの違う論文読んでた

algorithm

matching
リンク
1