SICP §2.3.4（Haffman 符号化木 その２ [Haffman 木の生成]）

前エントリで作成した Haffman 木、及び各記号（アルファベット）に割り当てる符号についてだけど、これは一体どうやって作るのか。本セクションでは割り当てる符号の最適性は割愛されているが、Haffman 木の構成方法についてはまとめられていたので俺もまとめておこう。（語頭符号化は面倒くさそうだよね。）

電文中の記号の出現頻度（相対頻度）に着目する。前エントリで記載しておいた電文、

BACADAEAFABBAAAGAH

について、各記号毎の出現頻度を解析するとこんな感じ。

{(A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)}

こいつらに対して、もっとも出現頻度が低い要素を２つ探す。発見したらその２つを左右の枝とする枝を作る。これを繰り返していき、最終的に要素が１つになったら完了。
じゃ、このアルゴリズムに従って上のリストを変形させていってみよう。

↓元ネタ

{(A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)}

↑このリスト中でもっとも出現頻度が低いのは、C,D,E,F,G,Hの１回。
１回の合体で一つの木を作ると、この中から任意に２つ選べる。
任意に選べるんだが、変形の見やすさの為に、C と D に着目するとこんな感じになる。

　　　　　　　　↓↓

{(A 8) (B 3) ({C D} 2)   (E 1) (F 1) (G 1) (H 1)}
　　※！！注意！！

　　　本当は任意に選ぶのだから、C と H を組み合わせる、こんな変形もまた真になる。

　　　　　{(A 8) (B 3) ({H C} 2) (D 1) (E 1) (F 1) (G 1)}

　　　同一の出現率の要素であれば、組み合わせも、右も左も任意ってこった。

　　　これは、同一アルゴリズムでも生成される木が一意に決まるとは限らないことを意味する。

同じように考えると、次のターゲットは E と D。

　　　　　　　　　　　　　　　↓↓

{(A 8) (B 3) ({C D} 2)   ({E F} 2)   (G 1) (H 1)}

繰り返して G と H を合体、

　　　　　　　　　　　　　　　　　　　　　↓↓

{(A 8) (B 3) ({C D} 2)   ({E F} 2)   ({G H} 2)}

次に出現頻度が少ないのは、{C D} の枝、{E F} の枝、及び {G H} の枝。やはり任意の組み合わせで合体できるが、変形の過程を見やすくする為に {E F} の枝、及び {G H} の枝を合体させる。

　　　　　　　　　　　　　　　　↓↓

{(A 8) (B 3) ({C D} 2)   ({E F G H} 4)}

次の出現頻度が低い枝は B 及び {C D} なのでこうなる。

　　　　　↓↓

{(A 8) ({B C D} 5)       ({E F G H} 4)}

同じく次に出現頻度が低いのは、{B C D} と {E F G H}。

　　　　　　　　↓↓

{(A 8) ({B C D E F G H} 9)}

最後は一つの要素にしちゃう。

　　　　　↓↓

{({A B C D E F G H} 17)}

おしまい。