2.2 哈夫曼编码原理和实现

哈夫曼（Huffman）编码（也称为霍夫曼编码）是一种无损数据压缩算法，该算法的基本思想是：为输入字符分配可变长度的编码，编码长度的分配基于对应字符的频率。最频繁的字符得到最短的编码，最不频繁的字符得到最长的编码。

2.2.1 哈夫曼编码的原理

分配给输入字符的可变长度编码是前缀码，这意味着码（位序列）的分配方式使得分配给一个字符的编码不是分配给任何其他字符编码的前缀。这就是哈夫曼编码能供保证译码生成的比特流没有“歧义”。

下面举一个“反例”来说明前缀码。假设有4个字符a、b、c和d，它们对应的可变长度的编码为“00”、“01”、“0”和“1”。这种编码会导致歧义，因为分配给字符c的编码是分配给字符a和字符b的编码的前缀。如果压缩比特流为“0001”，则压缩后的输出可能是cccd/ccb/acd/ab。

哈夫曼编码主要包含两部分：构建哈夫曼树；遍历哈夫曼树并将编码分配给字符。

1.构建哈夫曼树

本部分将介绍如何构建哈夫曼树。简单来说，输入是一组唯一字符，以及它们出现的次数，输出是哈夫曼树。具体实现步骤如下所示。

（1）为每个唯一字符创建一个叶子节点，并构建所有叶子节点的最小堆。其中，最小堆用作优先级队列。出现次数字段的值用于比较最小堆中的两个节点。最初，出现次数最少的字符在根节点处。

（2）从最小堆中提取出现次数最小的两个节点。

（3）创建一个新的内部节点，其出现次数等于两个节点之和。将第一个提取的节点作为其左孩子，将另一个提取的节点作为其右孩子，并将该节点添加到最小堆中。

（4）重复步骤（2）和（3），直到堆中只包含一个节点，剩下的节点是根节点，树是完整的。

下面通过一个例子来说明哈夫曼树的构建过程。输入字符及字符出现的次数如表2.2所示。

（1）构建一个包含6个节点的最小堆，其中每个节点代表具有单个节点的树的根。

（2）从表2.2给出的最小堆中提取两个出现次数最少的节点。添加一个出现次数为5+9=14的新内部节点，如图2.11 所示。

现在最小堆包含5个节点。其中，4个节点是树的根，每个节点有一个数据元素；一个堆节点是树的根，有3个元素，如表2.3所示。

（3）从表2.3给出的堆中提取两个出现次数最少的节点。添加出现次数为12+13=25的新的内部节点，如图2.12 所示。

现在最小堆包含4个节点。其中，2个节点是树的根，每个节点都具有一个元素；两个堆节点是树的根，有多个节点，如表2.4所示。

（4）从表2.4给出的堆中提取两个出现次数最少的节点。添加出现次数为14+16=30的新内部节点，如图2.13所示。

现在最小堆包含3个节点，如表2.5所示。

（5）从表2.5给出的堆中提取两个出现次数最少的节点。添加出现次数为25+30=55的新内部节点，如图2.14所示。

现在最小堆中包含两个节点，如表2.6所示。

（6）从表2.6中给出的最小堆中提取两个出现次数最少的节点，添加出现次数为45+55=100的新内部节点，如图2.15所示。

现在最小堆中只包含一个节点，如表2.7所示。

由于堆中只包含一个节点，所以构建哈夫曼树的过程结束。

2.哈夫曼编码

遍历从根开始形成的哈夫曼树。维护一个辅助数组。在向左孩子移动时，将0写入数组。在移动到右孩子的同时，将1写入数组。遇到叶子节点时打印数组，如图2.16所示。

因此，对于每个输入字符的哈夫曼编码如表2.8所示。

2.2.2 C语言程序设计

实现哈夫曼编码算法的C语言代码如代码清单2-4所示。注意，注释中提到的坐标实际上就是节点的编号。

注 ：读者可以定位到本书提供资源的\loongson1B_training_example\example_2_4目录中，使用LoongIDE软件工具打开example_2_4.lxp工程文件。

2.2.3 C语言编译及调试

本节将介绍如何对设计进行编译，并将设计下载到龙芯1B开发板进行验证。具体实现步骤如下所示。

（1）编译程序代码，给龙芯1B硬件开发平台上电。

（2）启动并配置PuTTY（64-bit）软件工具。

（3）在LoongIDE主界面主菜单下，选择Debug->Run，开始运行程序，在PuTTY命令行界面中将打印出哈夫曼编码的信息，如图2.17所示。

2.2.4 汇编语言程序设计

在bsp_start.S文件中，添加如代码清单2-5所示的实现哈夫曼编码算法的汇编语言代码。

注 ：读者可以定位到本书提供资源的\loongson1B_training_example\example_2_5目录中，使用LoongIDE软件工具打开example_2_5.lxp工程文件。

2.2.5 汇编语言编译和调试

本节将介绍如何对前面所设计的汇编语言代码进行编译，并在龙芯1B硬件开发平台上进行调试和验证。具体实现步骤如下所示。

（1）编译程序代码，给龙芯1B硬件开发平台上电。

（2）如图2.18所示，在代码清单2-5中设置断点。

（3）在LoongIDE主界面主菜单下，选择Debug->Run，进入调试器界面。

（4）单击“CPU Registers”标签，在“CPU Registers”标签页中找到寄存器名字为“s2”的一行，并用鼠标左键双击该行。

（5）弹出“View Memory”对话框，如图2.19所示。从图2.19可知，哈夫曼编码的结果保存在存储空间地址为0x80212910开始的位置。在该对话框中，设置下面的参数。

① Count：72。（通过“Count”标题右侧的旋转按钮设置）。

② Data Type：short（通过选择“short”前面的复选框设置）。

（6）单击“Fetch”按钮，即可在图2.19中看到生成的哈夫曼编码。

注 ：代码清单2-5中的注释中提到生成的哈夫曼编码使用2进行分割，从低地址到高地址依次读取哈夫曼编码，直到遇到数字2为止，保存哈夫曼编码的起始地址总是从最低地址为0的位置开始。在图2.19中，使用竖方框将生成的哈夫曼编码框起来，以方便读者知道如何查看生成的哈夫曼编码。