2026-03-12T05:28:05Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00144526 2025-01-20T18:46:26Z 1164:3500:7866:8310

トライにおける逆方向遷移可能かつコンパクトな配列構造 A Compact Array Structure with Reverse Traversal in a Trie 神田, 峻介 泓田, 正雄 森田, 和宏 青江, 順一 Shunsuke, Kanda Masao, Fuketa Kazuhiro, Morita Jun-ichi, Aoe アルゴリズム トライと呼ばれる順序木を効率的に表現するデータ構造として，高速な検索を提供するダブル配列がある．また，データの大規模化に伴いコンパクト性が重視される背景に応じて，様々なダブル配列の圧縮表現が提案されてきた．しかし，これらの圧縮表現は，トライにおける順方向の遷移 （親から子） のみを提供し，逆方向の遷移 （子から親） を提供していないため，結果としてダブル配列における逆引きや動的更新を犠牲にしている．本論文では，逆方向遷移を可能としたコンパクトな配列構造を提案する．記憶量について，ダブル配列の約 36%でトライを表現可能なことが実験により確認されている． A double-array efficiently represents an ordered tree called “trie”, and provides fast retrieval in the trie. Recently, many compact representations of the double-array have been proposed because a compact data structure is important in big data. The double-array provides inorder (from a parent to a child) and reverse (from a child to a parent) traversals, but the compact representations provide only the inorder traversal. Therefore, the compact representations don't have a dynamic update and a reverse lookup in the double-array. This paper proposes a compact array structure with the reverse traversal. In addition, experimental results show that the new structure represents the trie with 36% of the double-array size. 情報処理学会 2015-07-29 jpn technical report https://ipsj.ixsq.nii.ac.jp/records/144526 2188-8884 AN10114171 研究報告情報基礎とアクセス技術（IFAT） 2015-IFAT-119 10 1 6 https://ipsj.ixsq.nii.ac.jp/record/144526/files/IPSJ-IFAT15119010.pdf application/pdf 451.6 kB 2017-07-29