LOUDS++(1)
『Enginnering the LOUDS Succinct Tree Representaion*』という論文に目を通し終わったので、(まだ理解はしていないが)これから実装に入る。
現状での理解は次のような感じ。
- Level-Order Unary Degree Sequenceの略
- 順序木の表現方法の一つ。静的構築。サイズ効率が極めて良い。
- LOUDS++は、オリジナル(?)のLOUDSの改良版。
順序木のビット表現
LOUDSは、N個のノードを持つ順序木のノード間の親子兄弟関係を2N+1ビットで表現可能*1。
以下は、リストによって表現された木を、LOUDSのビット表現(LBS = LOUDS bit string)に変換する例。
;; 上記論文のFig.2の木のリスト表現(の一つ) ;; (ノード名 子ツリー ...)形式 (defvar *tree* '(:a (:b) (:c (:f) (:g (:i))) (:d) (:e (:h)))) --> *TREE* ;; リスト表現の木からLBSを作成する ;; 作成方法(ビット列へのエンコード方法)の概要は以下の通り ;; - 対象となる木に、仮想的なルートノードを追加する ;; - 子ノードの数だけ1をビット列に追加する ;; - 最後に0を追加する ;; - それを全てのノード(ツリー)に対して繰り返す ;; - level-order(レベル順、幅優先探索)で (defun tree-to-lbs (tree) (coerce (loop WITH tree-que = `((:super-root ,tree)) ; 仮想的なルートノードを追加する WHILE tree-que APPEND (destructuring-bind ((node-name . children) . rest-trees) tree-que (declare (ignore node-name)) (setf tree-que (append rest-trees children)) (append (loop REPEAT (length children) COLLECT 1) ; 子ノードの数だけ1を追加する '(0)))) ; 最後は0で区切る 'bit-vector))
;; 適用結果 (tree-to-lbs *tree*) --> #*1011110011001001000
ビット列へのエンコード形式自体は結構直截的。
ツリーの親子兄弟関係を保持する*2上記ビット列の他に、ノード名やその他任意の値を保持するための配列を用意すれば、一応木として機能的な要件*3は満たすことになる。
ただし、このビット列をそのまま使うと、木に関する各種操作が(多分極めて)遅くなってしまうので、LOUDS(LOUDS++)では、ビット列の実装方法を工夫したり、補助的なデータ構造を用意したり、といったことを行っている(と思う)。
追記(2010/05/21): tree-to-lbs関数修正
上で定義したtree-to-lbs関数を少し修正。
各ノードの名前もレベル順に集めて、返すようにする。
(defun tree-to-lbs (tree &aux names) (values (coerce (loop WITH tree-que = `((:super-root ,tree)) WHILE tree-que APPEND (destructuring-bind ((node-name . children) . rest-trees) tree-que (push node-name names) ; ノード名も集める (setf tree-que (append rest-trees children)) (append (loop REPEAT (length children) COLLECT 1) '(0)))) 'bit-vector) (coerce (reverse names) 'vector))) ;;; 例 (tree-to-lbs *tree*) --> #*1011110011001001000 #(:SUPER-ROOT :A :B :C :D :E :F :G :H :I) ;; 上の各ノードの配列内での添字 = ノード番号(ID) ;; ex) ノード:Aの番号(ID)は1、ノード:Dの番号(ID)は4
