SICP §2.3.4（Huffman 符号化木 その１）
可変長の符号化体系をどう処理するかというお話。
通信リソースが貴重だった昔は重要だったかもしれんが、インフラ的に恵まれた環境になってきた事と、標準が重視されている現代ではあんまり役にたたなさそうな話題。それとも他に応用できる場面があるんだろうか。。（俺の脳みそではちょっと思いつかないけども。。）
ざっと概要をまとめておこう。
8個の記号（A, B, C, D, E, F, G, H）で構成される電文があったとして、これらを相互に区別するには、固定長コードで３ビット使用すれば全ての記号を表現可能。こんな感じで。
| A | B | C | D | E | F | G | H |
| 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
は、ビット変換するとこんな感じになる。
BACADAEAFABBAAAGAH
合計５４ビット。
001000010000011000100000101000001001000000000110000111
で、世の中には可変長コードというものも存在する。（なんとモールス信号もその一つらしい。初めて知ったよ。）なんでそんなモンが存在するかというと、当然利点があるからなわけだ。
自分はシャーロックホームズシリーズの「踊る人形」で知ったんだが、英語圏の文章、というか単語は、「E」の出現する頻度がもっとも多いらしい。この作品では出現率をキーにしてホームズが暗号を解読していくんだが、「ホームズすげーっ！！」って感心したもんだ。話が横道にそれた。
つーわけで、文字や記号には「出現頻度」というものがまとわりついている。そこに着目すると、出現頻度が高い文字（記号）には短いビット数で判別できる記号を割り当て、その代わりに出現頻度が低い文字（記号）には長めのビット数を割り当てることにより、トータルで使用するビット数を節約することができるわけだ。
但し、可変長コードには弱点がある。それは記号のビットの終端をどう判別するかということ。モールス信号は、記号と記号の間に「分離符号」を置くことで解決している。もう一つの方法として、全ての記号が互いに他の記号の語頭（prefix）と競合しないようなコード体系にすること。この方法を「語頭符号」というらしい。
じゃ、上述の8個の記号を語頭符号の可変長コードで定義してみる。サンプルとして記載した電文では、あからさまにAの出現頻度が高いので、Aが少ないビット数で表現できるようにしてみる。こんな感じ。
| A | B | C | D | E | F | G | H |
| 0 | 100 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
合計４３ビット。約２０％の節約。
1000101001001101100011010100100000111001111
この語頭符号の可変長コードの符号化は簡単にイメージできるけど、復号化はどうするか。ここで今までやってきた二進木が力を発揮する。A〜Hを二進木で表現してみよう。ビットが「0」ならば左へ行き、「1」ならば右へいくという感じで。
| A | 左(0) | 0 |
| B | 右(1)、左(0)、左(0) | 100 |
| C | 右(1)、左(0)、右(1)、左(0) | 1010 |
| D | 右(1)、左(0)、右(1)、右(1) | 1011 |
| E | 右(1)、右(1)、左(0)、左(0) | 1100 |
| F | 右(1)、右(1)、左(0)、右(1) | 1101 |
| G | 右(1)、右(1)、右(1)、左(0) | 1110 |
| H | 右(1)、右(1)、右(1)、右(1) | 1111 |
これを見ると電文の先頭ビットから順番にこの木をたどるようにチェックしていき、記号にたどり着いたらまた木の一番上から続きのビットをチェックしていくことで復号化ができる。こんなマネができるのは「語頭符号」だから。１ビットずつ順にチェックしていけばどこかの葉にたどり着く。
(A B C D E F G H)17
／ ＼
A 8 (B C D E F G H)9
／ ＼
(B C D)5 ＼
／ ＼ ＼
B 3 (C D)2 ＼
／ ＼ ＼
C 1 D 2 (E F G H)4
／ ＼
／ ＼
(E F)2 (G H)2
／ ＼ ／ ＼
E 1 F 1 G 1 H 1
