構築した辞書を元にAho Corasick法を使ってキーワードを探す - yasuhisa's blog
どのようなときにAho Corasick法が必要か辞書構築した後の応用先(?)の一つとして、辞書を元にした転置インデックスを作ることがあげられる。「どのキーワードがどの文章に登場したか」が一番簡単な転置インデックスだと思うんだけど、今回は登場した文章のどの位置にあったかまで記録したい(例えばリンクを張る時に使いたいから)。転置インデックス作るときは、通常 形態素解析ベース N-gramベース の2種類が主な手法だと思うんだけど、今回はせっかく構築した辞書をもとに転置インデックスを作りたいので、上の2つではうまくできない。かといって、文章とキーワード総当たりとかやっていたら死ぬので、効率のよい方法が必要。そこでAho Corasick法ですよ、奥さん。はてなキーワードへのリンク処理とかに使われたりします。 入力と出力入力と出力を先に紹介しよう。入力は辞書とこんな感じの文章。 <総説誌名>蛋白
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
