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のコードも、この記事のものより簡潔ですね!

無限リスト入門

これはAizu Advent Calendar 2014 22日目の記事です。

@ishi_kuro

@youxkei

告知ではCoqの記事を書くとかのたまってましたが、僕には無理でした。ごめんなさい。だれか僕に依存型教えてください。

ということで(?)、代わりにHaskellの無限リストのことを書きます。

無限リストの基礎の基礎

Haskellでは、次のような、無限の長さのリストを簡単に定義できます!!

ones = 1:ones

とっても気持ち悪い定義ですね。onesはどのように評価されていくのでしょうか。

ones 
---ones=1:onesで書き換える。
~> 1:ones
---やはりones=1:onesで書き換える。
~> 1: (1: ones)
---同上
~> 1:(1:(1:ones))
---以下同様
~> 1:1:1:1:1:.....

ということで、onesは、1が無限に続くリストになることがわかりますね。

しかし、無限の長さのリストなんて定義できても、どのように使えばいいのでしょうか。 実際に無限リストの値を使う場合には、有限の部分だけ使うことになります。

ones = 1:ones

main = do
    print $ take 10 ones

実行結果

[1,1,1,1,1,1,1,1,1,1,]

あらかじめ無限の長さでとして定義しておけば、使いたいときに使いたい長さ分だけ使える、というところが、 無限リストのメリットですね。

無限リストで等差数列、等比数列、無限級数

もうちょっと役に立ちそうな例として、高校数学でもお馴染みの等差数列と等比数列Haskellで定義してみたいと思います。

便利なiterateという関数があるお陰で、簡単なんですけどね。

iterate f x ~> [x, f x, f (f x), f (f (f x)), .....,  ]

ということで、初項1, 公比2の数列

[1, 2, 4, 8, 16, 32, ....]

という数列であれば、以下のように定義できます

iterate (*2) 1

だから、一般的な等差数列、等比数列も簡単なのがわかりますね。

arith_seq a d = iterate (+d) a
geo_seq a r = iterate (*r) a

無限級数も、scanlという関数のお陰で簡単です。

series seq = scanl (+) 0 seq

では、数列

[1, 1/2, 1/4, 1/8, 1/16, ...]

の和が、2に収束するということを確かめてみましょう。

プログラム

p e = (\x -> (2-x) >= e)
l = series (geo_seq 1 0.5)

takeWhile (p 0.001) l 

実行結果

[0.0,
1.0,
1.5,
1.75,
1.875,
1.9375,
1.96875,
1.984375,
1.9921875,
1.99609375,
1.998046875]

おまけ

有理数 p / qの小数表示に対応する無限リストはこんな感じ。

rat p q = (p `div` q) : rat ((p `mod` q) * 10) q

Haskellの自然数が自然数じゃないという話(?)

12/26 追記

断定で書くほど、よくわかってる話でもないので、タイトルに疑問符追加

Haskellで、自然数の集合に対応する型は、以下のように定義できるように思えます (ここでの自然数は、0を含んでいるとします)。

自然数(?)Natの定義

data Nat = O | S Nat

以下のように、0,1,2に対応するNat型の値を定義することが出来ます。

zero :: Nat
zero = O

one :: Nat
one = S O

two :: Nat
two = S (S O)

問題点

しかし問題は、以下の様な定義もできてしまうことです。

omega :: Nat
omega = S omega

omegaは、どのように評価されるのでしょうか?

omega
~> S omega
~> S (S omega)
~> S (S (S omega))
.
.
.
~> S (S (S (S (S ....

ということで、無限に対応するような値が、Nat型の中に入り込んでしまいました。

イメージ図

自然数って、以下の様な構造を持っているイメージですよね。

f:id:LamLam:20141221142637j:plain

しかしHaskellのNatには、omegaが混じってしまっているので、以下の様なイメージです。

f:id:LamLam:20141221142659j:plain

図がきたねぇ。

他にも色々不純物

omega以外にも、Natには以下の様なものも混じっています。

omega1 :: Nat
omega1 = S omega2

omega2 :: Nat
omega2 = S omega1

omega' :: Nat
omega' = omega'

なんとなく、omegaomega1,omega2は結局同じもの、という気がしますが。

Nat型と数学的帰納法

上の図を見ていただけばなんとなく納得できると思うのですが、Nat型に関する性質を証明したいときには、普通の数学的帰納法では不十分です。

表示的意味論やらなんやらでがんばらないといけません。といっても、実際そんなに難しい手法になるわけではないようですが。

参考資料

関数プログラミング入門 ―Haskellで学ぶ原理と技法―

関数プログラミング入門 ―Haskellで学ぶ原理と技法―

元ネタはこの本です。

数学ガール ゲーデルの不完全性定理 (数学ガールシリーズ 3)

数学ガール ゲーデルの不完全性定理 (数学ガールシリーズ 3)

とても丁寧な「ペアノの公理」の説明がのってます。