データ圧縮技術の基礎と最近の動向

参考書

• 植松友彦 『文書データ圧縮アルゴリズム入門』（CQ出版社，1994年）
• 今野浩 『カーマーカー特許とソフトウェア――数学は特許になるか』（中公新書1278，中央公論社，1995年）

（補記）今野浩先生は東工大を退官され，今は中央大におられます（新URL）。

東京工業大学 大規模データ圧縮ライブラリ

青木尊之先生

• 東京工業大学 大規模データ圧縮ライブラリ (仮ドキュメントです) [2002-11-12 新URL: 東京工業大学 大規模データ圧縮ライブラリ]

オープンソース（商利用も可）

FortranやCで通常にファイルに書き込むのと同じ感覚で圧縮保存できる（はず）

• fopen() の代わりに titz_open() を呼ぶ
• fwrite() の代わりに titz_putData() を呼ぶ
• fclose() の代わりに titz_close() を呼ぶ

いろいろな圧縮エンジンが選べる (予定)

zlib, (予測符号化), (Wavelet), ……

HDF を追い越せ！

Introduction

なぜ圧縮？

いつの時代も CPU は I/O より速い

圧縮の種類

• 可逆（無歪） lossless
• 非可逆（不可逆）lossy

一番簡単な圧縮

Run-length coding（連長符号化）

あああああいいい → あ₅い₃

歴史

• Data Compression: Chronology
• 昔話

圧縮と詐欺

ZeoSync 事件

任意の n ビットのファイルを n - 1 ビット以下に可逆に圧縮するアルゴリズムは存在しない。

［証明］ n ビットのファイルは 2ⁿ 通り存在するが，n - 1 ビット以下のファイルは

1 + 2 + 2² + 2³ + …… + 2^n-1 = 2ⁿ - 1

通りしか存在しない。

Shannon (1948): A Mathematical Theory of Communication

m 個の文字がそれぞれ出現確率 p₁, p₂, …, p_m で独立に現れるとすると，平均して

Σ p_i log₂ (1 / p_i)

ビット／文字より縮めることはできない。

つまり，2^k 回に1回出現する文字は，k ビットで符号化するのが最適である。

Huffman (1951): A method for the construction of minimum-redundancy codes

• Huffman 符号化

算術符号化 (Elias, Rissanen, Pasco, ...)

LZ77の仲間

LZ77

Jacob Ziv and Abraham Lempel, A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, IT-23(3), 337-343, 1977.

LZSS

James A. Storer and Thomas G. Szymanski, Data compression via textual substitution, Journal of the Association for Computing Machinery, 29(4), 928-951, 1982.

LZSSでは「マハリクマハリタ」を次のように符号化する（文字を8ビットと仮定）

フラグ （1ビット）	文字 （8ビット）	戻り距離 （〜12ビット）	長さ （〜4ビット）
0	マ
0	ハ
0	リ
0	ク
1		4	3
0	タ

LZ78の仲間

LZ78

Jacob Ziv and Abraham Lempel, Compression of individual sequences via variable-rate coding, IEEE Transactions on Information Theory, IT-24(5): 530-536, 1978.

LZW

Terry A. Welch, A technique for high-performance data compression, IEEE Computer, 17(6): 8-19, 1984.

LZW は……

• Unix 標準の圧縮ツール compress に使われた。
• CompuServe が GIF の圧縮形式として採用した。
• MS-DOS上のシェアウェアARC，PKARCとして広く使われた。
• ARCがPKARCを提訴，PKARC敗退。
• Unisys特許で使いにくくなった。

LZARI/LZHUF/LHarc/LHA/Zip/gzip/zlib/PNG

LZARI: 1988年8月27日 奥村晴彦 (算術符号化を使用)
LZHUF: 1988年11月 吉崎栄泰 (Huffman符号化を使用)

フラグ （1ビット）	文字 （8ビット）	長さ （8ビット）	戻り距離 （≧12ビット）
0	マ
0	ハ
0	リ
0	ク
1		3	4
0	タ
9ビット ↓ 算術符号化 or ハフマン符号化			↓ 算術符号化 or ハフマン符号化

日本発：テレビ，車，次は圧縮ソフトか！

LHA won the October 1991 PC Magazine Editor's Choice award as the best data compression utility.

オンラインソフトウェア大賞/フリーソフトウェア大賞

FSP'92	LHA
FSP'93	WTERM
FSP'94	JW_CAD
FSP'95	-
FSP'96	AL-Mail
OSP'97	-
OSP'98-99	Becky! Internet Mail
OSP2000	午後のこ〜だ
OSP2001	-

圧縮ソフト受難

特許 がらみの紛争多し。

• 1988年，Karmarkar特許成立
• 1993年1月，Stac Electronics（後の Stac Software，現 Previo）が Microsoft を提訴。
• 1994年2月，Microsoft敗訴，1.2億ドル？
• 1995年，Unisys がLZW特許で警告
• 1998年，Fraunhofer (と Thomson multimedia) が MP3特許で警告， 1エンコーダあたり$2.5払え（フリーでも）。
  
• 1998年，8hz-MP3 (学生2人によるプロジェクト) は Fraunhofer から $25,000/年 払えというメールを受け取り，やむなく配布を停止。
• 1999年，UnisysがLZW特許で再警告， フリーソフトなどライセンス違反のソフトで作ったGIFを使うサイトは5000ドル払え。 GIFを扱う多数のフリーソフトが消える。 Burn All GIFs などの抗議運動が起こる

ソフトウェア特許については，今野浩 『カーマーカー特許とソフトウェア――数学は特許になるか』（中公新書1278，中央公論社，1995年）参照。

画像・信号圧縮

画像の例: Mona Lisa

DCT

予測誤差符号化

Golomb

Wavelet

浮動小数点データの圧縮

浮動小数で予測誤差（例：差分）を求めても桁数は減らない

Lossy → 整数化（量子化）してから上の方法を使う

Lossless → ビットパターンが同じ整数に変換する

たとえば IEEE 754 single は

1	8								23
符号	指数								仮数

このビットパターンを24ビット整数と見ても，大小関係は元の浮動小数点と同じ。

MSB ← 32ビット → LSB

圧縮テクニック

似たデータをまとめる

データベースの column-wise compression
XML では XMill

モデル化し，予測誤差に変換

松阪大学 奥村晴彦 okumura@matsusaka-u.ac.jp
Last modified: 2002-11-12 22:49:06