Move to front変換(先頭移動法)の話とHaskellでの実装
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
encode'
は、一文字分の符号化に対応します。
encode
は、mapAccumL
で、encode'
の計算をつないでいます
tableを更新しながら参照するような計算をつなぐためには、mapAccumL
はとても便利ですね!
再帰関数のメモ化とかにも使えるのかな? 検討してみるか。。。
参考
高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)
- 作者: 岡野原大輔
- 出版社/メーカー: 岩波書店
- 発売日: 2012/12/27
- メディア: 単行本
- 購入: 15人 クリック: 324回
- この商品を含むブログ (5件) を見る
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日目の記事です。
次 @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型の中に入り込んでしまいました。
イメージ図
自然数って、以下の様な構造を持っているイメージですよね。
しかしHaskellのNatには、omegaが混じってしまっているので、以下の様なイメージです。
図がきたねぇ。
他にも色々不純物
omega以外にも、Natには以下の様なものも混じっています。
omega1 :: Nat omega1 = S omega2 omega2 :: Nat omega2 = S omega1 omega' :: Nat omega' = omega'
なんとなく、omega
とomega1
,omega2
は結局同じもの、という気がしますが。
Nat型と数学的帰納法
上の図を見ていただけばなんとなく納得できると思うのですが、Nat型に関する性質を証明したいときには、普通の数学的帰納法では不十分です。
表示的意味論やらなんやらでがんばらないといけません。といっても、実際そんなに難しい手法になるわけではないようですが。
参考資料
- 作者: Richard Bird,山下伸夫
- 出版社/メーカー: オーム社
- 発売日: 2012/10/26
- メディア: 単行本(ソフトカバー)
- 購入: 3人 クリック: 28回
- この商品を含むブログ (4件) を見る
元ネタはこの本です。
数学ガール ゲーデルの不完全性定理 (数学ガールシリーズ 3)
- 作者: 結城浩
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2009/10/27
- メディア: ペーパーバック
- 購入: 37人 クリック: 930回
- この商品を含むブログ (155件) を見る
とても丁寧な「ペアノの公理」の説明がのってます。
ブログ始めるぞ
テストとーこー。