一般の文脈自由文法に対する効率的な並列構文解析

情報処理学会 HANDLE 被引用文献2件 オープンアクセス

書誌事項

タイトル別名
  • An Efficient Parallel Parsing Algorithm for General Contextfree Grammars
  • 自然言語処理

この論文をさがす

抄録

自然言語を解析するためには 構文情報や意味情報 文脈情報など各種の膨大な量の知識情報を用いて処理することが必要であるしかし これらの多量な知識情報を計算機で処理するためには 莫大な解析時間が必要となるため 並列処理などの手法を導入して 解析時間の短縮を計る必要がある一般に文脈自由言語の構文解析には長さが"の入力に対してO(n^2)の手数を必要とするしたがって実時間自然言語理解システムを実現するためには まず文脈自由言語をO(n)時間で解析できる並列構文解析アルゴリズムを開発する必要があるその時 使用するプロセッサ数は実現の可能性上O(n^2)以下であることが望ましいこれまでに並列構文解析のアルゴリズムがいくつか提案されてきたが これらのアルゴリズムには 解析時間やプロセッサ数が多くなりすぎるという問題がある本論文では 一般の文脈自由文法を対象とする並列構文解析アルゴリズムを提案このアルゴリズムの性能は解析時間O(n)・プロセッサ数O(n^2)でその積がO(n^3)である本アルゴリズムでは 一般の文脈自由文法からLR法に類似した手法を用いて作成したLR状態遷移図を解析制御表として使用し すべての可能性を並列に試しながら入力に非同期に解析を行う

収録刊行物

被引用文献 (2)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ