ハフマン符号まで。
情報源符号化
情報源に一番近いところで使われるべきもの。情報源から発生した通報(または通報の系列)を、記録系や処理系で利用可能な記号系列に変換すること。- 通報を符号語(0 or 1からなる系列)に変換する
- 符号語の集合を符号という
- 一意複合可能性
- 異なる通報系列が、同一の符号語系列に符号化されないこと
定義はそうだけど、どうやったら証明できるのかな?
- 符号化の仕方によっては、復号の遅延が発生してしまう(大きなバッファが必要になってしまう) => 使いづらい
- 例:YouTubeの再生が全部ダウンロードできないと再生できない
- 瞬時復号可能性
- 符号語の長さが異なっていても、瞬時復号可能な場合もある
- どんなときに瞬時復号可能でなくなるか?
- ある符号語が、他の符号語の最初の部分と一致(語頭となる)するとき
- 「Cのどの復号語も、他の復号語の語頭とならないこと」と「符号Cが瞬時復号可能になる」は必要十分条件!!
- 語頭条件を満たすような符号はどのように作ればよいか?
- すべての符号語を、同じ長さを持つ相違なる系列とする
- 符号語の最後(最初)に特別なパターンを配置する
- しかし、効率が悪い... => 符号木が便利
- 符号木ならば、語頭条件を満たすので瞬時復元可能であることが保証できる
- しかし、符号木の選び方、ラベルの付け方には自由度がある => じゃあ、どれがいいの?
クラフトの不等式
- 語頭条件を満たすなら、クラフトの不等式が成立
- クラフトの不等式を満たす符号語長が与えられたとき、語頭条件を満たしこの符号長をもつ符号を構成可能語頭条件を満たし、この符号長をもつ符号を構成可能
- 「こういう符号が作りたい」 => クラフトの不等式を満たしているかを考えれば可能かどうかは分かる(できるとして、どうやってやればいいかは分からない)
- 4つの符号語で長さ1、2、2、3は1/2 + 1/4 + 1/4 + 1/8 > 1なので不可能であることが分かる
符号の効率について
- 確率を合わせて考えることで、効率のよさを考えよう
- よく起こるものは短く割り当てたいってやつか
- 符号長の(確率による)荷重平均を考える
ハフマン符号
| 確率 | 符号語 | |
|---|---|---|
| A | 0.2 | 00 |
| B | 0.1 | 010 |
| C | 0.3 | 10 |
| D | 0.3 | 11 |
| E | 0.1 | 011 |
平均符号長は2.2bit。等長符号だと3bit必要になってしまう。
- 以下の自由度がハフマン符号化には存在するが、平均符号長は変わらない
- ラベル割り当ての自由度
- 確率が等しい節点選択の自由度
