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

LOUDS++(3): LOUDS++

common lisp algorithm

LOUDS++*1の三回目。
今回は、LOUDSの改良版であるLOUDS++に関する部分。

LOUDS++

LOUDSでは、木をビット列として表現していた。
参照: tree-to-lbs

(defvar *tree* 
  '(:a (:b)
       (:c (:f) 
           (:g (:i))) 
       (:d) 
       (:e (:h))))

(tree-to-lbs *tree*)
--> #*1011110011001001000  ; 木のビット列表現 (LBS = LOUDS bit string)
    #(:SUPER-ROOT :A :B :C :D :E :F :G :H :I)

LOUDS++でもビット列を扱うことに変わりはないが、LBSをさらに二分割している点が異なる。
※分割されてできたビット列は、r0およびr1と呼ばれる。

;; LOUDS++でのビット列表現
;; 詳しく(?)は後述
(partition (tree-to-lbs *tree*))
--> #*1010101001  ; r0
    #*100010111   ; r1

LBSを分割することのメリットは(多分)おおまかには次の二つ。

  • サイズ効率が(かなり?)良くなる
    • 理由:
      • LBSから木の親子兄弟(等の)情報を取り出すためには、ビット配列上でのselectやrankといった操作が必要
      • ただし、select操作は効率的に実装するための(空間的)オーバヘッドが大きい
      • オリジナルのLOUDSでは、select0とselect1の両方を実装する必要があるが、LOUDS++ではselect1のみで良いので、その分スペースを節約できる*2
    • この辺りはビット配列(bit-vector)の実装方法に関わるところなので、今のところはあまり関係ない
  • 子および兄弟ノードの有無の判定が、ビット配列中の一要素を参照するだけで可能
    • isleaf, next-sibling, prev-siblingが高速
    • ただし、first-child, next-child, parentはLOUDSに比べると若干低速

Partition

LBSの分割。
LBSを元に、r0およびr1というビット列を作成する。

;;; r0およびr1の作成方法
;;;
;;; [r0の場合] ※ r1の場合も対象となるビットが0から1に変わる以外は同様
;;; r0は、LBS内での0ビットの出現パターンをエンコードしたもの
;;;  1] LBS内の0ビットを順に辿る
;;;  2] 現在の0ビットの次(右側)が、0ビットの場合はr0に0を追加し、1ビットの場合は1を追加する
;;;  3] 1と2をLBSの末端に辿り付くまで繰り返す
;;;
;;; つまり、r0で位置nのビットの値が0ということは、LBS内でn個目の0ビットとn+1個目の0ビットが連接しているということを表している

;; LBS内のstart以降で、ビット値bitが連続して現れる数を求める。
;; -> (list bitが連続する数 bitの次の出現位置)
(defun run-length (lbs start bit &aux (~bit (logxor 1 bit)))
  (let* ((beg (position  bit lbs :start start))
         (end (position ~bit lbs :start beg)))
    (setf end (or end (length lbs)))
    (list (- end beg)
          (position bit lbs :start end))))

;; LBSを分割して、r0およびr1を作成する
(defun partition (lbs)
  (flet ((rX (bit)
           (loop FOR (length next) = (run-length lbs (or next 0) bit) ; 値がbitのビットが連続する個数を求める
                 FOR 0bits = (loop REPEAT (1- length) COLLECT 0)      ; 連続する数-1だけ、0を集める
                 APPEND `(,@0bits 1)                                  ; 最後に1を追加する
                 WHILE next)))                                        ; ↑をLBSの終端に達するまで繰り返す
    (values (coerce (rX 0) 'bit-vector)    ; r0
            (coerce (rX 1) 'bit-vector)))) ; r1

もともとのLBSでは、0ビットが親ノードを、それに続く1ビットが、その子ノードを表していた。
LOUDS++では、それを二つに分けて、r0で木の親子関係を、r1で木の兄弟関係を表現するようにしている(これは不正確かな...)

;; 番号Nのノードに子がいるかどうか
(bit r0 N) 
=> 0 or 1  ; 1なら子ノード有り

;; 番号Nのノードに兄弟(next-sibling)がいるかどうか
(bit r1 N) 
=> 0 or 1  ; 0なら兄弟(next-sibling)有り

;; N = 下の配列内でのインデックス  (今にして思えば、:super-rootは不要だった)
(subseq (nth-value 1 (tree-to-lbs *tree*)) 1)
--> #(:A :B :C :D :E :F :G :H :I)

;; r0, r1ともに、N個目の1ビットは、N個目の親ノードを表している
(select1 r0 N) ; r0内でのN個目の親ノードの位置。これは、N個目の親のノード番号でもある。
(select1 r1 N) ; r1内でのN個目の親ノードの位置。これに+1すれば、その親の最初の子ノード(の位置=ノード番号)が得られる

各種操作実装

後は、LOUDS++での木に対する各種操作の実装。
まずは構造体定義とそのコンストラクタ

(defstruct louds++ 
  r0     ; r0
  r1     ; r1
  names) ; 各ノードの名前を保持する配列

(defun tree-to-louds++ (tree)
  (multiple-value-bind (lbs names) (tree-to-lbs tree)
    (multiple-value-bind (r0 r1) (partition lbs)
      (make-louds++ :r0 r0
                    :r1 r1
                    :names (subseq names 1)))))

;; ついでに、ノード名取得関数も定義
(defun node-name (node-num louds++)
  (with-slots (names) louds++
    (aref names node-num)))

;;;;;;;
;;; 例
(tree-to-louds++ *tree*)
--> #S(LOUDS++
       :R0 #*1010101001
       :R1 #*100010111
       :NAMES #(:A :B :C :D :E :F :G :H :I))

(defvar *louds++* *)
--> *LOUDS++*

;; 番号3のノードは?
(node-name 3 *louds++*)
--> :D

各種操作関数定義。
参照: select/rank

;; 葉ノード(子無しノード)かどうか
(defun isleaf (node-num louds++)
  (with-slots (r0) louds++
    (= 0 (bit r0 node-num))))

;; 次の兄弟ノード取得。いないならnil。
(defun next-sibling (node-num louds++)
  (with-slots (r1) louds++
    (when (= 0 (bit r1 node-num))
      (1+ node-num))))

;; 前の兄弟ノード取得。いないならnil。
(defun prev-sibling (node-num louds++)
  (with-slots (r1) louds++
    (when (= 0 (bit r1 (1- node-num)))
      (1- node-num))))

;; 最初の子ノード取得。いないならnil。
(defun first-child (node-num louds++)
  (unless (isleaf node-num louds++)
    (with-slots (r0 r1) louds++
      (let ((nth-parent (rank1 r0 node-num))) ; node-numが何個目の親かを取得する
        (1+ (select1 r1 nth-parent))))))      ; r1内でのn個目の親の位置+1 = n個目の親の最初の子ノードの位置

;; 最後の子ノード取得。いないならnil。
(defun last-child (node-num louds++)
  (unless (isleaf node-num louds++)
    (with-slots (r0 r1) louds++
      (let ((nth-parent (rank1 r0 node-num))) ; node-numが何個目の親かを取得する
        (select1 r1 (1+ nth-parent))))))      ; r1内でのn+1個目の親の位置 = n個目の親の最後の子ノードの位置

;; 親ノード取得
(defun parent(node-num louds++)
  (with-slots (r0 r1) louds++
    (let ((nth-parent (rank1- r1 node-num)))  ; node-numの親が、何個目の親かを取得する
      (select1 r0 nth-parent))))              ; n個目の親のノード番号を取得する

例。

(defun louds++-traverse (louds++ &optional (root-node 0) (level 0))
  (format t "~&~V@T~S~%" level (node-name root-node louds++))
  (unless (isleaf root-node louds++)
    (loop FOR child-node = (first-child root-node louds++)
                      THEN (next-sibling child-node louds++)
      WHILE child-node
      DO
      (louds++-traverse louds++ child-node (1+ level)))))

(louds++-traverse *louds++*)
:A
 :B
 :C
  :F
  :G
   :I
 :D
 :E
  :H
--> NIL


ここまででLOUDS++そのものの実装は終了。
ただ、今のままだとselectやrankの実行にノード数に比例する時間が掛ってしまう。
それをO(1)(だったかな?)にするために、次回はこれらの操作を効率的に行えるビット配列(bit-vector*3 )の実装に取り組む。
論文読まないと...。

*1:O'Neil Delpratt, Naila Rahman, Rajeev Raman,『Enginnering the LOUDS Succinct Tree Representaion*』, LNCS 4007(p.134-145), 2006

*2:ちなみに、LOUDSではdouble-numberingという方法によって、rank操作を不要にすることが可能

*3:LOUDS++の論文では、単なるビットの配列をbit-string、select操作およびrank操作を備えたビット配列をbit-vectorと呼んでいる