DMC(Dynamic Markov Coding)によるデータ圧縮
参照
G. V. Cormack and R.N.S.Horspool.
Data Compression Using Dynamic Markov Modeling.
The Computer Journal, 30(6) :541-550, 1987.
はじめに
データ圧縮法
- ソースデータの構造に関するアプリオリな仮定をもとにしている。
- 例)Huffman coding
今回は、ソースデータを離散マルコフ連鎖モデルによって作られたビットの流れと仮定する。
研究の方向性
- データを表すマルコフ連鎖モデルを発見する
- メッセージの初めでモデルを構築して、予測する
- 各状態が次の遷移確率を保持する
Guazzoのアルゴリズム
まず、
Huffman codeの欠点
- 文字の出現が2のn乗の時だけ、減らせる
- グループ化したビット間だけ、相互関係が有利になる
Guazzoはこれを修正
[0.000… , 0.11111…] → 遷移確率を基に分割して行く。
↓
[0.000… , 0.0111…]
↓
…
↓
[0.011100110101 , 0.01110100101111]
(0111001で始まるソースメッセージを表している)
適応型
今までは,two-pass
- メッセージの性質を発見する(各確率を計算)
- それをもとに圧縮(エンコード)
今回は,
適応型
- 動的に行う
- 前準備がいらない(k-1個のデータと１つ前のモデルを用いる)
マルコフ連鎖モデル
- 確率の設定
動的に圧縮する上で、0%になるとまずいので、0の時は(n0+c)/(n0+n1+2c)、1の時は(n1+c)/(n0+n1+2c)と設定する。
- グラフの構造
- cloningする。
- 前後の情報をよりわかりやすくする。
- 遷移回数に閾値を用いる。(すべてにクローンを作ると無駄が多い)
- cloningする。
また、
- 状態数がある一定の値を超えたら、初期状態に戻す(最後のk個の要素を使って新たに状態を作る)。
Guazzoアルゴリズムの実用
- 範囲の上限下限を正確に決めなければならない
- 正確さの必要性を弱めた
- 正確に分割できなくても圧縮率にはあまり影響が無い
- 正確さの基準を決めた。
- 正確さの必要性を弱めた
- 各intervalが表す列がわからない。
- 0111010に関しては,[0.0111010000…,0.01110101111…]と表すようにする。
