哈弗曼编码介绍

哈弗曼编码简介：哈夫曼编码是一种可变字长的无损编码方式。对于出现概率大的元素编以短字长的码，对于出现概率小的元素编以长字长的码，来实现平均码长最短。

Huffman编码是一种应用广泛的可变长编码方式，是二叉树的一种特殊转化形式。利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。哈弗曼树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。哈弗曼编码的原理是：将使用次数多的代码转换成长度较短的编码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。

哈夫曼编码方法的具体过程是：首先把信源的各个输出符号序列按概率递降的顺序排列起来，求其中概率最小的两个序列的概率之和，并把这个概率之和看做是一个符号序列的概率，再与其他序列依概率递降顺序排列(参与求概率之和的这两个序列不再出现在新的排列之中)。然后，对参与概率求和的两个符号序列分别赋予二进制数字0和1。继续这样的操作，直到剩下一个以1为概率的符号序列。最后，按照与编码过程相反的顺序读出各个符号序列所对应的二进制数字组，就可分别得到各该符号序列的码字。

哈弗曼编码原理：哈夫曼编码是上个世纪五十年代由哈夫曼教授研制开发的，它借助了数据结构当中的树型结构，在哈夫曼算法的支持下构造出一棵最优二叉树，我们把这类树命名为哈夫曼树。因此，准确地说，哈夫曼编码是在哈夫曼树的基础之上构造出来的一种编码形式，它的本身有着非常广泛的应用。

众所周知，在计算机当中，数据的存储和加工都是以字节作为基本单位的，一个西文字符要通过一个字节来表达，而一个汉字就要用两个字节，我们把这种每一个字符都通过相同的字节数来表达的编码形式称为定长编码。以西文为例,例如我们要在计算机当中存储这样的一句话：I am a teacher 。就需要15个字节，也就是120个二进制位的数据来实现。

与这种定长编码不同的是，哈夫曼编码是一种变长编码。它根据字符出现的概率来构造平均长度最短的编码。换句话说如果一个字符在一段文档当中出现的次数多，它的编码就相应的短，如果一个字符在一段文档当中出现的次数少，它的编码就相应的长。当编码中，各码字的长度严格按照对应符号出现的概率大小进行逆序排列时，则编码的平均长度是最小的。这就是哈夫曼编码实现数据压缩的基本原理。

建立哈弗曼编码树

哈夫曼（Huffman）编码的核心部分为哈夫曼编码树（huffman coding tree）。对于所有可能的输入符号（通常对应为字节）在哈夫曼编码树上都有对应的一个叶节点，在叶节点的位置就是该符号的哈夫曼编码。具体来说，一个符号对应的哈夫曼编码就是从根节点开始，沿左字节点（0）或右子节点（1）前进，一直找到该符号叶节点为止的路径对应的二进制编码。同其他码词长度可变的编码一样，区别在于不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种称为“编码树”（coding tree）的技术。

算法步骤如下： 

（1）初始化，把n个字符根据符号概率的大小按由大到小顺序对符号进行排序。 

（2）对概率最小的两个符号按照递增（递减）排列组成一个新符号（节点），然后把这两个概率相加作为新的节点的概率。 

（3）将这个新的辅助符号与其他符号一起重新按概率大小顺序排列。

（4）重复第（2）步，直到概率相加等于1为止。 

（5）从编码树的根开始回溯到原始的符号，并将每一左分枝赋值为“1”，右分枝赋值为“0”。

哈夫曼编码的算法实例

下面我们以abcddbb为例，根据a,b,c,d 四个字符在原始数据串中出现的频率，构造静态哈夫曼编码树。

统计结果如表所示：

然后，按照前面提到的构造方法，经过表 2 的四个步骤，即可获得基于表 1 频率统计的哈夫曼编码树。

至此，我们建立起了给定符号串的哈夫曼编码树。经过编码 a:000，b:1，c:001，d:01。

注意：霍夫曼编码不唯一，同一层上的结点，位置是可以互换的。哈夫曼树不唯一，所以，编码也不唯一。

但是一旦哈夫曼树构造好了之后，哈夫曼编码是唯一的。

霍夫曼编码的硬件实现

霍夫曼编码的原理参考

基于FPGA的Huffman编码并行实现及高速存储系统设计

基于verilog实现哈夫曼编码的新方法

文章来源: reborn.blog.csdn.net，作者：李锐博恩，版权归原作者所有，如需转载，请联系作者。

原文链接：reborn.blog.csdn.net/article/details/80461513