問題2-70 (2.3.4 Example: Huffman Encoding Trees)

こういう単語とその頻度を用いて、

((A 2) (BOOM 1) (GET 2) (JOB 2) (NA 16) (SHA 3) (YIP 9) (WAH 1))

この歌詞をエンコードする。

Get a job

Sha na na na na na na na na

Get a job

Sha na na na na na na na na

Wah yip yip yip yip yip yip yip yip yip

Sha boom

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-16.html#%_sec_2.3.4

実行すると、こんな結果が得られました。

(define code-tree
  (generate-huffman-tree '((A 2) (BOOM 1) (GET 2) (JOB 2)
			   (NA 16) (SHA 3) (YIP 9) (WAH 1))))
(encode '(GET A JOB 
	      SHA NA NA NA NA NA NA NA NA 
	      GET A JOB 
	      SHA NA NA NA NA NA NA NA NA 
	      WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP 
	      SHA BOOM) 
	code-tree)
; (1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1)

表現するためには、全部で84bit必要みたいです。

もしこれを固定長符号でエンコードするとすると、1つの単語に3bitが必要で、全部で36単語ありますから、108bitが必要なはずでした。