ダブル配列におけるキー削除の効率化手法

概要

論文の詳細を見る
トライ法は自然言語処理システムの辞書を中心として広く用いられているキー検索技法であり,トライを実現するデータ構造に検索の高速性と記憶量のコンパクト性をあわせ持つダブル配列構造がある.ダブル配列構造の欠点は,キーの削除によって生じる未使用要素により空間効率が低下する点である.これに対し森田らはダブル配列を詰め直すことにより未使用要素を除去するキー削除法を提案した.しかし,この手法はすべての未使用要素を除去できないため高い空間効率を維持できず,また削除コストが未使用要素数に依存するので,削除を連続するほど削除速度が低下するという問題がある.本論文では,トライの節のうち兄弟を持たない節が多くの割合を占めること,また,これらの節の遷移は容易に変更できるという特徴を利用し,削除を連続した場合でも空間使用率と削除速度を低下させない効率的なキー削除法を提案する.EDR日英単語辞書,WordNet英単語辞書,日本の郵便番号リスト,各5万件に対する実験より,提案法は削除を連続した場合でもきわめて高い空間使用率を維持することが,また,森田らの削除法より約50〜200倍高速に削除できることが実証された.
2003-05-15