全二分木の簡潔な表現

• Item type: SIG Technical Reports(1)
• 公開日: 2010-02-26
• タイトル: 全二分木の簡潔な表現
• タイトル / 言語: en
• タイトル: A succinct representation of a full binary tree
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州大学
• 著者所属: 九州大学
• 著者所属: 国立情報学研究所
• 著者所属: 九州大学
• 著者所属(英): en
• 著者所属(英): Kyushu University
• 著者所属(英): en
• 著者所属(英): Kyushu University
• 著者所属(英): en
• 著者所属(英): National Indtitute for Informatics
• 著者所属(英): en
• 著者所属(英): Kyushu University
• 著者名: 馬場, 雅大; 小野, 廣隆; 定兼, 邦彦; 山下, 雅史
• 著者名(英): Masahiro, Baba; Hirotaka, Ono; Kunihiko, Sadakane; Masafumi, Yamashita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 大規模なデータを効率よく扱うために圧縮されたデータ上で高速な操作を行える簡潔データ構造が提案されてきた．本稿ではパトリシアトライなどに使われる全二分木に焦点を当てる．提案する全二分木の簡潔表現のサイズは n+o(n) ビットであり，右の子へ巡回するといった操作を定数時間で行うことができる．また接尾辞木 (ST) を全二分木に変換することで圧縮可能であることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2010-AL-129, 号 1, p. 1-8, 発行日 2010-02-26
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会