]> git.rkrishnan.org Git - sicp.git/blob - src/sicp/ex2_70.rkt
Solution to 4.44. A bit too verbose. Can be improved by better
[sicp.git] / src / sicp / ex2_70.rkt
1 #lang racket
2 (require rackunit
3          "ex2_69.rkt"
4          "ex2_68.rkt")
5
6 (define symbol-pairs '((A 2) (BOOM 1) (GET 2) (JOB 2) (NA 16) (SHA 3) (YIP 9) (WAH 1)))
7
8 (define huffman-tree (generate-huffman-tree symbol-pairs))
9
10 (define test-message '(GET A JOB
11                        SHA NA NA NA NA NA NA NA NA
12                        GET A JOB
13                        SHA NA NA NA NA NA NA NA NA
14                        WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP
15                        SHA BOOM))
16
17 (check = 
18        (length (encode test-message 
19                        huffman-tree))
20        84)
21
22 #|
23 a. Encoding requires 84 bits.
24 b. There are 8 symbols, so we use 3 bits/symbol.
25    (length test-message) is 36. So total length of the encoded
26    song, had it been fixed length code, will be (* 36 3) = 108
27 |#
28