データ圧縮

CoverAndThomasの5章を中心にまとめる。アルゴリズム

Elements of Information Theoryの三章〜八章 - なーんだ、ただの水たまりじゃないか の5章に詳しいメモがある。

Source Code

あるRandom Variable Xに対し、D種類のアルファベットをつなげた有限の文字列D*を対応させる。この対応させた文字列をsource codeという。

あるXの値xに対して、C(x)で対応するコードの文字列（codeword）を表すとしこのC(x)の長さをl(x)で表す。

圧縮で議論されるのは、このlの期待値L(C)。

Nonsingular

コードがnonsingularであるとは、Cが単射である事。（違うxが同じコードにならない）

Uniquely Decodable

C(x1x2x3...) = C(x1)C(x2)...

と定義した時（これをextensionと言う）、これがnonsingularな事をuniquely decodableと呼ぶ。

Prefix Code（instantaneous codeとも言う）

どのcodewordも他のcodewordのprefixになってないコードをPrefix Codeと言う。これは一致した瞬間にそれより後ろを見ずjにcodewordが決定するという事。

Kraftの不等式(5.2)

任意のprefix codeは、以下の式を満たす。

PngNote1

証明のメモ

上のツリーを参照。prefix codeという条件は、あるコードが他のコードの親になってない、という事なので、何かのコードワードになっていたら、その子どもは全部無いものとして考えられる。

式5.7は、あるシンボルのコードの長さがliとして、その下にlmaxまでの仮想的な足を全部生やすといくつになるか、という風に考える。 これが5.7式のシグマの中。

子どもが全部居たとしてもそれはlmaxまでの木の部分木のはずなので、それらを全部足してもレベルlmaxまでの木の葉の数よりは小さくなる。 これが式5.7の意味。