格構造解析における概念階層の効率的判定アルゴリズム

情報処理学会 Web Site 参考文献20件

書誌事項

タイトル別名
  • カクコウゾウ カイセキ ニ オケル ガイネン カイソウ ノ コウリツテキ ハン
  • An Efficient Algorithm for Determining Hierarchical Concepts of Case Structures
  • 自然言語処理

この論文をさがす

抄録

シソーラスに代表される階層化された分類体系は，非常にシンプルな知識表現であり，その応用範囲は非常に広い．特に，自然言語文の格構造解析では，格スロットの制約条件として，この階層化された概念体系（以後概念階層と呼ぶ）による上位と下位関係の判定がよく利用される．しかしながら，階層が深くなり，また解析文が複雑になると，この判定コストが増加するので，判定処理の高速化は重要な課題である．本論文では，概念階層のデータ構造にトライ構造を導入して，判定効率を向上させる手法を提案する．また，本手法では複数の用言の格構造を1つのトライに併合して格納するので，トライ検索後に目的とする用言を効率的に確定する手法も提案する．同音語とEDR1）の共起データに対する実験結果により，格スロットに概念20から96個を列挙する線形格納法に比べて，本手法は6から25倍高速化されることが分かった．また，トライを併合圧縮した記憶量は線形格納法とほぼ同等となり，十分に実用的な結果が得られた．

Case structure is a well-known approach for natural language analysis of Kana-Kanji transformation,machine translation and so on.The case slot is generally restricted by hierarchical concepts,because they are simple knowledge representations.With growing hierarchical structures,the number of concepts increases and the length of numerical codes representing concepts becomes long.The frequency of determinations is very high for complex sentences.Multiple concepts correspond to one word.From these reasons,it costs a lot to determine whether a concept for a given word is a sub-concept for concepts of the case slot or not.This paper presents a fast method for determining the sub-concept relationship by introducing trie structures instead of a sequential storage of concept codes.The worst-case time complexity of the determination process by the presented method remarkably improves the one of the sequential storage,which depends on the number of concepts in the slot.The trie structures can be compressed by merging commom transitions into one trie.From the simulation results,it is shown that the presented algorithm is 6 to 25 times faster than the sequential storage,while keeping a smaller size of tries.

収録刊行物

参考文献 (20)*注記

もっと見る

キーワード

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

問題の指摘

ページトップへ