全二分木の簡潔な表現 A succinct representation of a full binary tree

この論文にアクセスする

この論文をさがす

著者

抄録

大規模なデータを効率よく扱うために圧縮されたデータ上で高速な操作を行える簡潔データ構造が提案されてきた．本稿ではパトリシアトライなどに使われる全二分木に焦点を当てる．提案する全二分木の簡潔表現のサイズは 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.

収録刊行物

  • 研究報告アルゴリズム（AL）

    研究報告アルゴリズム（AL） 2010-AL-129(1), 1-8, 2010-02-26

    情報処理学会

参考文献:  9件中 1-9件 を表示

各種コード

  • NII論文ID(NAID)
    110007995610
  • NII書誌ID(NCID)
    AN1009593X
  • 本文言語コード
    JPN
  • 資料種別
    Technical Report
  • ISSN
    09196072
  • NDL 記事登録ID
    025055178
  • NDL 請求記号
    YH267-101
  • データ提供元
    CJP書誌  NDL  NII-ELS  IPSJ 
ページトップへ