情報圧縮

情報圧縮 ( Text p.68, 5.11 節 )
情報圧縮とは
対象となる情報の表現を変更する事により、より少ない量で表現する手段
元の情報を失わない「可逆圧縮」と、情報を失う「非可逆圧縮」がある
一般の(符号)表現
全ての表現に対する事象が、同じ確率で生じる事を想定 => 現実と異る
例 : 英語のアルファベット => 「e」が出る確率は 13％ > 3.4% = 1/26
ハフマンコーディング (可逆圧縮の例)
出現確率の高い文字を短い符号で表現すれば全体として短くなる
zip/lzh/gz 等のファイルの圧縮に利用されている
例: A:1/2, B:1/4, C,D:1/8 : ACAABBAD
A,B,C,D : 00,01,10,11 => 00 10 00 00 01 01 00 11 ( 16 bit )
A,B,C,D : 0,10,110,111 => 0 110 0 0 01 01 0 111 ( 14 bit )
ランレングス圧縮
同じ符号が連続して長く出る確率が高い : 文字そのものより出現回数(>2)をかく
例: AAAABDDDDDDC (12 byte) => A4BD6C (6 byte) [元のデータは数字はでないと仮定]