HUFFMAN编码技术应用研究 .pdfVIP

HUFFMAN鼬技术邮研究

摘要：现代社会每天产生海量级的信息，而这些信息的存储和传输需要大量的存储空间，信息本有很大的的冗

余度，因此信息必须采用压缩技术处理。Huffman编码是一种流行而又高效的无损编码，利用Huffman编码就可能比普

通的编码方法使用的码数少，提高了编码的有效性。

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

Huffman编码根据消息出现概率的分布特性进行统计，寻找概率与码字长度间的最优匹配，利用数据的统计冗余

进行压缩，基于符号出现概率的不同赋予长短不一的码字，出现概率越大的符号，相应的码越短;出现概率越小的符号，

其码越长。算法用一串二进制位(称作位码)来代替每个字符，再将这些位码写进压缩后的文件。利用位码压缩的关键

之处是选择最优二叉树，在Huffman树中没有一个位码是另一个位码的前缀，每一个字符都在树的叶子结点中出现。

Huffman编码一般用来压缩多媒体信息，如文本、程序文件和特色的图像等，实现对数据的无损压缩。解码时，

在消息和码字之间找到明确的一一对应关系，恢复时能准确无误地再现出来，完全恢复原始数据而不引起任何失真。

1编码步骤

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

(1)将信源符号按其出现的概率，由大到小顺序排列；

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

下一个信源符号且概率达到1.0为止；

(3)对每对组合的上边一个指定为1,下边一个指定为0；

(4)画出由每个信源符号到概率1处的路径，记下沿路径的1和0；

(5)对于每个信源符号都写出1、0序列，就得到非等长的Huffman码。

2Huffman编码设计

例如要压缩字符串“abaadffbghadffda”，首先统计各字符出现的概率：

a：5/16,b：2/16,d：3/16,f：4/16,g：1/16,h：1/16

上述原字符的二it制编码为0110001001100001011001100110011101100001011001100110011001100100共128bito

构造Huffman树，树从最下层的结点开始构造，选取概率最小和次小的两个符号作为左右子树构造一棵新的二叉

树，新二叉树根结点的权值为其左右子树根结点权值之和。重复这一过程，最后得到一个横放的码树即Huffman树。

Huffman编码就是将从根结点出发到叶结点的路径上各左、右分支的编码顺序排列就得到了该叶子结点所对应的

字符的二进制前缀编码，每个字符转换为一个唯一的二进制位串，则该字符串中每个字符的Huffman编码为：a：11,

b：011,d：00,f：10,g：0100,h：0101

原字符串的Huffman编码为：11011111100101001101000101110010100011,共38bit。

3Huffman编码分析

(1)压缩比

压缩比是压缩前后所需的信息存储量之比，上面的例子中可以计算出压缩比为：38/128=30%,所以说Huffman

编码在数据压缩中的压缩效果是非常好的，只要Huffman编码表基于大量概率统计，其编码效果是足够好的。

(2)时间空间效率高

Huffman编码是最佳变长码，得到的是最短的编码长度，有效节省空间。

(3)Huffman编码是无失真的数据压缩编码，解码之后可以无失真的恢复原信息。

(4)Huffman编码的实现方法有很多，比如说ATLAB实现，C语言实现等。

4Huffman编码不足

(1)Huffman编码要精确统计出每个符号出现的概率，通常要进行两次扫描：第一遍扫描产生统计结果，第二次

扫描完成编码，所以编码速度相对慢。

(2)Huffman编码只能用整数来表示单个符号而不能用小数。

(3)只有当信息源各符号