望月 久稔

LR 構文解析は，C 言語や Pascal などのプログラミング言語，SQL などの問合せ言語，XML パーサ，プロトコルパーサなどの様々な場面で利用されており，時間的，領域的に効率的な LR 構文解析表の実現が求められる．本論文では，ダブル配列の遷移を拡張して LR 構文解析表を実現し，解析時の状態遷移に要する計算量を抑制することで，LR 構文解析に要する時間を短縮する手法を提案する．実験の結果，提案手法は構文解析器生成系の一種である Bison と比較して LR 構文解析に要する時間を 10～23% 削減した．LR parsers are used widely, such as programing language compilers, SQL parsers, XML parsers, and protocol parsers. So it is important to implement efficient LR parsing tables. In this paper, we present an efficient implementation of LR parsing table with Double-Array that is extended transition function. Our experiment show that proposal method can decrease the parsing time about 10～23% in comparison with parser generator Bison.

自然言語処理における辞書構造として，トライ法が広く用いられているが，日本語のように分かち書きされていない言語のテキストからキーワードを検出するためには，解析対象となるテキストのあらゆる位置から探索する必要がある．より高速に形態素解析を行うため，複数のキーワードをテキストから線形時間で検出する 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.