読者です 読者をやめる 読者になる 読者になる

LOUDS++(1)

common lisp algorithm

『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

*1:ただし、それらの情報を効率的に取り出すためには補助的なデータ構造が必要となるので、実際のメモリ消費量はもう少し(?)多くなる。また、各ノードに対応する値を保持するためのメモリ領域ももちろん必要。

*2:これらの情報をどうやって取り出すかは、冒頭の論文(or 今後書く予定のブログ記事)を参照

*3:あるノードの子ノードや兄弟ノードを取得したり、ノードの値を取得したり、などなど