etsavの日記： 圧縮コメントアウト そにょ３

そんなわけで Move-to-front の実装。 前回の burrows-wheeler-transform 関数の結果をそのまま受け取って、 car 部の文字列を変換、 cdr 部は素通しという事で。 この『前に持ってくる』という操作がソートの一種だって事を利用したら、 コードはかなり簡単になりますねぃ。 処理が効率的かどうかはともかく。

(defun move-to-front (bwt-transformed)
  (cons (let ((pointers (initial-pointer-list 256)))
      (apply 'string
         (mapcar (lambda (arg)
               (prog1 (find arg pointers)
                 (setq pointers
                   (sort pointers
                     (lambda (a b) (eq a arg))))))
             (append (car bwt-transformed) nil))))
    (cdr bwt-transformed)))

(defun inverse-move-to-front (mtf-transformed)
  (cons (let ((pointers (initial-pointer-list 256)))
      (apply 'string
         (mapcar (lambda (arg)
               (let (char)
                 (prog1 (setq char (elt pointers arg))
                   (setq pointers
                     (sort pointers
                       (lambda (a b) (eq a char)))))))
             (append (car mtf-transformed) nil))))
    (cdr mtf-transformed)))

initial-pointer-list 関数は前回のものを流用。 変換も逆変換も微妙に違うのだけどほとんど構造は同じ。 これまた当然だけど、 (inverse-burrows-wheeler-transform (inverse-move-to-front (move-to-front (burrows-wheeler-transform 文字列)))) の結果は 文字列 になります。

でもって、 前回の C++ ソースコードをブロックソート後に MTF 変換しますと―― printable な文字列じゃなくなるので16進ダンプの結果。

3B 00 3E 7B 2F 7D 02 2D 10 2E 07 05 78 04 77 01
05 05 02 29 00 00 01 01 01 00 00 00 00 00 01 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 41 2C
76 73 44 6F 64 0B 00 6C 03 02 08 38 01 0A 00 00
01 01 0C 04 01 02 6E 01 07 01 00 00 00 0D 0B 02
3A 03 09 0D 03 0B 6C 06 00 72 6E 11 41 00 05 10
06 01 00 01 00 00 00 00 73 15 09 75 03 10 10 72
07 00 00 00 12 00 70 02 04 01 00 15 78 03 10 0E
13 06 0B 02 02 05 02 00 00 00 04 03 00 00 6D 09
40 78 18 05 1E 14 0C 09 08 06 01 0A 13 08 01 12
01 00 00 00 74 01 07 00 0B 77 08 12 08 02 00 00
00 12 00 09 03 05 11 04 00 01 00 07 00 05 19 08
0D 07 00 14 00 09 03 01 01

変換前よりもデータが『偏る』んだそーだけど、 定量的には確認してませぬ〔を〕。 まぁブロックソーティングで同じ文字が連続したところが、 MTF 変換で 00 の連続になってるのは容易に判りますが。

ここまでで前処理はおしまぃ。 次は実際の圧縮過程なのだけど、 何を使いましょうかねぃ……？