順序木の新しい表現法

概要

論文の詳細を見る
順序木を表現する簡潔データ構造として有名なものは2つ存在する.BP (balanced parenthesis) [Munro, Raman 2001]とDFUDS (depth first unary degree sequence) [Benoit et al. 2005]である.これらはnノードの木を2n+o(n)ビットで表現するものであり,この大きさは情報理論的下界と一致する.これらのデータ構造の上では多くの基本的演算(親,最初の子,次の弟)への移動,子孫の数など)をword RAMモデル上で定数時間で行える.しかし知られている基本的演算の全てを定数時間で行えるデータ構造は知られていない.BPではi番目の子を求めることができず,DFUDSではlca(lowest common ancestor)を求めることができない.本論文は,BPまたはDFUDSで実行できる基本的操作の全てを定数時間で実行可能な新しい順序木の表現法を提案する.このデータ構造のサイズは2nビットより小さく,木のノードの次数の分布から定義されるエントロピーまで圧縮できる.その結果,全ての内部ノードがちょうど2つの子を持つような木の場合,サイズはn+o(n)まで圧縮される.
社団法人電子情報通信学会の論文
2006-09-19