昇順数値列のunary表現と定数時間アクセス

common lisp algorithm

数値列の圧縮に関するメモ書き。

サンプル数値列

要素が昇順に並んだ数値列があるとする。

(defvar *numbers* #(0 1 2 4 5 8 9 10 11 14))

前準備: 差分列への変換

このような数値列を圧縮する場合は、その前準備として、もともとの数値列を各要素間の差分を取った列に変換する、ということが良く行われる(?*1 )。

;; 隣接する各要素の差分を求める
(defvar *diffs* (coerce
                 (loop WITH prev = 0
                       FOR n ACROSS *numbers*
                       COLLECT (prog1 (- n prev)
                                 (setf prev n)))
                 'vector))

*numbers* ; もともとの数値列
--> #(0 1 2 4 5 8 9 10 11 14)

*diffs* ; 差分列: こっちの方が要素の値が小さい
--> #(0 1 1 2 1 3 1 1 1 3)

上の例のように、もともとの数値列の各要素の値が密な場合は、各要素の値を一つ前の要素に対する差分で表現した方が、各値は小さくなる。

数値のunary表現

後は、変換後の列の各値を、サイズ効率の良い方法で表現すれば、圧縮は完了。
ここではunary表現を用いる。

;; unary表現
;; - 数値Nを「N個の0 + 末尾の1」形式の列で表現する
(defun unary (n)
  (append (loop REPEAT n COLLECT 0) ; N個分の0
          (list 1)))                ; 1で終端

(unary 3)
--> (0 0 0 1)

(unary 0)
--> (1)

;; 通常の数値列を、unary表現の数値列に変換する
(defun to-unary-seq (numbers)
  (coerce
   (loop FOR n ACROSS numbers
         APPEND (unary n))
   'bit-vector))

;;;
*diffs*
--> #(0 1 1 2 1 3 1 1 1 3)     ; 差分列

(defvar *unary* (to-unary-seq *diffs*))
*unary*
--> #*101010010100010101010001 ; そのunary表現

;;; 表現に必要なビット数
(length *unary*)
--> 24     ; *diffs* を24bitで表現可能

;; *numbers*の各要素を8bitで表現した場合  ※ *numbers*に限れば、実際には4bitあれば各要素は表現可能
(* 8 (length *numbers*))
--> 80     ; 80bit必要:  24/80 => 3/10 に圧縮

この例の場合、「昇順数値列 => 差分列 => unary表現」といった変換を経ることで、もともとの数値列の各要素を8bitで表現した場合に比べて、1/3以下に圧縮できている。

差分列の問題点(だと思っていたこと)

数値列をその差分で表現した場合、特定の要素の(もともと)値を取得するためには、その要素の前方にある要素全てを走査しなければいけないという問題点がある(と思っていた)。

;; *numbers*[index]の値を*diffs*を元に取得する
(defun diff-ref (diffs index)
  (loop FOR i FROM 0 TO index
        SUM (aref diffs i)))   ; 0からindexまでの値を走査し、累積していく必要がある

;;
(aref *numbers* 8)   ; O(1): 一回の配列アクセスで値が取得可能
--> 11

(diff-ref *diffs* 8) ; O(N): 値の取得毎に、先頭から添字位置までの走査が必要
--> 11

ただし、(少なくとも)差分列のunary表現に関しては、これは間違い。　
求めたい要素の添字に対応する1の位置さえ分かれば、その前方にある0の数==もともとの数値、となるためO(1)での要素取得が可能。

;; 求めたい要素の添字に対応する1の位置を求める。
;; ※ 以下の実装の簡単のためにunary-seqの長さに比例する時間が掛かる実装となっているが、
;;    ここではO(1)で実行可能なものと仮定する。
;;
;;    同様の処理(= ビット列のN個目の1の位置を求める処理)を実際にO(1)で実装する方法は、
;;   「簡潔データ構造(or succinct data structure) select」等をキーワードにして検索すれば
;;    ヒットすると思われるので、そちらを参照のこと。
;;    (common lispでの実装例としては、http://d.hatena.ne.jp/sile/20100613/1276445650、も一応参考になるかもしれない)
(defun select (unary-seq index)
  (loop FOR pos FROM 0 BELOW (length unary-seq)
        WHEN (= 1 (aref unary-seq pos))
    DO
    (when (= index 0)  ; index個目の1に達した場合は、その位置を返す
      (return pos))
    (decf index)))

;; *numbers*[index]の値を*unary*を元に取得する関数
;; (- indexに対応する1の位置 index) == indexに対応する1の位置より前方にある0の数 == *numbers*[index]の値、となる
(defun unary-ref (unary-ref index)
  (- (select unary-ref index) index))

;;
(aref *numbers* 8)    ; O(1): 一回の配列アクセスで値が取得可能
--> 11

(unary-ref *unary* 8) ; O(1): 一回のselect走査 + 一回の減算、で値が取得可能
--> 11

結論

つまりは、昇順数値列(の差分列)をunary表現で表せば、圧縮できて且つ定数アクセスも可能、ということ。

*1:ような気がするけど、詳しくないので不確か