# SICP-2.3.4节练习

lispor posted @ May 03, 2011 03:31:49 AM in Scheme with tags SICP , 2898 阅读

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

(define (weight-leaf 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)

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

(define (weight tree)
(if (leaf? tree)
(weight-leaf 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))

(cond ((null? set) (list x))
((< (weight x) (weight (car set)))
(cons x set))
(else
(cons (car set)

(define (make-leaf-set pairs)
(if (null? pairs)
'()
(let ((pair (car pairs)))
(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))
(tree-12 (make-code-tree leaf-1 leaf-2)))
(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时类似。

```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) (输入验证码)
or Ctrl+Enter