MTF : bzip2

BWTに続いて、MTF(Move To Front)。
BWTは、対象の列を、同じ値の要素が隣接する傾向がある列へと変換した。
MTFは、それらの隣接した要素を0(あるいは他の小さい整数)で置き換えるアルゴリズムらしい(不正確)。
BWT -> MTFの適用を経た列は、要素の多くが0やその他の小さな整数で占められることになるので、その列に対してハフマン符号化などを行った場合の圧縮率が高くなる。

以下は、MTFのコード例。

;;;;;;;;;;;;
;;;; MTF処理概要   
;;;; 1] 0〜255までの要素を持つリスト(リストAとする)を用意する
;;;; 2] MTFを適用する列の各要素(要素Bとする)に対して、以下の処理を繰り返す
;;;;    3] リストAの中の何番目に要素Bが出現するかを数える。
;;;       ==> この出現位置が、MTF変換後の要素の値
;;;     4] 要素BをリストAの先頭に持ってくる
;;;       ==> これよって、同じ要素が連続して出現した場合、二番目以降の要素の値は0となる
;;;     5] 列内の次の要素を処理する

;;;;;;;;;;;;;;;
;;;; パッケージ
(defpackage :mtf
  (:use :common-lisp)
  (:export mtf))
(in-package :mtf)

;;;;;;;;;;;;;;;;;
;;;; 宣言と型定義
(declaim (optimize (speed 3) (debug 0) (safety 0) (compilation-speed 0)))
(deftype simple-octets () '(simple-array (unsigned-byte 8)))

;; 前方宣言
(declaim (ftype (function (fixnum list) fixnum) move-to-front))

;; mtf関数
(defun mtf (octets)
  (declare (simple-octets octets))
  (let ((code-list (loop FOR i FROM 0 BELOW #x100 COLLECT i))
        (pos 0))
    (loop FOR code ACROSS octets COLLECT
      (setf (values pos code-list)  ; pos(= MTF変換後のコード)を集める
            (move-to-front code code-list)))))

;; 実際にmove-to-front処理を行う関数
;; code-list内でのcodeの出現位置の検索、およびcodeのcode-listの先頭への移動処理、を行う
;; --> (values codeの出現位置 更新されたコードリスト)
(defun move-to-front (code code-list)
  ;; code-listの先頭から何番目にcodeがあるかを探す
  ;; 先頭にある場合
  (when (= code (the fixnum (car code-list)))
    (return-from move-to-front (values 0 code-list)))

  ;; それ以外の場合
  (let ((i 0))
    (declare (fixnum i))
    (mapl
     (lambda (codes)
       (incf i)
       (when (= code (the fixnum (second codes)))
         ;; codeが先頭以外の場所にある場合は、code-listの先頭に持ってくる
         (setf (cdr codes) (cddr codes))
         (return-from move-to-front (values i (cons code code-list)))))
     code-list)))

使用例。
参照: bwt, read-binary-file

;; 同じ要素が続いた場合、二番目以降は0にエンコードされる
> (mtf:mtf (sb-ext:string-to-octets "aaaabbbaaaa"))
--> (97 0 0 0 98 0 0 1 0 0 0)

;; BWTとの組み合わせ
> (defparameter *bwt* (bwt:bwt (read-binary-file "/path/to/kokoro")))
--> *BWT*

> (defparameter *mtf* (mtf:mtf (bwt:to-octets *bwt*)))
--> *mtf*

;; サイズ
> (length *mtf*)
--> 554722

;; 値0の要素の数
> (count 0 *mtf*)
--> 399091   ; 全体の70%程度の要素の値が0