赫夫曼编译码系统的设计与实现

摘要：在信息快速传输和存储过程中，数据压缩有着重要的作用。从赫夫曼树定义及算法出发，介绍了一个赫夫曼编译码系统的设计与实现过程。这对于深入理解数据结构、程序设计有益。
关键词：赫夫曼树；赫夫曼编码；赫夫曼译码

    在数据结构课程的实践环节中，通常会让学生利用赫夫曼编码进行文本压缩与解压缩。由于教材上只是给出了赫夫曼树的定义及算法，学生会感到无从下手。本文将从赫夫曼树定义及算法出发，通过实例介绍赫夫曼编译码系统的具体设计与实现过程。

1 设计内容
1．1 赫夫曼编译码系统功能模块
    (1)赫夫曼建树模块：根据输入的字符和频率，完成赫夫曼树的构造，并根据赫夫曼树求赫夫曼编码。
    (2)编码模块：读取文本文件进行编码，编码结果存入到新文件。
    (3)译码模块：读取编码文件并解码，打开存储编码的文件，根据所读取的编码文件中的每个字符，利用赫夫曼树进行解码。
    (4)输出模块：将解码后的每个字母写入到一个新的文件中。
1．2 测试数据
    用表1给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码：“THISPROGRAM IS MY FAVORITE”。

    设计调试环境为Microsoft Visual C++6．0系统。

2 设计原理及算法分析
    本次要做的赫夫曼编译码系统的主要功能是：运用二叉树来设计二进制的前缀编码。给一个文件，先统计文件中每个字符出现的频数，即作为此字符的权值，然后将里面的字符编码成相应的赫夫曼编码。最后，根据赫夫曼译码原理把所给二进制数编译成对应的字符串。
2．1 构建赫夫曼树
    一般而言，给定n个实数w1，w2，…，w3其中，n≥2，求一个具有n个结点的二叉数，使其带权路径长度最小。可以证明赫夫曼树的带权路径长度是最小的。
    (1)根据与n个权值|w1，w2，…，w3|对应的n个结点构成具有n棵二叉树的森林F={HT1，HT2，…，HTn}，其中第i棵二叉树HTi(1≤i≤n)都只有一个权值为wi的根结点，其左、右子树均为空。
    (2)在森林F中选出两棵根结点权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点权值之和。
    (3)从F中删除构成新树的那两棵，同时把新树加入F中。
    (4)重复第1和第3步，直到F中只含有一棵为止，此树便为赫夫曼树。
2．2 赫夫曼编码
    赫夫曼编码是根据可变长最佳编码定理，应用赫夫曼算法而产生的一种编码，是消除编码冗余度最常用的方法。它的平均码字长度在具有相同输入概率集合的前提下，比其它任何一种可译码都小，因此，也常被称为紧凑码。
    (1)给定字符集的赫夫曼树生成后，求赫夫曼编码的具体实现过程是：依次以叶子HT[i](0≤i≤n-1)为出发点，向上回溯至根为止。上溯时走左孩子则生成代码0，走右孩子则生成代码1。
    (2)统计从根到叶子的路径上的标号依次相连，便为该叶子所对应字符的编码。
    (3)用生成的各个字符的编码替代原文件中的相应的字符，生成decode．txt文件。

    以下是部分编码的代码段


2．3 赫夫曼译码
    对压缩后的数据文件进行解码则必须借助于赫夫曼树，其过程是：从decode．txt文件中读取编码后的二进制码，从赫夫曼树的根结点出发，若当前为0，则向左孩子；若为1，则向右孩子。到达某一叶子结点时，便译出相应的字符。循环上步，直至解码完成。

3 设计结果
    (1)利用Microsoft Visual C++6．0系统进行调试，输入源程序，编译、连接后生成赫夫曼编译码系统可执行文件，如图1所示。
    (2)运行赫夫曼编译码系统可执行文件，输入表1字符和频度，编译码后得到运行结果，如图2所示。

4 结束语
    赫夫曼编码是已被证明的一种有效的熵编码方式，在诸如文本、图像、视频压缩及通信、密码等信息压缩编码标准中被广泛使用。目前广泛应用的许多其他高效数据压缩算法，例如算术编码、可预测编码也是在赫夫曼编码的基础上发展起来的，所以研究赫夫曼编码的思想，对于深入理解数据结构、程序设计学科中的相关课题有益。