Move to front変換とは?

作者: Richard bird,山下伸夫
出版社/メーカー: オーム社
発売日: 2014/11/12
メディア: 単行本（ソフトカバー）
この商品を含むブログ (1件) を見る

のBurrows Wheeler Transformに関する章で、名前だけ出てきて気になったので。

(例えば)以下の様な変換です!!

初期テーブル {a,b,c,d,e,f}

aaaaaa => 000000 
bbbbbb => 100000
cccccc => 200000 
bababa => 111111
cbacba => 222222 
abbaab => 010101
accbba => 020202
fedcba => 555555

なにやってんだこれ。

おおざっぱな解説

Move-to-front変換は、おおざっぱに言えば、「最近使った記号を、小さい数字に対応させる」という符号化です。

手順としては、

テーブルを見て一文字符号化
1 で参照した記号をテーブルの先頭に持ってくる

ということを繰り返します。

アルゴリズムとしては、とてもシンプルな変換です。

具体例

具体例に説明します。記号としては、{a,b,c,d,e,f}だけをつかい、この記号の記号列を符号化します。文字列ddbbaaを変換してみましょう。

初期設定として、テーブルは{0:a, 1:b, 2:c, 3:d, 4:e, 5:f} にします。

|ddbbaa

0 1 2 3 4 5
a b c d e f

=> 

3 | dbbaa

0 1 2 3 4 5
d a b c e f

=> 

30 | bbaa

0 1 2 3 4 5
d a b c e f

=> 

302 | baa

0 1 2 3 4 5
b d a c e f

=> 

3020 | aa

0 1 2 3 4 5
b d a c e f

=> 

30202 | a

0 1 2 3 4 5
a b d c e f

=>

302020 |

0 1 2 3 4 5
a b d c e f

復号は?

自明ですね! (めんどくさくなった)

この変換なにに使うの?

なんか圧縮の前処理に便利らしいです。まだよくわからない。

Haskell実装

import Data.List

encode' :: [Char] -> Char -> ([Char], Int)
encode' table x = (x:delete x table, n)
          where n = head $ elemIndices x table
                
encode :: [Char] -> [Int]
encode xs = snd $ mapAccumL encode' ['a'..'z'] xs 

decode' :: [Char] -> Int -> ([Char], Char)
decode' table n = (table', x)
                  where x = table !! n
                        table' = x:(delete x table)

decode :: [Int] -> [Char]
decode ns = snd $  mapAccumL decode' ['a'..'z'] ns