Define an encoding tree and a sample message:
(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                   (make-leaf 'B 2)
                   (make-code-tree (make-leaf 'D 1)
                                   (make-leaf 'C 1)))))
(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))
Use the decode procedure to decode the message, and give the result.

scheme@(guile-user)> (decode sample-message sample-tree)
(A D A B B C A)

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.

代码：
(define (make-leaf symbol weight)
  (list 'leaf symbol weight))

(define (leaf? x)
  (eq? 'leaf (car x)))

(define (symbol-leaf x)
  (cadr x))

(define (weight-leaf x)
  (caddr x))

(define (make-code-tree left right)
  (list left
        right
        (append (symbols left)
                (symbols right))
        (+ (weight left)
           (weight right))))

(define (left-branch tree)
  (car tree))

(define (right-branch tree)
  (cadr tree))

(define (symbols tree)
  (if (leaf? tree)
      (list (symbol-leaf tree))
      (caddr tree)))

(define (weight tree)
  (if (leaf? tree)
      (weight-leaf tree)
      (cadddr tree)))

(define (choose-branch bit branch)
  (cond ((= bit 0) (left-branch branch))
        ((= bit 1) (right-branch branch))
        (else (error "bad bit -- CHOOSE-BRANCH" bit))))

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
        (let ((next-branch (choose-branch (car bits) current-branch)))
          (if (leaf? next-branch)
              (cons (symbol-leaf next-branch)
                    (decode-1 (cdr bits) tree))
              (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((< (weight x) (weight (car set)))
         (cons x set))
        (else
         (cons (car set)
               (adjoin-set x (cdr set))))))

(define (make-leaf-set pairs)
  (if (null? pairs)
      '()
      (let ((pair (car pairs)))
        (adjoin-set (make-leaf (car pair)
                               (cadr pair))
                    (make-leaf-set (cdr pairs))))))

(define (encode-symbol symbol tree)
  (cond ((and (leaf? tree)
              (eq? symbol (symbol-leaf tree)))
         '())
        ((memq symbol (symbols (left-branch tree)))
         (cons 0 (encode-symbol symbol (left-branch tree))))
        ((memq symbol (symbols (right-branch tree)))
         (cons 1 (encode-symbol symbol (right-branch tree))))
        (else
         (error "bad symbol -- ENCODE-SYMBOL" symbol))))

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


(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree (make-leaf 'B 2)
                                  (make-code-tree (make-leaf 'D 1)
                                                  (make-leaf 'C 1)))))

(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))

运行结果：
scheme@(guile-user)> sample-message
(0 1 1 0 0 1 0 1 0 1 1 1 0)
scheme@(guile-user)> (define message (decode sample-message sample-tree))
scheme@(guile-user)> (encode message sample-tree)
(0 1 1 0 0 1 0 1 0 1 1 1 0)

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.)

(define (successive-merge leaf-set)
  (if (= 1 (length leaf-set))
      (car leaf-set)
      (let* ((leaf-1 (car leaf-set))
             (leaf-2 (cadr leaf-set))
             (tree-12 (make-code-tree leaf-1 leaf-2)))
        (successive-merge  (adjoin-set tree-12
                                       (cddr leaf-set))))))

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

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?

huffman 编码需要84个二进制位，而定长编码最少需要108个二进制位：
scheme@(guile-user)> (define frequency-pairs '((a 2)
                                               (na 16)
                                               (boom 1)
                                               (sha 3)
                                               (get 2)
                                               (yip 9)
                                               (job 2)
                                               (wah 1)))
scheme@(guile-user)> (define 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))
scheme@(guile-user)> (define tree (generate-huffman-tree frequency-pairs))
scheme@(guile-user)> (length (encode message tree))
84
scheme@(guile-user)> (* 3 (length message))
108

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?

n=5时：

                     {a b c d e} 31
                     /           \
                {a b c d} 15      e 16
                 /     \
           {a b c} 7    d 8
             /    \
        {a b} 3    c 4
         /   \
      a 1    b 2
n=10时，与n=5时类似。
编码最频繁的符号只用1位二进制位
而最不频繁的符号用了n-1位。

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.

最频繁的符号 O(n)
最不频繁的符号 O(n^2)

• SICP-2.3.3节练习
• SICP-2.3.2节练习
• SICP-2.3.1节练习
• SICP-2.2.4节-wave代码
• SICP-2.2.4节练习

• 魔法书1.1补充：平方根算法的论证
• sicp 1.2.2 迭代的费波那契
• sicp 1.11
• 正则序和应用序
• 立方根程序