SICPを読む(78) 問題2.67 ハフマン符号化木
ハフマン木に入ります。JPEGやらLHAでも使われてるアルゴリズムだそうです。
前回の二進木と違ってツリーのデータ型が二つに増えたという所が重要なポイント。
ハフマン符号化木
ハフマンさん頭良すぎ。
ハフマン符号化木のポイントは、ツリーを二進数に写像してる点。
0なら左へ。1なら右へ。
つまり、1 1 1 0は、ツリーの右、右、右、左にあるデータを取ってこい。という命令になる。SICPの図で、指折り数えるとわかりやすい。
問題 2.67
復号編。ハフマン符号化木と二進数列から、元の文字に戻すと何になるかという問題。ちゃんと出来たか確認するだけだったり。
(decode '(0 1 1 0 0 1 0 1 0 1 1 1 0) data) ; (A D A B B C A)
この動きは激しく面白いっす。
ツリーの構造が違うと返ってくる値も違う。つまり、0 1 1 0 ...を見ただけでは何処に区切りがあるのかわからない。
問題は木をどうやって作るのか。次が楽しみ。
