练习 2.69

在书本 111 到 112 页的『生成 Huffman 树』小节,已经很详细地说明了 Huffman 树的生成过程了, generate-huffman-tree 就是这一过程的程序化表示:

;;; 69-generate-huffman-tree.scm

(load "p113-adjoin-set.scm")
(load "p114-make-leaf-set.scm")

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

(define (successive-merge ordered-set)
    (cond ((= 0 (length ordered-set))
            '())
          ((= 1 (length ordered-set))
            (car ordered-set))
          (else
            (let ((new-sub-tree (make-code-tree (car ordered-set)
                                                (cadr ordered-set)))
                  (remained-ordered-set (cddr ordered-set)))
                (successive-merge (adjoin-set new-sub-tree remained-ordered-set))))))

因为 successive-merge 接受的是有序集合(按权重值从低到高排列,用一个列表表示),所以我们可以这样来生成 Huffman 树:

  1. 如果集合的大小为 0 ,那么返回空表 '()
  2. 如果集合的大小为 1 ,那么返回列表的 car 部分,也即是,取出列表中(已经生成完毕)的 Huffman 树
  3. 如果集合的大小大于 1 ,也即是说,集合中至少有两个元素,那么根据集合已排序的原则,列表最前面的两个元素肯定是集合所有元素中权重最少的两个,因此,调用 make-code-tree 组合起这两个元素,得出新子树,并从表示集合的列表中删除这两个元素,得出新集合,然后使用函数 adjoin-tree ,将新子树有序地加入到新集合中去
  4. 一直进行步骤 3 ,直到落入步骤 2 为止

以上步骤最重要的就是使用 adjoin-tree 保持新列表也是有序的,所以组合树的操作可以继续有序地进行。

另外要指出的一点是,当 successive-merge 第一次被调用时,它接受的列表中的所有元素都是树叶,但是之后这个列表里就既有树叶,也有树了,因为我们使用通用的 weight 提取它们的权重,所以不会遇到列表中有两类元素需要处理的麻烦,这也体现了通用操作的威力。

测试:

1 ]=> (load "69-generate-huffman-tree.scm")

;Loading "69-generate-huffman-tree.scm"...
;  Loading "p113-adjoin-set.scm"...
;    Loading "p112-huffman.scm"... done
;  ... done
;  Loading "p114-make-leaf-set.scm"...
;    Loading "p113-adjoin-set.scm"...
;      Loading "p112-huffman.scm"... done
;    ... done
;  ... done
;... done
;Value: successive-merge

1 ]=> (generate-huffman-tree '((A 4) (B 2) (C 1) (D 1)))

;Value 13: ((leaf a 4) ((leaf b 2) ((leaf d 1) (leaf c 1) (d c) 2) (b d c) 4) (a b d c) 8)

讨论

blog comments powered by Disqus