乐正

Actions speak louder than words.

Sicp-ex2-69

问题

下面过程以一个符号-频度对偶表为参数(其中没有任何符合出现在多于一个对偶中),并 根据Huffman算法生成出Huffman编码树。

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

其中的make-leaf-set是前面给出的过程,它将对偶表变换为叶的有序集,successive-merge 是需要你写的过程,它使用make-code-tree反复归并集合中具有最小权重的元素,直至集 和里面只剩下一个元素为止。这个元素就是我们所需要的Huffman树。(这个过程稍微有 点技巧性,但并不是很复杂。如果你正在设计的过程变得很复杂,那么几乎可以肯定是在什 么地方搞错了。你应该尽可能地利用有序集合表示这一事实。)

解答

1
2
3
4
5
6
7
8
9
10
(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

(define (successive-merge leaf-set)
  (cond ((null? leaf-set) '())
        ((= (length leaf-set) 1) (car leaf-set))
        (else (successive-merge (adjoin-set
                                  (make-code-tree (car leaf-set)
                                                  (cadr leaf-set))
                                  (cddr leaf-set))))))

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
;; (load 'p112-huffman-tree.scm)

(define sample-tree (generate-huffman-tree (list (list 'A 4)
                                                 (list 'B 2)
                                                 (list 'C 1)
                                                 (list 'D 1))))
;Value: sample-tree

(decode '(0 1 1 0 0 1 0 1 0 1 1 1 0) sample-tree)
;Value 15: (a d a b b c a)

(encode (list 'a 'd 'a 'b 'b 'c 'a) sample-tree)
;Value 16: (0 1 1 0 0 1 0 1 0 1 1 1 0)

draft

« sicp-ex2-68 sicp-ex2-70 »

Comments