著者

蔵満 琢麻 望月 久稔

出版者

情報処理学会

雑誌

情報処理学会論文誌データベース(TOD) (ISSN:18827799)

巻号頁・発行日

vol.2, no.2, pp.96-109, 2009-06-29

---

自然言語処理における辞書構造として,トライ法が広く用いられているが,日本語のように分かち書きされていない言語のテキストからキーワードを検出するためには,解析対象となるテキストのあらゆる位置から探索する必要がある.より高速に形態素解析を行うため,複数のキーワードをテキストから線形時間で検出する AC 法を用いる手法が提案されているが,AC 法はトライ法よりも使用する記憶領域が大きい.本論文では,AC マシンにおける遷移のうち,多分岐の節点における遷移をダブル配列に,1 方向分岐の節点における遷移をダブル配列と異なる配列にそれぞれ定義することで,照合時に必要な記憶領域を抑制し,高速性とコンパクト性をあわせ持つ AC マシンを実現する手法を提案する.日本語形態素 40 万語を登録した実験で,提案手法はトライを用いた辞書システム Darts とほぼ同等の記憶領域で対象テキストを 60~87% の時間で照合した.Trie structure is used widely, such as dictionary for natural language processing. However, it is not so effective using a trie structure for the morphological analysis of languages without explicit word boundaries like Japanese because we have to perform dictionary lookup for all possible substrings of the text. This paper proposes an efficient dictionary structure that is Aho-Corasick Machine using Double-array defining multi-way branch and different arrays defining oneway branch. Our experiments show that the matching time of the proposal machine decreased to about 60%-87% against other structures.