SICP-2.3.4节练习
练习 2.67 - 2.72
练习 2.67
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)
练习 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.
我的解答：
代码：
(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)
练习 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.)
我的解答：
(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)))
练习 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?
我的解答：
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
练习 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?
我的解答：
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位。
练习 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.
我的解答：
最频繁的符号 O(n) 最不频繁的符号 O(n^2)
评论 (0)