| 講演抄録／キーワード |
| 講演名 |
2006-09-26 15:40
順序木の新しい表現法
Jesper Jansson・○定兼邦彦（九大）・Wing-Kin Sung（NUS） |
| 抄録 |
（和） |
順序木を表現する簡潔データ構造として有名なものは2つ存在する．
BP (balanced parenthesis) [Munro, Raman 2001] と DFUDS (depth first
unary degree sequence) [Benoit et al. 2005] である．
これらは $n$ ノードの木を $2n+\order(n)$ ビットで表現するものであり，
この大きさは情報理論的下界と一致する．
これらのデータ構造の上では多くの基本的演算 (親, 最初の子, 次の弟)への移動，
子孫の数など) を word RAM モデル上で定数時間で行える．
しかし知られている基本的演算の全てを定数時間で行えるデータ構造は
知られていない．BPでは $i$ 番目の子を求めることができず，
DFUDSでは {\lca} (lowest common ancestor) を求めることができない．
本論文は，BPまたはDFUDSで実行できる基本的操作の全てを定数時間で実行可能な
新しい順序木の表現法を提案する．
このデータ構造のサイズは $2n$ ビットより小さく，
木のノードの次数の分布から定義されるエントロピーまで圧縮できる．
その結果，全ての内部ノードがちょうど2つの子を持つような木の場合，
サイズは $n+\order(n)$ まで圧縮される． |
| （英） |
There exist two well-known succinct representations of ordered trees:
BP (balanced parenthesis) [Munro, Raman 2001] and DFUDS (depth first
unary degree sequence) [Benoit et al. 2005].
Both have size $2n+\order(n)$ bits for $n$-node trees, which matches
the information-theoretic lower bound.
Many fundamental operations on trees
can be done in constant time on word RAM, for example finding parent,
the first child, next sibling, the number of descendants, etc.
However there has been no single representation supporting every existing
operation in constant time; BP does not support $i$-th child,
while DFUDS does not support {\lca} (lowest common ancestor).
In this paper, we give the first succinct tree representation supporting
every one of the fundamental operations previously proposed for BP or DFUDS
along with some new operations in constant time.
Moreover, its size surpasses the
information-theoretic lower bound and matches the entropy
of the tree based on the distribution of node degrees.
We call this an ultra-succinct data structure.
As a consequence, a tree in which every internal node has exactly two children
can be represented in $n+\order(n)$ bits. |
| キーワード |
（和） |
簡潔データ構造 / エントロピー / 順序木 / / / / / |
| （英） |
succinct data structures / entropy / ordered trees / / / / / |
| 文献情報 |
信学技報, vol. 106, no. 258, COMP2006-29, pp. 31-37, 2006年9月. |
| 資料番号 |
COMP2006-29 |
| 発行日 |
2006-09-19 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
COMP |
| 開催期間 |
2006-09-26 - 2006-09-26 |
| 開催地（和） |
北陸先端科学技術大学院大学 |
| 開催地（英） |
JAIST |
| テーマ（和） |
|
| テーマ（英） |
|
| 講演論文情報の詳細 |
| 申込み研究会 |
COMP |
| 会議コード |
2006-09-COMP |
| 本文の言語 |
日本語 |
| タイトル（和） |
順序木の新しい表現法 |
| サブタイトル（和） |
|
| タイトル（英） |
A New Representation of Ordered Trees |
| サブタイトル（英） |
|
| キーワード(1)（和/英） |
簡潔データ構造 / succinct data structures |
| キーワード(2)（和/英） |
エントロピー / entropy |
| キーワード(3)（和/英） |
順序木 / ordered trees |
| キーワード(4)（和/英） |
/ |
| キーワード(5)（和/英） |
/ |
| キーワード(6)（和/英） |
/ |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
Jesper Jansson / Jesper Jansson / |
| 第1著者 所属（和/英） |
九州大学 (略称： 九大)
Kyushu University (略称： Kyushu Univ.) |
| 第2著者 氏名（和/英/ヨミ） |
定兼 邦彦 / Kunihiko Sadakane / サダカネ クニヒコ |
| 第2著者 所属（和/英） |
九州大学 (略称： 九大)
Kyushu University (略称： Kyushu Univ.) |
| 第3著者 氏名（和/英/ヨミ） |
Wing-Kin Sung / Wing-Kin Sung / |
| 第3著者 所属（和/英） |
National University of Singapore (略称： NUS)
National University of Singapore (略称： NUS) |
| 第4著者 氏名（和/英/ヨミ） |
/ / |
| 第4著者 所属（和/英） |
(略称： )
(略称： ) |
| 第5著者 氏名（和/英/ヨミ） |
/ / |
| 第5著者 所属（和/英） |
(略称： )
(略称： ) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第2著者 |
| 発表日時 |
2006-09-26 15:40:00 |
| 発表時間 |
35分 |
| 申込先研究会 |
COMP |
| 資料番号 |
COMP2006-29 |
| 巻番号（vol） |
vol.106 |
| 号番号（no） |
no.258 |
| ページ範囲 |
pp.31-37 |
| ページ数 |
7 |
| 発行日 |
2006-09-19 (COMP) |
|