ビット数計算やら、ステップ数計算やら。 問題 2.70 8つのワードがあるから、2^3で、3ビット必要。固定長符号で考えると歌詞は39ワードあるので、39words*3bit = 117bit必要となる。可変長な符号な場合、88bitに圧縮された。約25%の節約となった。単調な繰り…

今度は木の生成 問題 2.69 何も考えずにやるとこうかな。 (define (successive-merge leaf-set) (define (iter set tree) (if (null? set) tree (iter (cdr set) (make-code-tree (car set) tree)))) (iter (cdr leaf-set) (car leaf-set))) あっさりすぎ?ツ…

符号化に挑戦。 問題 2.68 符号木を元に、(A D A B B C A)を符号化せよ。という問題。ムズそうなので方針を練ります。 方針 符号化でのポイントは、履歴を返すという所。 葉が見付かったら、'()を返します。見付からなかったら#fを返します。枝の検索も同じ…

ハフマン木に入ります。JPEGやらLHAでも使われてるアルゴリズムだそうです。前回の二進木と違ってツリーのデータ型が二つに増えたという所が重要なポイント。 ハフマン符号化木 ハフマンさん頭良すぎ。ハフマン符号 - Wikipediaハフマン符号化木のポイントは…