自适应霍夫曼编码

自适应霍夫曼编码院系：信息科学与工程学院

专业：通信与信息系统

学号：10S030084

姓名：吴立亮自适应霍夫曼编码10S030084吴立亮一．引言在实际应用中，经常使用的字符比较集中，每个字符使用的频率相差很大，如果根据字符使用频率的高低不同，采用不同长度的二进制位表示字符，即采用变长编码方法，使用频率高的字符编码短一些，而使用频率低的字符编码长一些，这样就可以明显地减少数据存储和通信时的开销，同时对数据也能起到保密的作用。二、静态霍夫曼编码的的问题哈夫曼编码技术是一种比较常用的变长编码方法，最早由DavidHuffman提出。它采用的是一种优化静态编码方法，由该算法产生的二叉树具有最小的加权路长之和丫WjLj,其中Wj是哈夫曼树中第k个叶结点的重量,Lj为该叶结点到树根的距离。假设原始数据中含有k个各不相同的字符a,a,a，其编码方式就是为这k个12k各不相同的字符都静态地分配一个Lj位的“。”“1”编码序列（因而称为静态哈夫曼编码），该序列指明由根结点到第j个叶结点的路径，“0”表示向左，“1”表示向右，并用该序列替换原始数据中的对应字符。静态哈夫曼方法的最大缺点就是它需要对原始数据进行两遍扫描:第一遍统计原始数据中各字符出现的频率，利用得到的频率值创建哈夫曼树并将树的有关信息保存起来，便于解压时使用;第二遍则根据前面得到的哈夫曼树对原始数据进行编码，并将编码信息存储起来。这样如果用于网络通信中，将会引起较大的延时;对于文件压缩这样的应用场合，额外的磁盘访间将会降低该算法的数据压缩速度。为此Faller等人提出了自适应即动态哈夫曼编码方法，，它对数据编码的依据是动态变化的哈夫曼树，也就是说，对第t+1个字符编码是根据原始数据中前t个字符得到的哈夫曼树来进行的.压缩和解压子程序具有相同的初始化树，每处理完一个字符，压缩和解压方使用相同的算法修改哈夫曼树，因而该方法不需要为解压而保存树的有关信息。压缩和解压一个字符所需的时间与该字符的编码长度成正比，因而该过程可以实时进行。三、自适应霍夫曼编码为了便于说明，我们先进行一些定义。原始数据:需要被压缩的数据压缩数据:被压缩过的数据n:字母表的长度a:字母表中第j个字符jt:已处理的原始数据中字符的总个数k:已处理数据中各不相同字符的个数显然1<j,k<n在压缩开始前，需要引进一个空叶结点，它的重量值始终为。。在以后的压缩和解压过程中，如果kvn,我们用它来表示n-k个字母表中还未出现的字符。初始化的哈夫曼树中只有一个根结点和空叶结点。

压缩子程序读进一个字符后，它将该字符加到根结点的右分枝上，而空叶结点仍留在左分枝上，然后将该字符以A义11码方式输出。解压子程序对其哈夫曼树作同样的调整。以后每读进一个字符a。，压缩子it程序都执行以下的步骤：首先它检查a。是否出现在编码树中，如果是，it压缩子程序就以静态哈夫曼编码中相同的方式对a.进行编码;如果a不在itit编码树中，压缩子程序首先对空叶结点进行编码，然后将a输出，最后编it码树中增加两个结点:在空叶结点的右分枝上加入一个新结点，并将a:放在it里面，然后在其左分枝上加入一个新的空叶结点。自适应哈夫曼编码的关键就是如何将前t个字符的哈夫曼树调整成一棵前t+1个字符的哈夫曼树。为解决上述问题，分两步进行。第1步把前t个字符的哈夫曼树转换成它的另一种形式，在该树中只需在第二步中简单把由根到叶结点a，路径上的所有结

it+1点重量加1，就可以变成前t+1个字符的哈夫曼树.其过程就是以叶结点ait+1为初始的当前结点，重复地将当前结点与具有同样重量的序号最大的结点进行交换，并使后者的父结点成为新的当前结点，直到遇到根结点为止。编码流程见图1。.所谓交换结点，是指交换以该结点为根结点的二叉树（如果该结点有二叉树的话）。叶子结点重量就是该字符已经出现的次数，空叶点的重量可以理解为字母表中尚未出现的字符出现的次数（因为其重量为0）。图1自适应霍夫曼编码流程四、结束语自适应哈夫曼编码数据压缩与复原方法，它克服了静态哈夫曼编码方法需要进行两遍扫描的缺点，具有较强的实时性，对于网络特别是远程通信特别适合。参考文献1方敏,秦晓新,刘本善.动态哈夫