徐爱芸

摘要：现代社会每天产生海量级的信息，而这些信息的存储和传输需要大量的存储空间，信息本身有很大的的冗余度，因此信息必须采用压缩技术处理。Huffman编码是一种流行而又高效的无损编码，利用Huffman编码就可能比普通的编码方法使用的码数少，提高了编码的有效性。

关键词：Huffman编码;最优二叉树;无损压缩

Huffman编码根据消息出现概率的分布特性进行统计，寻找概率与码字长度间的最优匹配，利用数据的统计冗余进行压缩，基于符号出现概率的不同赋予长短不一的码字，出现概率越大的符号，相应的码越短;出现概率越小的符号，其码越长。算法用一串二进制位（称作位码）来代替每个字符，再将这些位码写进压缩后的文件。利用位码压缩的关键之处是选择最优二叉树，在Huffman树中没有一个位码是另一个位码的前缀，每一个字符都在树的叶子结点中出现。

Huffman编码一般用来压缩多媒体信息，如文本、程序文件和特色的图像等，实现对数据的无损压缩。解码时，在消息和码字之间找到明确的一一对应关系，恢复时能准确无误地再现出来，完全恢复原始数据而不引起任何失真。

1编码步骤

Huffman编码是一种一致性编码法，以Huffman树即带权路径长度最小的二叉树构建变长最佳编码，其步骤如下：

（1）将信源符号按其出现的概率，由大到小顺序排列;

（2）将两个最小的概率的信源符号进行组合相加，并重复这一步骤，始终将较大的概率分支放在上部，直到……