2026-03-09T00:44:27Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00068031 2025-01-22T00:23:20Z 1164:2592:5970:6032

全二分木の簡潔な表現 A succinct representation of a full binary tree 馬場, 雅大 小野, 廣隆 定兼, 邦彦 山下, 雅史 Masahiro, Baba Hirotaka, Ono Kunihiko, Sadakane Masafumi, Yamashita 大規模なデータを効率よく扱うために圧縮されたデータ上で高速な操作を行える簡潔データ構造が提案されてきた．本稿ではパトリシアトライなどに使われる全二分木に焦点を当てる．提案する全二分木の簡潔表現のサイズは n+o(n) ビットであり，右の子へ巡回するといった操作を定数時間で行うことができる．また接尾辞木 (ST) を全二分木に変換することで圧縮可能であることを示す． To take large-scale data efficiently, succinct data structures that support highspeed operations on compressed data have been developed. In this paper, we focus on full binary trees which are used as patricia tries. We propose for a succinct data structure whose size is n+o(n) bits. This representation enables constant time operations such as traversing from a internal node to its right child node. Then, we show that a suffix tree (ST) is compressible by converting it to a full binary tree. technical report 情報処理学会 2010-02-26 application/pdf 研究報告アルゴリズム（AL） 1 2010-AL-129 1 8 AN1009593X https://ipsj.ixsq.nii.ac.jp/record/68031/files/IPSJ-AL10129001.pdf jpn