LOUDS++(3): LOUDS++
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を分割することのメリットは(多分)おおまかには次の二つ。
- サイズ効率が(かなり?)良くなる
- 子および兄弟ノードの有無の判定が、ビット配列中の一要素を参照するだけで可能
- 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 )の実装に取り組む。
論文読まないと...。
