2.3 Symbolic Data - CloneableX/SICP-learning GitHub Wiki

目前为止，接触过的复合数据对象都是由数字组成，而本节将介绍通过字符标识构造数据的能力。

可以按照下列方式使用标识构造复合数据：

(a b c d)
(23 45 17)
((Norah 12) (Molly 9) (Anna 7) (Lauren 6) (Charlotte 4))

上述构造的列表中包含了标识，就像人类语言的表达方式一样：

(* (+ 23 45)
   (+ x 9))
(define (fact n)
  (if (= n 1) 1 (* n (fact (- n 1)))))

为了方便标识的维护，我们需要在编程语言中添加一个新元素，它的能力是引用数据对象。假设需要构建列表 (a b)，不能使用 (list a b)，因为这表示 a 和 b 的值构建的列表，而不是由标识构建的列表。在自然语言中也存在同样的问题，词语和句子即可以视作语义实体也可以视作语法实体。自然语言通过引号标识词语或句子表示语法实体。例如，"John" 的第一个字符为 "J"；如果你向某人说 "大声说出你的名字"，其实是希望听到对方说出自己的名字，但如果表示为 "大声说出 ’你的名字'"，则是希望对方说出 "你的名字"。这个例子中通过内嵌的引号表示需要其他人表述的内容。

参考上述自然语言的实践，在编程语言中也可以声明应该被视作数据对象而不是计算结果的列表和标识。不过在编程中使用的引号有些不同，通常是在被引用对象的开头使用单个「'」表示。由于 Scheme 是依靠空格和小括号分隔变量和表达式，所以使用单个引号并不会引进混淆。

这样我们便可以在 Scheme 中区分标识和它们对应的值了：

(define a 1)
(define b 2)
(list a b)
(1 2)
(list 'a 'b)
(a b)
(list 'a b)
(a 2)

引用也可应用于复合对象中，按照列表的打印形式即可表示列表：

(car '(a b c))
a
(cdr '(a b c))
(b c)

同理，'() 便可以表示空列表，所以可以省掉变量 nil。

另一个标识的基础程式是 eq?，它会比较两个标识是否相同。利用 eq? 能够实现程式 memq，它接收一个标识和一个列表作为参数，然后判断列表中是否包含指定标识。如果列表中不包含标识 memq 将返回 false，如果包含标识，将返回以此标识起始的子列表。

(define (memq item x)
  (cond ((null? x) false)
         ((eq? item (car x)) x)
         (else (memq item (cdr x)))))

(memq 'apple '(pear banana prune))
false

(memq 'apple '(x (apple sauce) apple pear))
(apple pear)

为了进一步说明标识的维护和数据抽象，我们将设计一个程式用于对任意表达式的指定标识进行微分运算。此程式将接收一个任意表达式和变量，然后返回表达式基于变量的微分结果。例如，当参数是 和 x 时，返回的结果为 2ax+b。微分标识是 Lisp 中的一个历史性标志，它不断鼓励着居于幕后的计算机编程开发人员开发标识相关操作。同时，它也是标识运算系统研究方向的开端，如今相关理论已经应用在大量的数学和物理学领域。

在开发微分标识的系统中，需要继续沿用数据抽象的策略，就像在建造有理数系统时一样。所以，首先要定义一个微分算法和一系列供此算法应用的抽象对象，比如加法、乘法和变量等，这一系列的数据将如何表示是后面要解决的问题，现在暂时不用关心。

为了保证事情在一开始时不要过于繁杂，我们目前设计的微分程式只处理两数相加或两数相乘的表达式。也就是说此程式可应用于满足下列规则的表达式：

c 是一个常量或者不同于 x 的变量

最后两个规则是天然递归的。以加法的微分规则为例，要计算加法的微分结果需要先计算每一项加数的微分结果，再将其相加。其中的加数可能是需要分解的表达式，不断分解直到结果为常数、变量或者微分为 0 或 1。

如果要通过程序表达上述规则需要依靠一些假设性思考，就像在设计有理数系统时一样。假设此时已经存在方法可表示任意表达式，于是便可以判断此表达式是加法、乘法、常量或变量，并且还可以提取表达式的各个组成部分。对于加法而言，需要提取加数和被加数。反过来使用这些组成部分也可以还原表达式。此时，先假设已经实现了下列选择器、构造器和判断方法：

(variable? e)
(same-variable? v1 v2)
(sum? e)
(addend e)
(augend e)
(make-sum a1 a2)
(product? e)
(multiplier e)
(multiplicand e)
(make-product m1 m2)

利用上述程式及基础程式 number?（可判断参数是否为数字），可将微分规则实现为下列程式：

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp) (if (same-variable exp var) 1 0))
        ((sum? exp) (make-sum (deriv (addend exp) var)
                              (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (multiplicand exp)
                         (deriv (multiplier exp) var))))
        (else
         (error "unknown expression type: DERIV" exp))))

deriv 程式包含了完整的微分算法。只要完成将表达式中的元素抽象为数据的工作，它便可以完美运行，在这之前还需要处理一个问题。

我们能够想象到有许多种方式可以通过列表表示表达式。例如，将表达式的所有符号转换为同样的符号标识存储于列表中，也就是说表达式 ax+b 可表示为列表 (a * x + b)。不过还可以使用更加直接的表达方式，直接使用 Lisp 中的小括号和运算符前缀表示法，表达式 ax+b 表示为 (+ (* a x) b)。于是关于微分问题的相关数据可按如下表示：

• 变量标识可以通过基础程式 symbol? 判断：(define (variable? x) (symbol? x))
• 如果变量都是标识类型，则可以通过 eq? 判断它们是否相等：

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

• 加法和乘法都以列表形式构造：

(define (make-sum a1 a2) (list '+ a1 a2))
(define (make-product m1 m2) (list '* m1 m2))

• 加法以 + 号作为列表的首个元素：

(define (sum? x) (and (pair? x) (eq? (car x) '+)))

• 加数是加法列表的第二个元素：

(define (addend s) (cadr s))

• 被加数是加法列表的第三个元素：

(define (augend s) (caddr s))

• 乘法列表的第一个元素是 *：

(define (product? x) (and (pair? x) (eq? (car x) '*)))

• 乘数是乘法列表的第二个元素：

(define (multipliter p) (cadr p))

• 被乘数是乘法列表的第三个元素：

(define (multiplicand p) (caddr p))

接着，只需要将这些程式与 deriv 结合即可，让我们展示一下它的效果：

(deriv '(+ x 3) 'x)
(+ 1 0)
(deriv '(* x y) 'x)
(+ (* x 0) (* 1 y))
(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* (* x y) (+ 1 0))
   (* (+ (* x 0) (* 1 y))
      (+ x 3)))

虽然运算结果都正确，但结果还可以简化，比如 ，众所周知 x*0=0 1*y=y 0+y=y，所以第二个示例的答案应该被简化为 y。如果不进行简化，将会在遇到复杂表达式时产生复杂的结果。

在有理数的实现中也遇到过同样的问题，当时为了实现对有理数的简化我们对有理数的构造器和选择器的实现进行了修改。目前微分程序遇到的问题也适配类似的解决方案，根据目前的情况可以优先考虑修改 make-sum 程式，当加数是 0 时应该特殊处理：

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2))
         (+ a1 a2))
        (else (list '+ a1 a2))))

其中 =number? 可实现为如下程式：

(define (=number? exp num) (and (number? exp) (= exp num)))

同样，也可以在 make-product 的乘数出现 0 或 1 时特殊处理：

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list '* m1 m2))))

下面是修改后程式运算效果：

(deriv '(+ x 3) 'x)
1
(deriv '(* x y) 'x)
y
(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* x y) (* y (+ x 3)))

虽然这是一个相当大的改进，但第三个例子说明运算结果尚未达到最简。因为代数简化的问题十分复杂，对于一种使用目的是最简形式，但对于另一种使用目的来说可能就不是。

在此之前本书已经展示了两种复合数据对象的表示方式，分别是有理数和代数表达式。在这两个例子中都对表达式进行了简化，通常是在构造器或选择器中处理，而数据对象的结构通常使用列表的方式表示。如果通过集合表示相应的复合数据对象，就难以达到让人轻易理解的效果。使用集合当然也是一种表示数字的方式，不过它与其他方式有所不同。

通俗地讲，集合就是一组非重复的对象组成的集合。如果要进行更加精确的定义需要通过数据抽象方法。假设我们通过 set 定义集合，相应地存在一系列方法，union-set、intersection-set、element-of-set? 和 adjoin-set。其中 element-of-set? 用于判断一个元素是否存在于集合中。adjoin-set 将根据提供的对象和集合返回包含该对象的集合以及与它相邻的元素。union-set 能够拼接两个集合，intersection-set 将返回两个集合的交集。从数据抽象的角度来看，我们可以自由设计集合的表示方式，只要能够符合上述程式的解释即可。

其实集合可以视作没有重复元素的列表，而空集合就是空列表。按照这种表示方式，element-of-set? 与 memq 的功能相似，不过它使用 equal? 而不是 eq?，这样可以避免必须通过标识进行运算。

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))

按照这个思路继续编写 adjoin-set。如果一个对象已经存在于集合中，程式将返回集合，否则将通过 cons 把对象添加至集合中。

(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))

对于 intersection-set 需要运用递归策略。如果已经知道 set2 与 (cdr set1) 交集的形成过程，那么只需要决定 (car set1) 是否包含在交集中，不过这有赖于 (car set1) 是否包含于 set2 的判断。所以按此过程实现的程式如下：

(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)
         (cons (car set1) (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))

在设计表示方式的过程中，计算效率的问题也需要同时观注。目前其他的集合操作都基于 element-of-set? 程式，所以它的执行效率将会影响整个集合系统。element-of-set? 的实现方式导致每次检测一个对象是否存在于集合中时要扫描整个集合。所以 element-of-set? 的时间增长为 O(n)，adjoin-set 也使用了此程式，所以时间增长也为 O(n)。对于 intersection-set，检测 set1 中是否包含指定对象的次数由另一个集合决定，所以时间增长为 O(n^2)，对于 union-set 也是同样的时间增长。

为了提升集合操作的效率，可以将集合用递增排序的列表表示。要实现这种表示方式，需要设计一个方法能够比较两个对象的大小。比如，按字典序比较标识，按复合对象中的数字元素比较复合对象等。为了保证接下来的讨论易于理解，目前只考虑数字集合，所以可以通过 < 和 > 比较集合中元素的大小。

按照通过有序列表表示集合的方法，element-of-set? 可以进行这样的优化。当检测集合中是否包含某元素时，并不需要检测整个集合，如果在集合中遇到比当前对象大的元素，便知道当前集合中不包含此对象。

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (car set)) true)
        ((< x (car set)) false)
        (else (element-of-set? x (cdr set)))))

上述程式在最差情况下还是需要扫描整个集合，所以它的时间增长与无序列表的实现一样。不过如果考虑更多情况的集合时，目前实现的检测可能会出现在集合的首个元素检测时或集合的中间元素检测时就结束对集合的扫描。根据大量的实验花费的时间是集合大小的一半，所以花费时间是 n/2，时间增长依然是 O(n)，但与之前的实现相比已经提高了两倍的效率。

接着对 intersection-set 进行优化。在无序列表的实现中此程式的时间增长是 O(n^2)，但基于有序列表时可以使用更智慧的实现。实现过程是这样，首先比较两个集合的首个元素 x1 和 x2，如果 x1 等于 x2 则当前元素是交集中的一员，然后交集中的其它部分属于两个集合的剩下元素。假设 x1 小于 x2，并且 x2 是 set2 中的最小元素时，可得出结论 x1 不可能等于 set2 中的任意元素，所以 x1 肯定不存在交集中。于是，交集应该从 (cdr set1) 与 set2 中取。同样的道理，如果 x2 小于 x1，并且 x1 是 set1 中的最小元素，那么交集应该存在于 set1 与 (cdr set2) 之间。具体实现如下：

(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
      '()
      (let ((x1 (car set1)) (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1 (intersection-set (cdr set1) (cdr set2))))
              ((< x1 x2) (intersection-set (cdr set1) set2))
              ((< x2 x1) (intersection-set set1 (cdr set2)))))))

为了计算此程式的时间增长，需要观察每一步对集合做出的缩减操作，也就是对集合首个元素的移除。所以，该程式的最差情况为 set1 与 set2 的大小之和，时间增长为 O(n)，相比之前时间增长为 O(n^2) 的实现效率已经得到了可观的提升。

除了有序列表外，集合还有更好的表现形式，就是使用二叉树表示。二叉树的每个节点都持有一个集合的元素，该元素称为节点的条目，同时节点还链接另外两个节点（也可能是空节点）。其中节点链接的左分支节点的条目小于当前节点的条目，链接至右分支的节点的条目大于当前节点的条目。就如同下图展示的一样，并且相同的集合会因为根节点条目的不同形成不同的二叉树，不过无论如何变化形态都依然遵循左右分支的规则。

使用树形结构表示集合的优势在于可以提升检测集合中是否包含某元素的效率。假设当前打算检测数字 x 是否存在于集合中，在树形中可以先与顶点比较。如果 x 小于顶点条目，则只需要继续搜索左分支；相反，则只需要搜索右分支即可。现在，如果集合构建的是棵平衡二叉树，则每个子树都是上一组二叉树的一半。所以在每一步的搜索中，都是以二分的方式查找，时间增长为 O(log n)。对于规模较大的集合，效率提升的效果更加明显。

如果要表示树形结构可以通过列表。每个节点都表示为一个拥有三个元素的列表，三个元素分别表示当前节点的条目，左分支和右分支。如果分支不存在通过空列表表示，按此规则实现的程式如下：

(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
  (list entry left right))

接着按一开始描述的过程实现 element-of-set? 程式：

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (entry set)) true)
        ((< x (entry set))
         (element-of-set? x (left-branch set)))
        ((> x (entry set))
         (element-of-set? x (right-branch set)))))

添加元素的实现方式也是相似的，时间增长为 O(log n)。当需要添加数字 x 时，先将 x 与树的顶点比较，再确定将 x 添加至左分支还是右分支。如果 x 与某个节点的条目相等，则返回此节点即可。如果将 x 添加至空二叉树，则需要生成左右分支都为空列表的节点。下列是具体实现：

(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree (entry set)
                    (adjoin-set x (left-branch set))
                    (right-branch set)))
        ((> x (entry set))
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-set x (right-branch set))))))

之前对于 element-of-set? 的时间增长计算是基于集合构成的二叉树是平衡二叉树的假设之上，也就是说左右分支的节点数量基本一致，所以每个分支都包含上一级树形的一半节点。但是，应该如何保障二叉树构建时的平衡性呢？即使一开始集合形成的是一棵平衡二叉树，但通过 adjoin-set 添加元素可能会破坏它的平衡性。在向集合添加元素时，是基于被添加元素与当前节点的大小比较，假如添加的元素是完全随机的，最后整棵树依然会趋于平衡，但这并不是绝对的事件。例如，向空二叉树添加 1 到 7 的数字时，整棵树最后的形态会变得极度不平衡，如下图所示。最后形成的二叉树左分支完全为空，数字全部有序排布在右分支，此时二叉树演化为了有序列表的表示方式。其中一种解决方案是定义一个程式能够将任意二叉树转换为平衡二叉树，然后在每次完成 adjoin-set 操作后通过此程式保持二叉树的平衡性。另外的解决方案是再设计一种数据结构表示集合，并使搜索和添加的时间增长都为 O(log n)。

目前我们已经实验了几种通过列表表示集合的方案，并且对比了不同实现方式的集合在使用时的性能差异，并且它也是后续会不断在涉及信息检索的应用中出现的技术话题，这是在本节要讲解集合的原因。

假设有一个数据库，其中存在大量的记录，比如公司的个人文件或会计系统中的交易记录。基于这些数据会存在一种经典的数据管理系统，它将高频次地探索和修改这些记录中的数据，所以需要一个极高性能的搜索方法。此方法可以通过定位记录的键（键也是记录的一部分）查找数据，键可以是任何形式，不过它必须能够唯一标识某个数据。对于个人文件，键可以是员工的 ID 号码；在会计系统中，键可以是交易编号。无论键用什么表示，都可以通过键的选择器程序从一条记录中获取键。

现在我们通过一组记录表示数据库，然后通过程式 lookup 根据键定位数据记录，如果对应键的记录存在则返回此条记录，否则返回 false。lookup 的实现与 element-of-set? 相似，假如这组记录通过无序列表实现，则 lookup 的具体实现如下：

(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) false)
        ((equal? given-key (key (car set-of-records)))
         (car set-of-records))
        (else (lookup given-key (cdr set-of-records)))))

不过肯定有更好的方式可以表示大量的数据。实现随机访问记录的信息检索系统通常是基于树形结构实现，例如之前讨论过的二叉树。数据抽象的方法论在系统的设计中也能够起到极大的帮助。设计师能够通过简单直接的方式进行基础版本的实现，比如使用无序列表。虽然与最终系统的实现有所区别，但它能够快速但还不够好地实现系统的基础数据便于对系统的其他功能进行测试。不过在稍后的版本中，数据的表现方式将变得更加复杂，如果基础数据的操作是通过它的构造器和访问器运行，那么无论数据的表现方式如何变化系统的其他实现都不需要修改。

本部分内容将展示一个列表结构使用的实例，以及用于维护集合和树的数据抽象。这个应用是通过零和一的序列表示数据的方法。例如，用于在计算机中表示文本的 ASCII 码每个字符都是组 7 字节的序列。通过 7 个字节的序列可以区分 128 个不同的字符。通常情况下，如果我们打算区分 n 个不同的标识，只需要使用 个字节表示一个标识即可。如果一段信息由 A、B、C、D、E、F、G、H 这 8 个标识组成，则每个字符用三个字节表示即可，例如：

A 000 C 010 D 100 G 110
B 001 D 011 F 101 H 111

基于上述编码「BACADAEAFABBAAAGAH」可转换为下列 54 个字节：

001000010000011000100000101000001001000000000110000111

上述谈到的 ASCII 码和 A 至 H 的编码都是定长编码，这种编码方式表示每个标识都使用相同长度的字节码表示。不过，有时使用变长编码更加有利。例如，摩斯密码并没有相同数量的点和横线表示字符，其中的 E 只需要一个单独的点就能够表示。也就是说，如果基于字符的使用频率提供不同长度的编码，在使用时将会更加高效。A 到 H 的编码按此规则修改为下列形式：

A 0 C 1010 E 1100 G 1110
B 100 D 1011 F 1101 H 1111

如果使用这种编码，同样的信息将转换为下列代码：

100010100101101100011010100100000111001111

上述代码只有 42 个字节，它比原先的表现形式节省的 20% 的空间。

使用变长编码的难点在于通过字节码检索标识的结束边界。摩斯密码通过一段特殊的分隔代码解决此问题，另一种解决方案是将每个字符的代码设计为不是其他字符的开头（或者前缀）。以上述例子为例，A 和 B 的编码分别是 0 和 100，所以其他字符的编码不能以 0 或 100 开头。

一般来说，在使用变长编码时，根据其在当前信息中的出现频率给定相应的前缀会使编码效率得到提升，这种方法被称为霍夫曼编码法。霍夫曼编码使用二叉树表示，叶子表示被编码的字符，每一个非叶子节点包含一组叶子。并且，每一个叶子节点都被分配了一个权重（也就是此标识的相对频率），每一个非叶子节点的权重是其所有叶子节点权重之和。权重信息并不会用于编码或解码过程，它只是用来帮助构建树。

下图展示了 A 到 H 编码的霍夫曼树。叶子节点中的权重表示 A 在给定信息中出现了 8 次，B 出现了 3 次，其他字符都只出现了 1 次。

在霍夫曼树中能够找到每个标识的编码。转换编码的过程是这样，首先从树的根节点开始查找，并不断向下寻找，直至找到标识所处的叶子节点为止。当每次向左分支移动时为编码添加 0，向右分支移动时为编码添加 1。

解码时从树的根节点开始，按照零与一的序列进行左右分支的移动，直到找到叶子节点为止，每当到达叶子节点，都将对应的标识加入结果中，然后再继续从树的根节点解码下一个标识。

我们如何根据标识出现的频率构建霍夫曼树呢？也就是说，如何使用最少的字节长度表示一段信息。霍夫曼提供了一种算法根据标识出现频率进行编码的构建，但无法保证它是最优的霍夫曼编码算法，只是单纯展示霍夫曼树的构建过程。

霍夫曼树的构建方式十分简单，只要遵循将出现频率最少的标识放置在距离根节点最远的地方的原则即可。首先构建叶子节点，它包含标识及标识的出现频率，并将它们放入集合中管理。接着将权重最低的两个节点合并形成一个新节点，并且这两个节点分别位于新节点的左右分支，新节点的权重就是当前两个节点的权重之和。然后将这两个叶子节点从叶子节点的集合中移除，并使用新节点替代它们。重复上述合并节点的步骤，直到集合中只剩下一个节点即可，此时剩下的节点就是霍夫曼树的根结点。

上述算法可能不止形成一棵树，因为在合并节点的步骤中可能存在多个相同数值的最小节点。这种情况合并下的分支选择将是随机的。

在下面的练习中，我们将构建一个系统进行霍夫曼编码和解码，以及构建霍夫曼树。首先需要讨论霍夫曼树应该如何表示。

树的叶子节点通过标识 leaf 表示，它包含叶子中标识和权重：

(define (make-leaf symbol weight) (list 'leaf symbol weight))
(define (leaf? object) (eq? (car object) 'leaf))
(define (symbol-leaf x) (cadr x))
(define (weight-leaf x) (caddr x))

通常来说，树形结构会有一组左分支和右分支，以及标识集合和权重，其中标识集合使用列表表示。当将两个节点合并为树时，树的权重为两个节点的权重之和，以及由两个节点中的标识合并成的标识组合（其中的标识应该是唯一的）。不过目前的实现中标识集合使用列表表示，所以先使用 append 程式保证列表元素的唯一性。

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

symbols 和 weight 对根节点进行了类似的特殊处理，这是通用程式的简单示例，在稍后的章节我们将进行深入探讨。

解码算法的实现如下：

(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 (choose-branch bit branch)
  (cond ((= bit 0) (left-branch branch))
        ((= bit 1) (right-branch branch))
        (else (error "bad bit: CHOOSE-BRANCH" bit))))

decode-1 接收两个参数，一个是字节序列，另一个是位于当前树上的节点。它一直在沿着树向下查找，并根据当前字节确定接下来向左分支移动还是向右分支移动。当抵达叶子节点时，将叶子节点的标识加入信息结果中，接着再回到根结点重复此过程。当字节码的数值不是 0 或 1 时将触发 choose-branch 中的错误处理机制。

在霍夫曼树的表示方式中，每个非叶子节点都包含一组标识，目前是使用列表实现。但是，在构建树的算法讨论中，连续合并最小两个节点时需要重复查找集合中的最小元素，所以有序集合更加适合当前情况。

接下来将按权重的递增排序表示节点集合。adjoin-set 向集合添加元素时会比较权重数据，具体实现如下：

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