著者

馬場 雅大 小野 廣隆 定兼 邦彦 山下 雅史

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2010-AL-129, no.1, pp.1-8, 2010-02-26

---

大規模なデータを効率よく扱うために圧縮されたデータ上で高速な操作を行える簡潔データ構造が提案されてきた.本稿ではパトリシアトライなどに使われる全二分木に焦点を当てる.提案する全二分木の簡潔表現のサイズは n+o(n) ビットであり,右の子へ巡回するといった操作を定数時間で行うことができる.また接尾辞木 (ST) を全二分木に変換することで圧縮可能であることを示す.