2004年5月27日（木）NIFS
奥村晴彦（三重大学）
いつの時代も CPU は I/O より速い
Shannon (1948): A Mathematical Theory of Communication
m 個の文字がそれぞれ出現確率 p1, p2, …, pm で独立に現れるとすると，平均して
（エントロピー）H = Σ pi log2 (1 / pi)
ビット／文字より縮めることはできない。
つまり，2k 回に1回出現する文字は，k ビットで符号化するのが最適である（可変長符号化）
Jacob Ziv and Abraham Lempel, A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, IT-23(3), 337-343, 1977.
一つのインプリメント：
「マハリクマハリタ」を次のように符号化する（文字を8ビットと仮定）
| フラグ （1ビット） | 文字 （8ビット） | 戻り距離 | 長さ |
|---|---|---|---|
| 0 | マ | ||
| 0 | ハ | ||
| 0 | リ | ||
| 0 | ク | ||
| 1 | 4 | 3 | |
| 0 | タ |
LHA，ZIP，gzipのアルゴリズム（奥村，1988〜1989）：↑を↓のように整理する。
| フラグ （1ビット） | 文字または長さ （8ビット） | 戻り距離 （≧12ビット） |
|---|---|---|
| 0 | マ | |
| 0 | ハ | |
| 0 | リ | |
| 0 | ク | |
| 1 | 3 | 4 |
| 0 | タ | |
| 9ビット ↓ 可変長符号化 | 12ビット超 ↓ 可変長符号化 | |
gzipのアルゴリズムをハードウェア化したもの もある（PCI，32MB/s）。 Webのトラフィック（テキストベース，繰返し多）などには非常に効果があるが，これを単にADC出力に接続するのは不適
画像の例: Mona Lisa
浮動小数で予測誤差（例：差分）を求めても桁数は減らない
Lossy → 整数化（量子化）してから上の方法を使う
Lossless → ビットパターンが同じ整数に変換する
たとえば IEEE 754 single は
| 1 | 8 | 23 | |||||||||||||||||||||||||||||
| 符 号 | 指数 | 仮数 | |||||||||||||||||||||||||||||
このビットパターンを24ビット整数と見ても，大小関係は元の浮動小数点と同じ。
| MSB ← 32ビット → LSB | |||||||||||||||||||||||||||||||
[2006-06-25追記] 説明が不十分でしたが，負数の場合は符号ビット以外を反転させます。これを符号付き整数と見れば，大小関係が保たれ，しかも絶対値が同じ正負の数を（符号付き整数として）加えれば 0 になります。
似たデータをまとめる
例： データベースの column-wise compression
XML では XMill
モデル化し，予測誤差に変換
Last modified: 2006-06-25 21:04:50