LOUDS++(2): rankとselect

common lisp algorithm

LOUDS++*1実装の続き。
前回はここ。

今回は、この論文中に良く出てくるrankとselectという関数を自分なりに(= 間違っている可能性あり*2 )整理してみた。

rank, select

rank及びselectは、前回作成したLBS(LOUDS bit-string)から、木のノード情報を取り出すための関数。

;;; LBS(= 木のビット列へのエンコード)の例
;;; 詳しくは前回参照   ※ 前回も別に詳しくはないけど ... 

;; 元となる木
(defvar *tree* 
  '(:a (:b)
       (:c (:f) 
           (:g (:i))) 
       (:d) 
       (:e (:h))))
--> *tree*

;; LBSに変換
(tree-to-lbs *tree*)
--> #*1011110011001001000  
    #(:SUPER-ROOT :A :B :C :D :E :F :G :H :I) 

;; 後で使うので保存しておく
(defvar *lbs*)
(defvar *node-names*)
(setf (values *lbs* *node-names*) (tree-to-lbs *tree*))

定義

rankとselectの定義。
それぞれ0ビット用のものと1ビット用のものがある。

;;; 論文中での定義を、ほぼそのままlispプログラムに落としたもの
;;; 実際の場面では非効率過ぎて使えないが、分かりやくはある

(defun select0 (lbs i)
  "LBSの中のi番目の0の位置を返す。iが0以下、もしくはi番目の0がLBSに存在しない場合は-1を返す。"
  (loop FOR pos FROM 0
        FOR bit ACROSS lbs
    WHEN (= 0 bit)
    DO (when (zerop (decf i))
         (return pos))
    FINALLY (return -1)))

(defun select1 (lbs i)
  "LBSの中のi番目の1の位置を返す。iが0以下、もしくはi番目の1がLBSに存在しない場合は-1を返す。"
  (loop FOR pos FROM 0
        FOR bit ACROSS lbs
    WHEN (= 1 bit)
    DO (when (zerop (decf i))
         (return pos))
    FINALLY (return -1)))
        
(defun rank0 (lbs x) 
  "LBS内で、位置Xよりも左(Xも含む)にある0ビットの数を返す。"
  (loop FOR i FROM x DOWNTO 0
        FOR bit = (aref lbs i)
    WHEN (= 0 bit) SUM 1))

(defun rank1 (lbs x)
  "LBS内で、位置Xよりも左(Xも含む)にある1ビットの数を返す。"
  (loop FOR i FROM x DOWNTO 0
        FOR bit = (aref lbs i)
    WHEN (= 1 bit) SUM 1))
#|
;; rank1は、rank0を使っても定義できる  ※ 逆も同様
(defun rank1 (lbs x) 
  (- x (1- (rank0 lbs x))))
|#

(LBSも含めて)簡単にまとめてしまえば、(多分)だいたい次のような感じとなる。

  • LBS内のN番目の0ビットは、番号Nのノードに対応する。
  • LBS内のN番目の1ビットは、番号Nのノードに対応する。
    • ノードの番号は、木をレベル順で走査した場合の到達順序
    • LBS内の0ビットは親ノードを、それに続く1ビットはその子ノードを、表している。
  • selectはノード番号を受け取って対応するLBS内の(0 or 1)ビットの位置を返す。ノード番号=>LBS内のビット位置
  • rankは逆に、LBS内のビット位置からそれに対応するノード番号を算出する。LBS内のビット位置=>ノード番号

つまりは、rankとselectを使うことで、LBSのどのビットが木のどのノードに対応しているかが分かる、というだけのこと(だと思う)。

もう少し整理(?)

対応表。

関数 説明
(rank1 LBS LBS内での1ビットの位置) そのビットに対応するノード番号を取得する
(rank0 LBS LBS内での0ビットの位置) そのビットに対応するノード番号を取得する
(rank0 LBS LBS内での1ビットの位置) そのビットに対応するノードの親ノードの番号を取得する
(select1 LBS ノード番号) そのノードに対応するLBS内での1ビットの位置を取得する
(select0 LBS ノード番号) そのノードに対応するLBS内での0ビットの位置を取得する

例。

 *lbs*
--> #*1011110011001001000

;; *lbs*[9]にあるビット(1)が対応するノードは?
(rank1 *lbs* 9) 
--> 7   ; 7番目のノードに対応

(aref *node-names* (rank1 *lbs* 9))
--> :G  ; ノード:G

;; *lbs*[9]にあるビット(1)が対応するノード(:G)の親ノードは?
(rank0 *lbs* 9)
--> 3

(aref *node-names* (rank0 *lbs* 9))
--> :C

;; ノード:Iに対応する0ビットは?
(select0 *lbs* (position :i *node-names*))
--> 17

(aref *node-names* (rank1 *lbs* 17))
--> :I

木に対する操作

参照した論文中では、LOUDSでの木に対する操作として次の六つを挙げている。

  • isleaf(node-num)
  • parent(node-num)
  • first-child(node-num)
  • last-child(node-num)
  • next-sibling(node-num)
  • prev-sibling(node-num)

これらは、rankとselectを(例えば)以下のように組み合わせることで実装できる。

;;; 簡潔さのために、配列の範囲外アクセスなどは気にしていない
;;; 効率よりも分かりやすさを優先

(defun isleaf(lbs node-num)
  (let* ((node-bit (select0 lbs node-num))         ; 対応する0ビットを取得
         (child-node-bit (bit lbs (1+ node-bit)))) ; 最初の子ノード(候補)を取得する
    (= 0 child-node-bit)))  ; 子ノードは、node-bitに続く1ビットで表現されているので、それが0の場合は、子ノードなしと判断できる

(defun parent(lbs node-num)
  (let ((node-bit (select1 lbs node-num)))  ; 対応する0ビットを取得
    (rank0 lbs node-bit)))                     ; 親のノード番号を取得

(defun first-child(lbs node-num)
  (unless (isleaf lbs node-num)
    (let ((parent-bit (select0 lbs node-num))) ; 対応する0ビットを取得
      (rank1 lbs (1+ parent-bit)))))           ; 最初の子ノードを取得する

(defun last-child(lbs node-num)
  (unless (isleaf lbs node-num)
    (let ((next-parent-bit (select0 lbs (1+ node-num)))) ; 一つ後の0ビットを取得する
      (rank1 lbs (1- next-parent-bit)))))                ; 最後の子ノードを取得する

(defun next-sibling (lbs node-num)
  (let* ((node-bit (select1 lbs node-num))   ; 対応する1ビットを取得
         (next-bit (bit lbs (1+ node-bit)))) ; 一つ右のノードを取得する
    (when (= 1 next-bit)  ; 1ビットが続く場合は兄弟あり
      (1+ node-num))))

(defun prev-sibling (lbs node-num)
  (let* ((node-bit (select1 lbs node-num))   ; 対応する1ビットを取得
         (prev-bit (bit lbs (1- node-bit)))) ; 一つ左のノードを取得する
    (when (= 1 prev-bit)  ; 1ビットが続く場合は兄弟あり
      (1- node-num))))

;;;;;;
;;; 例
;; LBS表現の木を操作して、各ノードの名前を出力する
(defun lbs-traverse (lbs node-names &optional (parent-node 1) (level 0))
  (format t "~&~V@T~S~%" level (aref node-names parent-node))
  (unless (isleaf lbs parent-node)
    (loop FOR child-node = (first-child lbs parent-node) 
                     THEN (next-sibling lbs child-node)
      WHILE child-node
      DO 
      (lbs-traverse lbs node-names child-node (1+ level)))))

(lbs-traverse *lbs* *node-names*)
:A
 :B
 :C
  :F
  :G
   :I
 :D
 :E
  :H
--> NIL

これで、LBSを木として扱えるようには、一応なった。
残りは、以下にしてこれらの操作を効率的に行うか、というところ。

名前

それにしてもrankとselectという名前は分かりにくいと思う。
上の対応表を見ないと、いまだにrankとselectの機能を取り違えることがある。
何でこの名前にしたんだろう...。

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

*2:基本的に自分用メモなので、ちゃんと知りたい人はオリジナルの論文を参照のこと