Move to front変換(先頭移動法)の話とHaskellでの実装

Move to front変換とは?

関数プログラミング 珠玉のアルゴリズムデザイン

関数プログラミング 珠玉のアルゴリズムデザイン

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. テーブルを見て一文字符号化
  2. 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

encode'は、一文字分の符号化に対応します。

f:id:LamLam:20141223122820p:plain

encodeは、mapAccumLで、encode'の計算をつないでいます

f:id:LamLam:20141223122828p:plain

tableを更新しながら参照するような計算をつなぐためには、mapAccumLはとても便利ですね! 再帰関数のメモ化とかにも使えるのかな? 検討してみるか。。。

参考

高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)

高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)

Move to front変換のアルゴリズムが載ってた。確率統計やりなおさないと、ちゃんと読めなさそう。

Algorithms with Python ブロックソート (BlockSorting)

この記事よりわかりやすく、Python実装つきの解説があります! Move to frontの色々な拡張まで紹介されています。

Move-to-front algorithm(rosettacode)

Haskell他いろんな言語でのMove to frontの実装。 Haskellのコードも、この記事のものより簡潔ですね!