動的マルコフ圧縮（DMC ）は、ゴードン・コーマックとナイジェル・ホースプールによって開発されたロスレスデータ圧縮 アルゴリズムです。[1]部分マッチングによる予測（PPM）に似た予測算術符号化 を使用しますが、入力が（1バイトずつではなく）1ビットずつ予測される点が異なります。DMCはPPMと同様に圧縮率が高く、速度も適度ですが、必要なメモリがやや多く、広く実装されていません。最近の実装としては、Nania Francesco Antonioによる実験的な圧縮プログラムフック、Frank Schwellingerによるocamyd、 Matt Mahoneyによるpaq8lのサブモデルなどがあります。これらは、1993年にゴードン・コーマックがCで実装したものに基づいています。
アルゴリズム
DMCは一度に1ビットずつ予測し、符号化します。PPMとは異なり、バイトではなくビット単位で符号化します。また、PAQなどのコンテキスト混合アルゴリズムとは異なり、予測ごとに1つのコンテキストしか使用しません。予測されたビットは、算術符号化を用いて符号化されます。
算術符号化
DMC などのビット算術符号化器には、予測器と算術符号化器の 2 つのコンポーネントがあります。予測器は、nビットの入力文字列x = x 1 x 2 ... x nを受け取り、一連の予測の積として表現される確率p ( x ) を割り当てます。 p ( x 1 ) p ( x 2 | x 1 ) p ( x 3 | x 1 x 2 ) ... p ( x n | x 1 x 2 ... x n –1 )。算術符号化器は、 2 つの高精度の 2 進数p lowとp high を維持します。これは、これまでに確認されたxのビットを前提として、モデルが辞書式でxより小さいすべての文字列に割り当てる合計確率の可能な範囲を表します。 xの圧縮コードはp xで、 p lowとp highの間の数値を表す最短のビット文字列です。この範囲内で、シャノン限界log 2 1 / p ( x )より1ビット以内の数値を見つけることは常に可能です。そのような数値の1つは、 p highから、 p lowと異なる最初のビット以降のビットをすべて削除することで得られます。
圧縮は次のように進行します。初期範囲はp low = 0、p high = 1 に設定されます。各ビットについて、予測器はp 0 = p ( x i = 0 | x 1 x 2 ... x i –1 ) およびp 1 = 1 − p 0（それぞれ0または1の確率）を推定します。次に、算術符号化器は現在の範囲 ( p low、 p high ) をp 0とp 1に比例して2つの部分に分割します。そして、次のビットx iに対応するサブ範囲が新しい範囲になります。
伸長処理では、予測器はこれまで伸長されたビットに基づいて、同一の一連の予測を行います。算術符号化器は、同一の一連の範囲分割を行い、 p x を含む範囲を選択し、その部分範囲に対応するビットx iを出力します。
実際には、高精度を実現するためにメモリ内でpを低く、pを高く保つ必要はありません。範囲が狭まるにつれて、両方の数値の先頭ビットは同じになり、すぐに出力できます。
DMCモデル
DMC予測子は、（ビット単位の）コンテキストを、このコンテキストで以前に観測された0と1の数を表すカウントのペアn 0とn 1にマッピングするテーブルです。したがって、次のビットが0になる確率はp 0 = n 0 / n = n 0 / ( n 0 + n 1 )、1になる確率はp 1 = 1 − p 0 = n 1 / nであると予測します。さらに、各テーブルエントリには、現在のコンテキストの右側に0または1を追加することによって（左側のビットを削除して）取得されたコンテキストへのポインタのペアがあります。したがって、テーブルで現在のコンテキストを検索する必要はありません。現在のコンテキストへのポインタを保持し、リンクをたどるだけで十分です。
オリジナルのDMC実装では、初期テーブルはバイト境界から始まる8ビットから15ビットまでの長さを持つすべてのコンテキストの集合です。初期状態は8ビットコンテキストのいずれかです。カウントは0.2などの小さな非ゼロ定数に初期化された浮動小数点数です。カウントがゼロに初期化されないのは、現在のコンテキストで以前に使用されたことがない値であってもコード化できるようにするためです。
圧縮と解凍のモデリングは同じです。各ビットについて、p 0とp 1が計算され、ビットx iが符号化または復号化され、 x iに対応するカウントに1を加算してモデルが更新され、 x iに対応するリンクを辿ることで次のコンテキストが検索されます。
新しいコンテキストの追加
上で説明したDMCは、オーダー1のコンテキストモデルと同等です。ただし、圧縮率を向上させるために、より長いコンテキストを追加するのが一般的です。現在のコンテキストがAで、次のコンテキストBが左側のビットを落とす場合、DMCはBから新しいコンテキストCを追加（複製）することがあります。Cは、Bと同様に右側に1ビットを追加した後、Aと同じコンテキストを表しますが、左側のビットは落としません。したがって、AからのリンクはBからCを指すように移動されます。BとCはどちらも同じ予測を行い、どちらも同じ次の状態のペアを指します。Cの合計カウントn = n 0 + n 1は、 Aの カウントn x （入力ビットxの場合）と等しくなり、そのカウントがBから差し引かれます。
例えば、状態Aがコンテキスト11111を表しているとします。入力ビット0を入力すると、状態Bはコンテキスト110を表します。コンテキスト110は左側の3ビットを落としたものです。コンテキストAには、0のビットが4つと1のビットがいくつかありました。コンテキストBには、0のビットが3つと1のビットが7つ（n = 10）あり、p 1 = 0.7と予測されます。
| 州 | 0個 | 1 | 次の0 | 次の1 |
|---|---|---|---|---|
| A = 11111 | 4 | B | ||
| B = 110 | 3 | 7 | E | F |
C は B から複製されます。コンテキスト 111110 を表します。B と C は両方ともp 1 = 0.7 を予測し、両方とも同じ次の状態 E と F に進みます。C のカウントはn = 4 で、A のn 0と等しくなります。これにより、B の n = 6 になります。
| 州 | 0個 | 1 | 次の0 | 次の1 |
|---|---|---|---|---|
| A = 11111 | 4 | C | ||
| B = 110 | 1.8 | 4.2 | E | F |
| C = 111110 | 1.2 | 2.8 | E | F |
状態は遷移する直前に複製されます。オリジナルのDMCでは、状態を複製するための条件は、AからBへの遷移回数が2回以上で、かつBの遷移回数がそれより2回以上多い場合です。（2つ目の閾値が0より大きい場合、複製後も他の状態がBに遷移することが保証されます。）hookなどの一部の実装では、これらの閾値をパラメータとして設定できます。paq8lでは、メモリ使用量が増えるにつれてこれらの閾値が増加し、新しい状態の増加速度を遅くします。ほとんどの実装では、メモリが使い果たされるとモデルは破棄され、元のバイト単位順序1のモデルに再初期化されます。
参考文献
- ^ Gordon CormackとNigel Horspool、「動的マルコフモデリングを用いたデータ圧縮」、Computer Journal 30:6（1987年12月）
外部リンク
- 動的マルコフモデリングを用いたデータ圧縮
- Google Developers YouTube チャンネル: Compressor Head エピソード 3 (マルコフ連鎖圧縮) (
ページが読み込まれると音声が再生されます)
