著者

神田 峻介 泓田 正雄 森田 和宏 青江 順一

雑誌

研究報告情報基礎とアクセス技術(IFAT) (ISSN:21888884)

巻号頁・発行日

vol.2015-IFAT-119, no.10, pp.1-6, 2015-07-29

---

トライと呼ばれる順序木を効率的に表現するデータ構造として,高速な検索を提供するダブル配列がある.また,データの大規模化に伴いコンパクト性が重視される背景に応じて,様々なダブル配列の圧縮表現が提案されてきた.しかし,これらの圧縮表現は,トライにおける順方向の遷移 (親から子) のみを提供し,逆方向の遷移 (子から親) を提供していないため,結果としてダブル配列における逆引きや動的更新を犠牲にしている.本論文では,逆方向遷移を可能としたコンパクトな配列構造を提案する.記憶量について,ダブル配列の約 36%でトライを表現可能なことが実験により確認されている.