2.3 符号数据

迄今为止，我们用过的所有复合数据都是从数值出发构造起来的。在这一节我们要扩充语言的表述能力，引进把字符的串（字符串，也简称为串）作为数据的功能。

2.3.1 字符串

前面我们已经把字符串用在函数display和error里（例如在练习1.22），用于显示各种消息。我们也可以从字符串出发构造复合数据，例如可以有下面这样的表：

为了区分字符串与程序里的名字，我们用双引号括起串里的字符序列。例如，JavaScript表达式z表示名字z的值；而JavaScript表达式"z"表示由一个字符构成的字符串，该字符是英语字母表中最后一个字母的小写形式。

通过双引号标记，我们就能区分字符串和名字了：

我们在1.1.6节介绍了针对数的基本谓词===和!==。从现在开始，我们也允许字符串作为===和!==的运算对象：当且仅当两个参数串相同时谓词===返回真，当且仅当两个串不同时谓词!==返回真 。利用===，我们可以实现一个名为member的有用函数。该函数有两个参数，一个串和一个以串作为项的表，或者一个数和一个以数为项的表，如果表中不包含第一个参数（也就是说，表中任何项与它都不同，用===检查），member就返回 null ，否则返回表参数的从该串或数第一次出现位置开始的那个子表。

例如，表达式

的值是 null ，而表达式

的值是list（"apple", "pear"）。

练习2.53 对下面各表达式求值的结果是什么？请分别用盒子记法和表记法说明。

练习2.54 两个表equal，如果它们包含同样元素，而且这些元素按同样顺序排列。例如：

是真，而

是假。说得更准确些，我们可以从数和串的基本等词===出发，以递归的方式定义equal：a和b是equal的，如果它们都是数或者都是串，而且它们满足===；或者它们都是序对，而且head（a）与head（b）是equal的，tail（a）和tail（b）也是equal的。请利用这一思想，把equal实现为一个函数。

练习2.55 JavaScript解释器在读到双引号"后会连续读入字符，直至遇到另一个双引号，把这两者之间的所有字符都当作字符串的内容，不包括这两个双引号本身。如果我们希望一个串里包含双引号，该怎么办呢？为了解决这个问题，JavaScript也允许用单引号作为串标记符，例如'say your name aloud'。这样，在单引号括起的串里就可以写双引号，反之亦然。所以，'say "your name" aloud'和"say 'your name' aloud"都是合法的字符串，但两者中位置4和14的字符不同（从0开始算位置）。根据所用的字体不同，两个单引号和一个双引号有时不容易区分。你可以看清楚下面的表达式并给出它的值吗？

2.3.2 实例：符号求导

为了展示符号操作的情况，也进一步阐释数据抽象的思想，我们现在考虑设计一个函数，它能执行代数表达式的符号求导。我们希望这个函数以一个代数表达式和一个变量作为参数，返回该表达式对该变量的导数。例如，如果送给这个函数的参数是 ax ² + bx + c 和 x ，它就应该返回2 ax + b 。对于程序设计语言Lisp ，符号求导有特殊的历史意义，它是推动人们为符号操作开发计算机语言的最重要实例之一。进一步说，符号求导也是人们为符号数学工作开发功能强大的系统的研究领域的开端。今天有越来越多的应用数学家和物理学家们正在使用符号数学系统。

在开发做符号计算的程序时，我们遵循与2.1.1节开发有理数系统一样的数据抽象策略。也就是说，我们要先定义一个求导算法，令它在一些抽象对象上操作，如“和”“乘积”和“变量”，不考虑这些对象的实际表示，到后面再去关心具体表示的问题。

对抽象数据的求导程序

为使讨论比较简单，现在我们考虑一个非常简单的符号求导程序，它处理的表达式都是通过对两个参数的加法和乘法运算构造起来的。对这种表达式求导可以通过下面几条归约规则完成：

可以看到，这里的最后两条规则具有递归的性质，也就是说，要得到一个和式的导数，我们需要先找出其中各个项的导数，然后把它们相加。这里的每个项又可能是需要进一步分解的表达式。这种分解将得到越来越小的片段，最终得到常量或变量，它们的导数只可能是0或者1。

为了能在一个函数中体现上述规则，我们稍微放开自己基于意愿的思路，就像在前面设计有理数实现时的做法。如果现在已经有了表示代数表达式的方法，我们一定能确定遇到的表达式是否为和式、乘式、常量，或者变量，也能提取出表达式的各个部分。举例说，对于和式，我们应该希望能取得其被加项（第1个项）和加项（第2个项）。我们还需要能从几个部分出发构造整个的表达式。让我们假定现在已经有了一些函数，它们实现了下述的构造函数、选择函数和谓词：

利用这些函数，以及判断表达式是否为数的基本函数is_number，我们就可以把各种求导规则表达为下面的函数了：

函数deriv实现了一个完整的求导算法。由于它是基于抽象数据表述的，因此，无论怎样选择代数表达式的具体表示，只要我们设计了一组完美的选择函数和构造函数，这个求导函数就能工作了。当然，这些函数也是下一步必须处理的问题。

代数表达式的表示

我们可以设想出许多用表结构表示代数表达式的方法。例如，我们可以用符号的表直接反映代数的记法形式，把表达式 ax + b 表示为表list（"a", "*", "x", "+", "b"）。然而，如果我们用的JavaScript值的表示方法能直接反映被表示的数学表达式的结构，显然是一种更合适的选择。按这种想法， ax + b 应该表示为list（"+", list（"*", "a", "x"）,"b"）。与1.1.1节介绍的中缀记法不同，这种把运算符放在其运算对象前面的记法称为 前缀记法 。采用前缀记法，我们为求导问题而采用的数据表示具有如下的定义：

●变量就是字符串，可以用基本谓词is_string判断：

●两个变量相同就是表示它们的字符串相同：

●和式与乘式都构造为表：

●和式就是第一个元素为字符串"+"的表：

●被加项是表示和式的表里的第二个元素：

●加项是表示和式的表里的第三个元素：

●乘式就是第一个元素为字符串"*"的表：

●被乘项是表示乘式的表里的第二个元素：

●乘项是表示乘式的表里的第三个元素：

这样，我们只需要把这些函数与deriv装配在一起，就得到了一个能工作的符号求导程序了。现在让我们来看几个实例，观察这一程序的行为：

这个程序产生的结果都是正确的，但是它们没做化简。确实会产生：

我们可能希望这个程序知道 x ·0=0，1· y = y 以及0+ y = y 。如果这样，第二个例子的结果就应该是简单的y。正如上面的第三个例子所显示的，当表达式变得更复杂时，这一情况可能变成很严重的问题。

现在面临的困难，非常像我们在做有理数实现时遇到的：希望把结果化简到最简形式。为了完成有理数的化简，我们只需要修改实现中的构造函数和选择函数。这里也可以采用同样的策略。我们可以完全不用修改deriv，而是只修改make_sum，使得当两个求和对象都是数时，make_sum求出并返回它们的和。还有，如果有一个求和对象是0，make_sum就直接返回另一个对象。

在这个实现里用到了函数number_equal，它检查某个表达式是否等于一个给定的数。

类似地，我们也需要修改make_product，以便引入下面的规则：0与任何东西的乘积都是0，1与任何东西的乘积总是那个东西：

下面是这一新函数版本处理前面三个例子的结果：

情况已经大大改观。然而，第三个例子还是说明，要想做出一个程序，使它能把表达式做成我们都能同意的“最简”形式，还有很长的路要走。代数化简是一个非常复杂的问题，除了其他因素外，一个表达式对一种用途是最简的，也可能对另一用途不是最简的。

练习2.56 请说明如何扩充上面的基本求导规则，以便处理更多种类的表达式。例如，实现下面的求导规则：

请给程序deriv增加一个新子句，并以适当的方式定义函数is_exp、base、exponent和make_exp，实现这个求导规则（你可以考虑用符号"**"表示乘幂）。请把如下规则也构造到程序里：任何东西的0次幂都是1，而它们的1次幂都是其自身。

练习2.57 请扩充我们的求导程序，使之能处理任意多个项（两项或更多项）的求和与乘积。这样，上面的最后一个例子就可以表示为：

请试着通过只修改求和与乘积的表示，完全不修改函数deriv的方式完成这一扩充。例如，让一个和式的addend是它的第一项，而其augend是和式中的其余项。

练习2.58 假设我们希望修改求导程序，使它能用于常规的数学公式，其中的"+"和"*"采用中缀记法而不是前缀。由于求导程序的定义基于抽象的数据，我们可以修改它，使之能用于不同的表达式表示，只需要换一套工作在求导函数需要处理的代数表达式的新表示形式上的谓词、选择函数和构造函数。

a.请说明怎样做出这些函数，实现在中缀表示形式上的代数表达式求导。例如下面的例子：

为了简化工作，你可以假定"+"和"*"总具有两个运算对象，而且表达式里已经加了所有括号。

b.如果我们希望处理某种接近标准的中缀表示法，其中可以略去不必要的括号，并假定乘法具有比加法更高的优先级，例如

问题就会变困难许多。你能为这种表示方式设计好适当的谓词、选择函数和构造函数，使我们的求导程序仍能工作吗？

2.3.3 实例：集合的表示

在前面的实例中，我们已经为两类复合数据对象（有理数和代数表达式）设计了表示方法。对这两个实例，我们都考虑了在构造时或选择成员时简化（约简）表示的问题，但对它们的表示方法则都没做更多的考虑，因为用表的形式表示它们都是直截了当的。现在我们转到集合的表示问题，在这里表示方法的选择就不那么显然了。实际上，这里存在多种不同的选择，而且它们相互之间在若干方面存在着明显的差异。

非形式地说，一个集合也就是一些不同对象的汇集。要给出更精确的定义，我们可以采用数据抽象的方法，也就是说，用一组可以应用于“集合”的操作给出定义。这些操作是union_set、intersection_set、is_element_of_set和adjoin_set。函数is_element_of_set是谓词，用于确定给定的元素是否某一给定集合的成员。adjoin_set以一个对象和一个集合为参数，返回一个集合，其中包含了原集合的所有元素，以及刚刚加入的这个新元素。union_set计算两个集合的并集，这也是一个集合，其中包含了所有属于两个参数集合之一的元素。intersection_set计算两个集合的交集，该集合包含同时出现在两个参数集合里的那些元素。从数据抽象的观点看，我们在设计集合的表示方面有充分的自由，只要在这种表示上实现的上述操作能以某种方式符合上面给出的解释 ^[9] 。

集合作为不排序的表

表示集合的一种方法就是用其元素的表，其中任何元素的出现都不超过一次。这样，空集就用空表表示。对于这种表示，is_element_of_set类似2.3.1节的函数member，但它应该用equal检查而不是用===，以保证集合的元素不仅可以是数或字符串：

利用它就能写出adjoin_set。如果要求加入的对象已经在集合里，那么就直接返回那个集合。否则就用pair把这个对象加入这个表示集合的表里：

实现intersection_set可以采用递归策略：如果我们已经知道如何做出set2与set1的tail的交集，那么就只需要确定是否应该把set1的head包含到结果中，而这要看head（set1）是否也在set2里。下面的函数实现了这种想法：

在为数据设计表示形式时，必须关注的一个问题是操作的效率。现在考虑上面定义的集合操作所需的工作步数。因为它们都用到is_element_of_set，所以，这个操作的速度对集合的整体实现效率有重要影响。在上面的实现里，为了检查某个对象是否为一个集合的成员，is_element_of_set可能必须扫描整个集合（最坏情况是该元素恰好不在集合里）。因此，如果集合有 n 个元素，is_element_of_set就可能需要 n 步才能完成。这样，该操作所需步数将以 Θ （ n ）的速度增长。adjoin_set用了这个操作，因此它所需的步数也以 Θ （ n ）的速度增长。至于intersection_set，它需要对set1的每个元素做一次is_element_of_set检查，因此所需步数将按两个参数集合的大小之乘积增长，或者说，在两个集合大小都为 n 时就是 Θ （ n ² ）。union_set的情况也是如此。

练习2.59 请为用不排序的表表示的集合实现union_set操作。

练习2.60 我们前面说明了如何把集合表示为没有重复元素的表。现在假定允许重复，例如，集合{1, 2, 3}可能被表示为表list（2, 3, 2, 1, 3, 2, 2）。请为在这种表示上的操作设计函数is_element_of_set、adjoin_set，union_set和intersection_set。与前面不允许重复的表示里的相应操作相比，现在这些操作的效率如何？在什么样的应用中你更倾向于使用这种表示，而不用前面那种无重复的表示？

集合作为排序的表

加速集合操作的一种方法是改变其表示方法，让表中的集合元素按上升序排列。为此我们需要有某种方式来比较两个元素，以确定哪个元素更大。例如，我们可以按字典序比较字符串；或者统一采用某种方式为每个对象关联一个唯一的数，在比较元素时就比较它们关联的数。为简化这里的讨论，下面我们只考虑集合元素是数值的情况，这样，我们就可以用>和<比较元素了。我们考虑把数的集合表示为元素按上升顺序排列的表。在前面讨论的第一种表示方法下，集合{1, 3, 6, 10}的元素在表里可以任意排列，而按现在的新表示方法，该集合的表示就只能是list（1, 3, 6, 10）。

从操作is_element_of_set就能看到采用有序表示的一个优势：为了检查一个项的存在与否，现在通常不必扫描完整个表。如果检查中遇到的某个元素大于当时要找的东西，那么就可以断定这个东西不在表里：

这样能节省多少步数呢？在最坏情况下，我们要找的项是集合中的最大元素，此时所需步数与采用不排序的表示时一样。但另一方面，如果需要查找许多不同大小的项，我们总可以期望有些时候这一检索可以在接近表开始的某点停止，也有些时候需要检查表中一大部分。平均而言，我们可以期望需要检查表的一半元素，这样，平均所需的步数就是大约 n /2。这仍然是 Θ （ n ）的增长速度，但与前一实现方法相比，现在我们可能节约了一些步数。

操作intersection_set的加速情况更令人印象深刻。在不排序的表示方法里，这一操作需要 Θ （ n ² ）的步数，因为对set1的每个元素，我们都需要做一次对set2的扫描。采用排序表示，我们有一种更聪明的方法。开始时我们比较两个集合的起始元素，例如x1和x2。如果x1等于x2，那么就找到了交集的一个元素，而交集的其他元素就是这两个集合的tail部分的交集。如果这时x1小于x2，由于x2是集合set2的最小元素，我们立即可以断定x1根本不会出现在集合set2里，因此它一定不在交集里。这样，两集合的交集就等于集合set2与set1的tail的交集。与此类似，如果x2小于x1，那么两集合的交集就等于集合set1与set2的tail的交集。下面是这样工作的函数：

要估算这一计算过程所需的步数，我们可以注意到，这里每一步都能把求交集问题归结到计算更小的集合的交集——去掉了set1和set2之一或两者的第一个元素。这样，所需步数至多等于set1与set2的大小之和，而不像在不排序表示中的它们之乘积。这就是 Θ （ n ）的增长速度，而不是 Θ （ n ² ）——即使是对中等大小的集合，这一加速也非常明显。

练习2.61 请给出排序表示时adjoin_set的实现。通过类似is_element_of_set的方法，说明如何利用排序的优势得到一个函数，其所需平均步数可能是未排序表示时的一半。

练习2.62 请给出在集合的排序表示上union_set的一个 Θ （ n ）实现。

集合作为二叉树

如果把集合里的元素安排成一棵树的形式，还可以得到比排序表表示更好的结果。树中每个结点保存集合的一个元素，称为该结点的“数据项”。它还链接到另外两个结点（可能为空），其中“左边”的链接所指向部分的元素均小于本结点的元素，而“右边”链接到的元素都大于本结点里的元素。图2.16显示了表示集合{1, 3, 5, 7, 9, 11}的几棵树，同一个集合可以按多种不同方式表示为树。我们对合法表示的要求就是，位于左子树里的所有元素都小于本结点里的数据项，而位于右子树里的所有元素都大于它。

树表示的优点如下：假定我们希望检查某个数 x 是否包含在一个集合里，开始时我们用 x 与树顶结点的数据项比较。如果 x 小于它，我们就知道现在只需要去搜索左子树；如果 x 较大，那么就只需要搜索右子树。现在，如果这棵树是“平衡的”，也就是说，每棵子树大约是整个树的一半大，那么，经过一步我们就把搜索规模为 n 的树的问题归约为搜索规模为 n /2的树的问题。由于树的规模在每一步能减小一半，搜索规模为 n 的树，我们可以期望所需要的步数以 Θ （log n ）速度增长 。对于很大的集合，与前面的表示方法相比，现在的操作速度可以加快很多。

我们可以用表来表示树，结点用表表示，每个结点是一个包含三个元素的表：本结点中的数据项，其左子树和右子树。如果左子树或右子树是空表，就表示那里的子树为空。我们可以用下面几个函数描述这种表示 ：

现在，我们就可以采用前面说明的策略实现is_element_of_set了：

向集合里加入一项的实现方式与此类似，同样也需要 Θ （log n ）步。为了加入元素x，我们用x与结点数据项比较，以确定x应该加入右子树还是左子树。在把x加入适当分支后，我们把这个新构造的分支和原来的数据项与另一分支放到一起。如果x等于这个数据项，我们就直接返回这个结点。如果要求把x加入一棵空树，我们就构造一棵树，以x作为数据项，让它的左右分支为空。下面是函数adjoin_set的声明：

前面我们曾经断言，树的搜索可以通过对数步数完成，但这实际上依赖树“平衡”的假设，也就是说，每棵树的左子树和右子树里的结点数大致相同，因此每棵子树包含的结点数大约是整个树的一半。但是，我们怎么才能确保构造的树是平衡的呢？即使从一棵平衡的树开始工作，采用adjoin_set加入元素也可能产生不平衡的结果，因为新加元素的位置依赖于它与当时已经在树里的那些数据项比较的情况。我们可以期望，如果把元素“随机地”加入树中，平均而言会使树趋于平衡。但是这一点并没有保证。例如，如果我们从一个空集出发，顺序地把数值1至7加入树中，就会得到如图2.17所示的高度不平衡的树。在这个树里所有左子树都为空，因此，与简单的排序表相比，它没有一点优势。解决这个问题的一种方式是定义一个操作，它能把任意的树变换为一棵具有同样元素的平衡树。在每执行过几次adjoin_set操作之后，我们就通过执行这个操作来维持树的平衡。也存在能解决这个问题的另一些方法，大部分方法都牵涉设计一种新的数据结构，使得在其中的搜索和插入都能在 Θ （log n ）步数完成 。

练习2.63 下面两个函数都能把树变换为表：

a.这两个函数对所有的树都生成同样的结果吗？如果不是，它们生成的结果有什么不同？它们对图2.16中的那些树生成怎样的表？

b.把 n 个结点的平衡树变换为表时，这两个函数所需的步数具有同样量级的增长速度吗？如果不一样，哪个增长得慢些？

练习2.64 下面的函数list_to_tree把一个有序表变换为一棵平衡二叉树。其中辅助函数partial_tree以整数 n 和一个至少包含 n 个元素的表为参数，构造出一棵包含该表前 n 个元素的平衡树。由partial_tree返回的结果是一个序对（用pair构造），其head是构造出的树，其tail是没有包含在树里那些元素的表。

a.请简要并尽可能清楚地解释为什么partial_tree能完成所需的工作。请画出把list_to_tree应用于表list（1, 3, 5, 7, 9, 11）生成的树。

b.list_to_tree转换 n 个元素的表，所需的步数以什么量级增长？

练习2.65 利用练习2.63和练习2.64的结果，给出对采用（平衡）二叉树方式实现的集合的union_set和intersection_set操作的 Θ （ n ）实现 。

集合与信息检索

我们已经考察了用表表示集合的多种选择，并看到了数据对象表示的选择可能如何深刻地影响到使用数据的程序的性能。关注集合的另一个原因是，在涉及信息检索的各种应用中，这里讨论的技术将会一次次地出现。

考虑一个包含大量独立记录的数据库，例如一个企业的人事文件，或者一个会计系统里的交易记录。典型的数据管理系统都要消耗大量时间访问和修改相关记录中的数据，为此需要访问记录的高效方法。完成这项工作的一种方法，就是把每个记录中的一部分当作标识key（ 键值 ）。键值可以是任何能唯一标识记录的东西。对于人事文件，它可能是雇员的ID号。对于会计系统，它可能是交易的编号。无论键值是什么，我们把记录定义为一种数据结构后，就需要定义一个key选择函数，用于从记录里提取相关的键值。

现在我们就可以把数据库表示为记录的集合。为了根据给定键值确定相关记录的位置，我们需要一个函数lookup，它以一个键值和一个数据库为参数，返回具有这个键值的记录，或在找不到需要的记录时报告失败。函数lookup的实现方式与is_element_of_set几乎一模一样，如果记录的集合被表示为不排序的表，我们就可以用：

不言而喻，对于很大的集合，存在比不排序的表更好的表示方法。信息检索系统常常需要“随机访问”保存的记录，经常采用某种基于树的方法实现，例如用前面讨论的二叉树。在设计这种系统时，数据抽象的方法学可以有很大的帮助。设计师可以创建某种初始实现，例如简单而直接地采用不排序的表。对最终系统而言，这种设计显然很不合适，但采用这种方式提供一个“一挥而就”的数据库，对于测试系统的其他部分则可能很有帮助。我们可以在后来逐步把数据的表示修改得更加精细。如果对数据库的访问都基于抽象的选择函数和构造函数，在表示方法改变时，我们就不需要对系统的其余部分做重大修改。

练习2.66 假设用二叉树结构实现记录的集合，其中的记录按作为键值的数值排序。请实现相应的lookup函数。

2.3.4 实例：Huffman编码树

本节要给出一个例子，其中实际地使用了表结构和数据抽象来操作集合和树。这里讨论的应用是想确定一种用0和1（二进制位）的序列表示数据的方法。举例说，在计算机中经常使用的表示文本的ASCII标准编码里，每个字符用一个包含7个二进制位的序列表示，7个二进制位能区分2 ⁷ 种不同情况，或者说128个可能不同的字符。一般而言，如果我们需要区分 n 个不同字符，就需要为每个字符使用log ₂ n 个二进制位。假设我们的所有消息都用A, B, C, D, E, F, G和H这8个字符组成，我们就可以选一种编码，其中每个字符用3个二进制位，例如：

采用这种编码时，消息：

BACADAEAFABBAAAGAH

将编码为下面的包含54个二进制位的串：

001000010000011000100000101000001001000000000110000111

如ASCII码和上面A到H的编码，采用的编码方式都称为 定长 编码，因为它们用同样数目的二进制位表示消息里的每个字符。另一种编码是变长的，其中不同字符可以用不同数目的二进制位表示，这种编码有时也可能有优势。举例说，对于字母表中的字母，摩尔斯电报码就没有采用同样数目的点和划，特别是E只用一个点表示，因为它是出现最频繁的字母。一般而言，如果在我们的消息里某些符号出现得很频繁，而另一些却很少见，那么，如果为频繁出现的符号指定较短的码字，就可能更高效地完成数据的编码（对同样消息使用更少的二进制位）。考虑如下的对字母A到H的另一种编码：

采用这种编码，上面的同样信息将编码为如下的串：

100010100101101100011010100100000111001111

这个串只包含42个二进制位。也就是说，与前面的定长编码相比，现在这种编码方式节约了超过20%的空间。

采用变长编码有一个困难，就是如何在读0/1序列的过程中确定已经到了一个字符结束。为解决这个问题，摩尔斯电报码的方法是在每个字母的点划序列之后用一个特殊 分隔符 （它用一个间歇）。另一解决方法是按某种方式设计编码，使其中任何字符的完整编码都不是另一个字符的编码的前面部分（或称 前缀 ）。具有这种性质的编码称为 前缀码 。例如，在上面例子里，A编码为0而B编码为100，没有其他字符的编码由0或100开始。

一般而言，如果所用的变长前缀码能很好利用被编码消息中符号出现的相对频度，我们有可能明显地节约空间。能做好这件事的一种特别方法称为Huffman编码，这个名称取自其发明人David Huffman。一个Huffman编码可以用一棵二叉树表示，其中的树叶是被编码的符号。树中每个非叶结点对应一个集合，其中包含了这一结点之下的所有树叶的符号。除此之外，位于树叶的每个符号还赋予了一个权重（也就是它的相对频度），每个非叶结点的权重就是位于它之下的所有叶结点的权重之和。这种权重在编码和解码中并不使用。但我们将在下面看到，这些权重可以帮助我们构造这棵树。

图2.18显示的是上面给出的A到H的编码对应的Huffman编码树，树叶上的权重表明，在这棵树的设计所针对的那些消息里，字母A具有相对权重8，B具有相对权重3，其余字母的相对权重都是1。

给了一棵Huffman树，要找出一个符号的编码，我们只需要从树根开始向下运动，直至到达了保存着这个符号的树叶为止，在每次向左下行时给代码加一个0，向右下行时加一个1。在确定向哪一分支运动时，需要检查该分支是否包含对应这个符号的叶结点，或者其集合中包含这个符号。举例说，从图2.18中的树根开始，到达D的叶结点的方式是走一个右分支，而后一个左分支，而后是右分支，而后又是右分支，因此其代码是1011。

在使用一棵Huffman树解码一个序列时，我们也从树根开始，通过位序列中的0或1确定是移向左分支还是右分支。每当我们到达一个叶结点时，就生成出消息中的一个符号。此时重新从树根开始解码下一个符号。例如，如果给我们的是上面的树和序列10001010。我们从树根开始，移向右分支（因为串中第一个位是1），而后向左分支（因为第二个位是0），而后再向左分支（因为第三个位也是0）。这时已经到达B的叶，所以被解码消息中的第一个符号是B。现在再次从根开始，因为序列中下一个位是0，这就导致一次向左分支的移动，使我们到达包含A的叶结点。然后我们再次从根开始处理剩下的串1010，经过右左右左移动后到达了C。这样，整个消息就是BAC。

生成Huffman树

给定了一个符号组成的“字母表”和各个符号的相对频度，我们怎么能构造出“最好的”编码呢？（换句话说，哪样的树能使消息编码的位数达到最少？）Huffman给出了一个完成这一工作的算法，并且证明，如果消息中各个符号出现的相对频度与构造树时所用的频度相符，这样得到的编码就是最好的变长编码。我们不打算在这里证明Huffman编码的最优性质，但要说明如何构造Huffman树 。

生成Huffman树的算法实际上十分简单，其想法就是设法安排这棵树，使频度最低的符号出现在离树根最远的地方。构造过程从叶结点的集合开始，各个结点分别包含各个符号和它们的频度。这些就是构造过程的初始数据。现在我们找出两个具有最低权重的叶结点，归并它们，并生成一个以这两个结点为左右分支的结点。新结点的权重就是所选的那两个结点的权重之和。从原集合删除那两个叶结点，用这个新结点代替它们，然后继续这个构造过程。过程中的每一步都归并两个具有最小权重的结点，把它们从集合删除，并用一个以这两个结点为左右分支的新结点取代之。这个过程进行到集合中只剩一个结点时终止，这个结点就是树根。下面就是图2.18中的Huffman树的生成过程：

这个算法描述的树通常不唯一。这是因为，每一步选取权重最小的两个结点，满足条件的选择可能不唯一。还有，在归并两个结点时，采用的顺序也是任意的（也就是说，哪个结点作为左分支，哪个作为右分支都可以）。

Huffman树的表示

在下面的练习中，我们要做出一个系统，它能根据上面给出的梗概生成Huffman树，还能用Huffman树完成消息的编码和解码。我们还是从讨论这种树的表示开始。

树的树叶也用表来表示，其中元素是字符串"leaf"、叶中的符号和权重：

一棵一般的树也是一个表，其中包含字符串"code_tree"、左分支、右分支、一集符号和一个权重。符号集合就是符号的表，这里没用更复杂的集合表示。在归并两个结点做出一棵树时，树的权重是这两个结点的权重之和，树的符号集合是两个结点的符号集合的并集。因为这里的符号集用表来表示，利用2.2.1节的append函数就能得到它们的并集：

对于按这种方式构造的树，我们需要下面的选择函数：

在对树叶或者一般的树调用函数symbols和weight时，需要做的事情稍有不同。这些不过是 通用型函数 （可以处理多类不同数据的函数）的简单实例。有关这方面的情况，在2.4节和2.5节将有很多讨论。

解码函数

下面的函数实现解码算法，它以一个0/1的表和一棵Huffman树为参数：

辅助函数decode_1有两个参数，其中一个是包含着剩余的二进制位的表，另一个是树中的当前位置。我们在工作中不断在树里“向下”移动，根据表中的下一个位是0或1选择树的左分支或右分支（这一工作由函数choose_branch完成）。当我们到达叶结点时，就把位于这里的符号作为消息中的下一个符号，将其pair到对消息里的随后部分的解码结果之前。然后，这一解码又从树根重新开始。请注意，choose_branch的最后一个子句检查错误，并在遇到输入中非0/1的东西时报错。

带权重元素的集合

在我们的树表示里，每个非叶结点包含了一个符号集合，表示为一个简单的表。然而，上面的树生成算法要求我们能对树叶和树的集合工作，不断地归并一对对权重最小的项。因为这里需要反复确定集合里的最小项，采用某种排序的集合表示比较方便。

我们准备把树叶和树的集合表示为元素的表，按权重的上升顺序排列表中元素。下面用于构造集合的函数adjoin_set与练习2.61中描述的函数类似，但这里比较的是元素的权重，而且，加入集合的新元素原来绝不会出现在这个集合里。

下面的函数以一个符号-频度对偶的表为参数，例如

它构造出树叶的初始排序集合，以便Huffman算法能由其开始做归并：

练习2.67 声明了下面的编码树和样例消息：

请用函数decode完成该消息的编码，并给出编码的结果。

练习2.68 函数encode以一个消息和一棵树为参数，生成被编码消息对应的二进制位的表：

其中的函数encode_symbol需要你写，它根据给定的树产生给定符号的二进制位表。如果遇到未出现在树中的符号，你设计的encode_symbol应该报告错误。用你在练习2.67中得到的结果检查你的函数，工作中使用同样的树，看看得到的结果是不是原来的消息。

练习2.69 下面的函数以一个符号-频度对偶的表为参数（其中任何符号都不会出现在多于一个对偶中），并根据Huffman算法生成出Huffman编码树。

make_leaf_set是前面定义的函数，它把对偶表变换为叶的有序集合，successive_merge是需要你写的函数，它用make_code_tree反复归并集合中权重最小的两个元素，直至集合里只剩下一个元素为止。这个元素就是我们需要的Huffman树。（这一函数稍微有点技巧性，但并不复杂。如果你发现自己设计了一个很复杂的函数，那么几乎可以肯定是在什么地方搞错了。你应该尽可能地利用有序的集合表示这一事实。）

练习2.70 下面带有相对频度的8个符号的字母表，是为了有效编码20世纪50年代的摇滚歌曲中的词语而设计的。（注意，“字母表”中的“符号”不必是单个字母。）

请用（练习2.69的）generate_huffman_tree函数生成对应的Huffman树，用（练习2.68的）encode编码下面这个消息：

这一编码需要多少个二进制位？如果对这8个符号的字母表采用定长编码，完成这个歌曲的编码最少需要多少个二进制位？

练习2.71 假定我们有一棵 n 个符号的字母表的Huffman树，其中各个符号的相对频度分别是1, 2, 4,…, 2 ^{n -1} 。请对 n =5和 n =10勾勒出树的形式。对这样的树（对一般的 n ），编码出现最频繁的符号用了多少个二进制位？最不频繁的符号呢？

练习2.72 考虑你在练习2.68中设计的编码函数。编码一个符号，计算步数的增长速度如何？这里必须计入遇到每个结点时检查符号表所需的步数。一般性地回答这个问题非常困难。考虑一类特殊情况，其中 n 个符号的相对频度如练习2.71所述。请给出编码最频繁符号所需的步数和编码最不频繁符号所需的步数的增长速度（作为 n 的函数）。 11+i/swFZRMV/tzmVVILetRxJdUFFVVn5/RbHSy4dRkErvWS+P7cE9KdZwlSGGu5