著者

森田 和宏 望月久稔 山川 善弘 青江 順一

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.39, no.9, pp.2563-2571, 1998-09-15

---

自然言語辞書に構築される基本語彙は有限であるが,それら基本語の関係を定義することで,膨大な数の関係情報が作り出される.複合語,慣用表現,格関係などもこの関係情報の範疇に属し,これらを基本単語の共起情報と呼ぶ.共起情報を基本単語の並びとして格納すると,記憶効率が非常に悪くなるので,これら関係情報の効率的な記憶検索技法は重要な課題である.本論文では,基本単語からなる共起情報をトライ構造で効率的に記憶検索する手法を提案する.本手法では共起情報を構成する2つの基本単語を1つのトライに登録し,関係情報をトライの葉ノード間のリンク関数で定義する.共起情報の登録による記憶量の増加はこのリンク情報のみとなり,リンク情報もトライに格納する.本手法では,トライのアークを高速にたどる必要があるので,これをO(1)の計算量で実現するダブル配列法を適用する.この結果,共起情報の検索時間は,基本単語数や葉ノード間のリンク数に依存しない一定の計算量となった.約10万語の基本単語に対して,複合語,同音語判定の共起語,格構造辞書などの約100万の関係情報を構築した実験結果より,検索時間は1.2msと一定となること,また記憶量は従来法より1/3に圧縮できることが分かった.Collocational information is very useful for natural language processing systems and it includes compound words,cooccurrency words,verbs and the role of nouns in the case slot,and so on.Collocational information can be constructed by combining basic words infinitely,so it is important to propose a fast and compact structure representing them.This paper presents an efficient data structure by introducing a trie that can define the linkage among leaves.It enables us to decrease the amount of memory required for the same basic words.Theoretical observations show that the worst-case time complexity of retrieving collocational information is a constant,independent of the number of words and linkages.From the simulation results for collocational information,it is shown that the presented method is about 1/3 smaller than that of the competitive methods.