2次記憶上のダブル配列の効率的検索法

概要

論文の詳細を見る
自然言語処理における辞書の検索手法として,トライ法が広く使われており,トライ法を表現するデータ構造としては,ダブル配列法が検索の高速性とコンパクト性において非常に優れている.しかし,ダブル配列を主記憶におくことは,高速検索に有効であるが,格納キー数が多くなると,ダブル配列のサイズが大きくなる.そこで,本論文では,ダブル配列を分割して2次記憶上に格納することにより,少ない主記憶領域でも効率的に検索でき,更に記憶量も圧縮できる分割ダブル配列法を提案する.しかし,本手法では,分割されたトライをたどらなければならなくなるので,2次記憶のアクセス回数の増加が問題となる.この問題に対して,分割トライをたどる回数を少なくする手法を提案し,ダブル配列の高速性を保持した.7万〜23万のキーに対する実験を行った結果,一つのキーに対する検索時の2次記憶のアクセス回数が2回以下となり,分割トライの記憶容量は分割なしの場合に比べて約50%に圧縮されることがわかった.
社団法人電子情報通信学会の論文
2002-11-01