トライ構造を用いた共起情報の効率的検索アルゴリズム

概要

論文の詳細を見る
自然言語辞書に構築される基本語彙は有限であるが, それら基本語の関係を定義することで, 膨大な数の関係情報が作り出される.複合語, 慣用表現, 格関係などもこの関係情報の範疇に属し, これらを基本単語の共起情報と呼ぶ.共起情報を基本単語の並びとして格納すると, 記憶効率が非常に悪くなるので, これら関係情報の効率的な記憶検索技法は重要な課題である.本論文では, 基本単語からなる共起情報をトライ構造で効率的に記憶検索する手法を提案する.本手法では共起情報を構成する2つの基本単語を1つのトライに登録し, 関係情報をトライの葉ノード間のリンク関数で定義する.共起情報の登録による記憶量の増加はこのリンク情報のみとなり, リンク情報もトライに格納する.本手法では, トライのアークを高速にたどる必要があるので, これをO(1)の計算量で実現するダブル配列法を適用する.この結果, 共起情報の検索時間は, 基本単語数や葉ノード間のリンク数に依存しない一定の計算量となった.約10万語の基本単語に対して, 複合語, 同音語判定の共起語, 格構造辞書などの約100万の関係情報を構築した実験結果より, 検索時間は1.2msと一定となること, また記憶量は従来法より1/3に圧縮できることが分かった.
一般社団法人情報処理学会の論文
1998-09-15

トライ構造を用いた共起情報の効率的検索アルゴリズム

スポンサーリンク

概要

著者

関連論文

スポンサーリンク