►zthomae’s SICP solutions
▼2 Chapter 2
2.1 Exercise 2.1
2.2 Exercise 2.2
2.3 Exercise 2.3
2.4 Exercise 2.4
2.5 Exercise 2.5
2.6 Exercise 2.6
2.7 Exercise 2.7
2.8 Exercise 2.8
2.9 Exercise 2.9
2.10 Exercise 2.10
2.11 Exercise 2.11
2.12 Exercise 2.12
2.13 Exercise 2.13
2.14 Exercise 2.14
2.15 Exercise 2.15
2.16 Exercise 2.16
2.17 Exercise 2.17
2.18 Exercise 2.18
2.19 Exercise 2.19
2.20 Exercise 2.20
2.21 Exercise 2.21
2.22 Exercise 2.22
2.23 Exercise 2.23
2.24 Exercise 2.24
2.25 Exercise 2.25
2.26 Exercise 2.26
2.27 Exercise 2.27
2.28 Exercise 2.28
2.29 Exercise 2.29
2.30 Exercise 2.30
2.31 Exercise 2.31
2.32 Exercise 2.32
2.33 Exercise 2.33
2.34 Exercise 2.34
2.35 Exercise 2.35
2.36 Exercise 2.36
2.37 Exercise 2.37
2.38 Exercise 2.38
2.39 Exercise 2.39
2.40 Exercise 2.40
2.41 Exercise 2.41
2.42 Exercise 2.42
2.43 Exercise 2.43
2.44 Exercise 2.44
2.45 Exercise 2.45
2.46 Exercise 2.46
2.47 Exercise 2.47
2.48 Exercise 2.48
2.49 Exercise 2.49
2.50 Exercise 2.50
2.51 Exercise 2.51
2.52 Exercise 2.52
2.53 Exercise 2.53
2.54 Exercise 2.54
2.55 Exercise 2.55
2.56 Exercise 2.56
2.57 Exercise 2.57
2.58 Exercise 2.58
2.59 Exercise 2.59
2.60 Exercise 2.60
2.61 Exercise 2.61
2.62 Exercise 2.62
2.63 Exercise 2.63
2.64 Exercise 2.64
2.65 Exercise 2.65
2.66 Exercise 2.66
2.67 Exercise 2.67
2.68 Exercise 2.68
2.69 Exercise 2.69
2.70 Exercise 2.70
2.71 Exercise 2.71
2.72 Exercise 2.72
2.73 Exercise 2.73
2.74 Exercise 2.74
2.75 Exercise 2.75
2.76 Exercise 2.76
2.77 Exercise 2.77
2.78 Exercise 2.78
2.79 Exercise 2.79
2.80 Exercise 2.80
2.81 Exercise 2.81
2.82 Exercise 2.82
2.83 Exercise 2.83
2.84 Exercise 2.84
2.85 Exercise 2.85
2.86 Exercise 2.86
2.87 Exercise 2.87
2.88 Exercise 2.88
2.89 Exercise 2.89
2.90 Exercise 2.90
2.91 Exercise 2.91
2.92 Exercise 2.92
2.93 Exercise 2.93
2.94 Exercise 2.94
2.95 Exercise 2.95
2.96 Exercise 2.96
2.97 Exercise 2.97
    ← prev  up  next → 

2.70 Exercise 2.70

The first thing we need to do is generate the weights from the text of the song. This can be done simply but inefficiently by creating a list of symbol-count pairs that we update as we traverse the list of symbols.

(define (partition-pairs ps key)
  (define (loop front back)
    (cond ((null? back) (cons front back))
          ((eq? key (caar back)) (cons front back))
          (else (loop (cons (car back) front) (cdr back)))))
  (loop '() ps))
(define (generate-weights symlist)
  (define (add-symbol weights symbols)
    (if (null? symbols)
        weights
        (let ((partition (partition-pairs weights (car symbols))))
          (let ((front (car partition))
                (back (cdr partition)))
            (if (null? back)
                (add-symbol (cons (cons (car symbols) 1) front) (cdr symbols))
                (add-symbol (append front
                                    (cons (cons (caar back) (+ 1 (cdar back)))
                                          (cdr back)))
                            (cdr symbols)))))))
  (map (lambda (p) (list (car p) (cdr p))) (add-symbol '() symlist)))

We can set up the tree and the message as such:

(define song
  '(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))
(define song-tree (generate-huffman-tree (generate-weights song)))

Using the pretty-display function (from Racket), we can see the structure of the constructed tree:

> (pretty-display song-tree)

{{leaf na 16}

 {{leaf yip 9}

  {{{leaf a 2} {{leaf wah 1} {leaf boom 1} {wah boom} 2} {a wah boom} 4}

   {{leaf sha 3} {{leaf get 2} {leaf job 2} {get job} 4} {sha get job} 7}

   {a wah boom sha get job}

   11}

  {yip a wah boom sha get job}

  20}

 {na yip a wah boom sha get job}

 36}

Encoding the message is then simple, and we can see that it has a length of 84:

> (length (encode song song-tree))

84

If we used a fixed-length code, we would need to use a code of 3 bits, for 2^3 = 8 symbols. Since there are

> (length song)

36

symbols in the song, we would need 3 * 36 = 108 bits using our fixed-length code. Just like the first example in the chapter, the encoded length with the Huffman tree is 7/9th the length of the fixed-length encoding.

TODO: More about efficiency?

    ← prev  up  next →