目次
ファイルの圧縮
ファイルはバイト単位で記録
1byte = 8bit = 00000000~11111111 = 0~255
ファイルはバイトデータの集まり
例：文書ファイル(値は適当)
こんにちは ↓ 実体 01010000 01000111 00001011 10101101
例：画像ファイル(値は適当)
画像 ↓ 実体 01010000 01000111 00001011 10101101
ランレングス法の仕組み
「データ * 繰り返し回数」で圧縮
例：AAAAAABBCDDEEEEEF(17byte)を圧縮
AAAAAABBCDDEEEEEF (17byte) ↓ ランレングス法 A6B2C1D2E5F1 (12byte)
ハフマン法
- 使われる文字のバイト数を小さくして
- 使われない文字のバイト数は大きくする
例：Aを100回、Qを3回使ってる文章ファイル
悪い例：AもQも8bit
A(8bit) * 100回 + Q(8bit) * 3回 = 800bit + 24bit = 824bit
良い例：Aは2bit、Qは10bit
A(2bit) * 100回 + Q(10bit) * 3回 = 200bit + 30bit = 230bit
824→230とかなり小さくできた
ハフマン法の手順
- ファイル毎に最適な符号体系を構築(ハフマン符号を作成)
- ハフマン符号を基に圧縮
| 圧縮前のファイル | 圧縮後のファイル |
|---|---|
| 圧縮前のデータ | ハフマン符号 |
| 圧縮されたデータ |
例：AAAAAABBCDDEEEEEFをハフマン法で圧縮
データの出現頻度を並べる
出現頻度 6 5 2 2 1 1 データ A E B D C F 出現頻度の少ない方から2つ選び、数値を合計して上に伸ばす
1 2 出現頻度 6 5 2 2 1 1 データ A E B D C F 手順2を繰り返す。どの位置にある数値を選んでもOK
1 4 2 出現頻度 6 5 2 2 1 1 データ A E B D C F 2 6 1 4 2 出現頻度 6 5 2 2 1 1 データ A E B D C F 2 6 1 11 4 2 出現頻度 6 5 2 2 1 1 データ A E B D C F 3 17 2 6 1 11 4 2 出現頻度 6 5 2 2 1 1 データ A E B D C F 数値が1つになったら左に0、右に1を書く
3 17 bit 0 1 2 6 bit 0 1 1 11 4 2 bit 0 1 0 1 0 1 出現頻度 6 5 2 2 1 1 データ A E B D C F 上位桁から並べたものがハフマン符号になる
3 17 bit 0 1 2 6 bit 0 1 1 11 4 2 bit 0 1 0 1 0 1 出現頻度 6 5 2 2 1 1 データ A E B D C F ハフマン符号 00 01 100 101 110 111
上記の表だと、以下になる
AAAAAABBCDDEEEEEF
=
0000000000001001001101011010101010101111
17byteから5byteに圧縮成功
