SICP 2.3 exercises cont. 4

2.70

(define (successive-merge elements)
  (if (null? (cdr elements)) (car elements)
   (let ((e1 (car elements))
         (e2 (cadr elements))
         (rest (cddr elements)))
     (successive-merge (adjoin-set (make-code-tree e1 e2) rest)))))

(define song (generate-huffman-tree '((A 2) (NA 16) (BOOM 1) (SHA 3) (GET 2) (YIP 9) (JOB 2) (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) song)
(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)

84 bits using huffman encoding above.
fixed length encoding would require 3 bit per word for 36 words, which is 108 bits.

2.71
Just going to have the diagram for n=5 here, as n=10 looks the same, just longer.

huffman

1 bit for the most frequent symbol
n bits for least frequent symbol

2.72
Most frequent symbol will be encoded in O(1) time because it is always the first symbol that the encode procedure encounters as shown in 2.71.

The least frequent symbol will be encoded in O(n^2) time because at each level of the tree, encode must scan through up to n symbols to check which branch to encode, and there are n levels in the tree.

Comments: Finally done with 2.3. These questions made me realized I implemented encode incorrectly as my answer yesterday raises an error inappropriately. In fact I was overcomplicating it as I had forgotten that parent node has information about what symbols are represented by the branch. Correct answer below.

(define (encode-symbol symbol tree)
  (cond ((leaf? tree)
         '())
        ((element-of-set? symbol (symbols (left-branch tree)))
         (cons 0 (encode-symbol symbol (left-branch tree))))
        ((element-of-set? symbol (symbols (right-branch tree)))
         (cons 1 (encode-symbol symbol (right-branch tree))))
        (else (error "No such symbol in tree:" symbol))))
Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s