原创 自适应霍夫曼编码原理

HUFFMAN编码是 1952年由HUFFMAN提出的一种比较常用的变长编码方法，其主导思想是根 据源数据符号发生的概率进行编码。在源数据中出现概率越高的符号，相应的码长越短 ；出现概率越小的符号，其码长越长，从而达到用尽可能少的码符号表示源数据。理论 研究表明，HUFFMAN编码方法是接近压缩比上限的一种较好的编码方法。HUFFMAN编码需 对原始数据进行两遍扫描，第一遍统计原始数据中各字符出现的频率，由此创建HUFFMA N树并将其有关信息保存起来，以便解压时使用；第二遍则根据所得到的HUFFMAN树对原 始数据进行编码，并将编码信息保存起来。这种传统HUFFMAN编码是一种静态的编码方法 ，在实际应用系统中它有很大的局限性，特别在诸如通信等实时传输、处理的系统中 , 更不允许这种两次处理过程。自适应HUFFMAN编码是相对上述方法的一种动态编码方法 ,它对数据编码的依据是动态变化的HUFFMAN树 ,也就是对第Ｋ +1个字符的编码是根据原 始数据中前Ｋ个字符得到的HUFFMAN树来进行的。此外 ,压缩和解压子程序具有相同的初 始化树 ,每处理完一个字符 ,压缩和解压使用相同的算法修改HUFFMAN树 ,因而不需要为 解压而保存树的有关信息。压缩和解压一个字符所需要的时间与该字符的编码长度成正 比 ,所以该过程可以实时进行 自适应编码的动态特性体现在压缩用的代码表在压缩处 理过程中不断变化 ,每从源数据流读入一个字符 ,就要按字符发生的频率重新调整各字 符的编码 ,从而保持当前的编码始终处于编码效果的最佳状态。因此 ,自适应HUFFMAN编 码要解决的主要问题是HUFFMAN树的更新 ,其更新步骤如下 : (1)增加输入字符所在叶结 点的权重 ;(2 )检查HUFFMAN树是否仍满足兄弟特性 ,若是则保持HUFFMAN树的结构不变 ,执行 (4),否则执行(3 );(3 )当不满足兄弟特性时 ,要调整HUFFMAN树的结构 ,具体操 作是 :与序号高于、权重小于该结点的结点交换字符及权重。若有多个结点满足此条件 ,则与最右边的结点进行交换 ;若欲交换的结点是非叶结点 ,则应将该结点及后代作为 一个整体进行交换 ; (4)根据调整后的HUFFMAN树 ,按结点指针依次调整各结点的父结点 权重。总之 ,自适应HUFFMAN编码方法中 ,每当读入一个字符就要调整字符的计数 ,并进 行HUFFMAN树的更新。在整个编码过程中 ,HUFFMAN树一直动态地随输入数据中字符的权 重进行调整 ,并立即进行压缩编码。因此 ,自适应HUFFMAN编码方法可随时确保编码效率 最高 ,而且一次扫描源数据文件即可完成计数和编码 ,从而能更好适应于实时编码传输 系统