2015-08-28_huffman.md

内容

2.3.4小节 Huffman编码树

笔记

Huffman是一种变长编码的解决方案，思路也比较简单，就是字符频率高的字符用少的位编码，频率低的用多个位编码。

我们组内经过讨论，发现难点在于如何构造一颗Huffman树，习题2.69也是让我们实现该问题。

这里主要的难点在于如何让Huffman数平衡，不至于出现右子树或左子树的节点个数都为1的情况。

                     {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

右子树节点个数都为1

在习题2.69。中，是基于以下原理实现平衡Huffman数的：

在按升序排列的列表中把最小的两个节点取出，做make-code-tree运算，然后再把得到的结果放回原列表（按权重从小到大），当原列表中只剩下一个节点时，就是我们想要的Huffman树了。

我第一次做2.69时，就做错了，做出的Huffman树会像上面图画的那样，左子树或右子数节点数都为1。

现把这个错误的代码贴出来，因为它实在是太简洁了，删了觉得好可惜😊

(define (successive-merge leaf-sets)
  (if (= 1 (length leaf-sets))
    (car leaf-sets)
    (make-code-tree (car leaf-sets)
                    (successive-merge (cdr leaf-sets)))))