D-010
関数辞書を用いたダブル配列の圧縮手法

◎土井優太・森田和宏・泓田正雄（徳島大）

トライ法は，自然言語を中心に広く用いられるキー検索法であり，トライ法を実現するデータ構造として，二つの一次元配列を用いるダブル配列がある．ダブル配列は，トライ法で必要となる遷移処理を二つの式で実行できるため高速だが，遷移処理を高速に行うためのランダムアクセスに必要な情報を各配列に格納している．したがって，遠くの配列要素にアクセスする際には，大きな値を格納する必要があるため，ダブル配列全体の記憶効率は低下する．本稿では，遷移処理の際に関数辞書を経由する事で，ダブル配列の各要素に格納する値の記憶領域を圧縮する手法を提案する．