SICP 习题参考答案 2.3

win_hate

1. 
   
2. guile> (decode sample-message sample-tree)
   
3. (A D A B B C A)
   

复制代码

win_hate

Exercise 2.68.  The encode procedure takes as arguments a message and a tree and produces the list of bits that gives the encoded message.

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))

Encode-symbol is a procedure, which you must write, that returns the list of bits that encodes a given symbol according to a given tree. You should design encode-symbol so that it signals an error if the symbol is not in the tree at all. Test your procedure by encoding the result you obtained in exercise 2.67 with the sample tree and seeing whether it is the same as the original sample message.

win_hate

1. 
   
2. (define (encode-symbol symb tree)
   
3.   (cond ((leaf? tree) (if (eq? symb (symbol-leaf tree)) '()
   
4.                           (error "bat symbol -- ENCODE-SYMBOL" symb)))
   
5.         ((member symb (symbols (left-branch tree)))
   
6.          (cons 0 (encode-symbol symb (left-branch tree))))
   
7.         (else (cons 1 (encode-symbol symb (right-branch tree))))))
   

复制代码

1. 
   
2. guile> (decode sample-message sample-tree)
   
3. (A D A B B C A)
   
4. guile> (encode '(A D A B B C A) sample-tree)
   
5. (0 1 1 0 0 1 0 1 0 1 1 1 0)
   
6. guile> sample-message
   
7. (0 1 1 0 0 1 0 1 0 1 1 1 0)
   

复制代码

win_hate

Exercise 2.69.  The following procedure takes as its argument a list of symbol-frequency pairs (where no symbol appears in more than one pair) and generates a Huffman encoding tree according to the Huffman algorithm.

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

Make-leaf-set is the procedure given above that transforms the list of pairs into an ordered set of leaves. Successive-merge is the procedure you must write, using make-code-tree to successively merge the smallest-weight elements of the set until there is only one element left, which is the desired Huffman tree. (This procedure is slightly tricky, but not really complicated. If you find yourself designing a complex procedure, then you are almost certainly doing something wrong. You can take significant advantage of the fact that we are using an ordered set representation.)

win_hate

1. 
   
2. (define (generate-huffman-tree pairs)
   
3.   (successive-merge (make-leaf-set pairs)))
   
4. 
   
5. (define (successive-merge leaf-set)
   
6.   (let ((fst (car leaf-set))
   
7.         (rst (cdr leaf-set)))
   
8.     (if (null? rst) fst
   
9.         (let* ((snd (car rst))
   
10.               (new (make-code-tree fst snd)))
    
11.           (successive-merge (adjoin-set new (cdr rst)))))))
    

复制代码

win_hate

Exercise 2.70.  The following eight-symbol alphabet with associated relative frequencies was designed to efficiently encode the lyrics of 1950s rock songs. (Note that the ``symbols'' of an ``alphabet'' need not be individual letters.)

A         2         NA         16
BOOM         1         SHA         3
GET         2         YIP         9
JOB         2         WAH         1
Use generate-huffman-tree (exercise 2.69) to generate a corresponding Huffman tree, and use encode (exercise 2.68) to encode the following message:

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

How many bits are required for the encoding? What is the smallest number of bits that would be needed to encode this song if we used a fixed-length code for the eight-symbol alphabet?

[ 本帖最后由 win_hate 于 2008-12-3 18:00 编辑 ]

win_hate

1. 
   
2. (define L '((A 2) (NA 16)
   
3.             (BOOM 1) (SHA 3)
   
4.             (GET 2) (YIP 9)
   
5.             (JOB 2) (WAH 1)))
   
6. 
   
7. (define SONG-TREE (generate-huffman-tree L))
   
8. 
   
9. (define SONG '(GET A JOB
   
10.                SHA NA NA NA NA NA NA NA NA
    
11.                GET A JOB   
    
12.                SHA NA NA NA NA NA NA NA NA
    
13.                WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP
    
14.                SHA BOOM))
    

复制代码

1. 
   
2. guile> (encode SONG SONG-TREE)
   
3. (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)
   
4. guile> (length (encode SONG SONG-TREE))
   
5. 84
   

复制代码

如果用定长码，需要 36*([log_2 6]+1)=108 个比特。

win_hate

Exercise 2.71.  Suppose we have a Huffman tree for an alphabet of n symbols, and that the relative frequencies of the symbols are 1, 2, 4, ..., 2^{n-1}. Sketch the tree for n=5; for n=10. In such a tree (for general n) how may bits are required to encode the most frequent symbol? the least frequent symbol?

win_hate

• 5 个的
  
  
• 10 个的
  
  

树长成这样，是因为 1+2+...+ 2^i < 2^{i+1}

[ 本帖最后由 win_hate 于 2008-12-4 15:30 编辑 ]

win_hate

Exercise 2.72.  Consider the encoding procedure that you designed in exercise 2.68. What is the order of growth in the number of steps needed to encode a symbol? Be sure to include the number of steps needed to search the symbol list at each node encountered. To answer this question in general is difficult. Consider the special case where the relative frequencies of the n symbols are as described in exercise 2.71, and give the order of growth (as a function of n) of the number of steps needed to encode the most frequent and least frequent symbols in the alphabet.