情報処理学会 第77回全国大会講演要旨

高速な探索手法であるトライ木を実装するデータ構造としてダブル配列がある．ダブル配列は同じキー集合を登録しても，節点の配置順序や，衝突した節点の再配置方法により異なる構造をとり得る．このダブル配列の構造と探索性能との間に関係があると考えて，トライ木でキーを探索する際，比較的頻繁に使用する節点に着目して，トライ木上での深さに基づいて節点を配置する構築手法を提案する．構造を評価する指標として遷移距離を定義し，これを抑制することで探索時間の短縮をはかる．探索時間と遷移距離の相関を評価する．また，構築時間と探索時間について他の構築手法と比較する．