摘要：介绍自适应哈夫曼编码的数据压缩与解压方法及程序流程，给出该方案的压缩性能及其对远程通信的实际效果。
关键词：数据压缩　数据复原　哈夫曼编码　结点　故障信息
分类号：TP 31.56　TM 734

　　随着微型计算机与通信技术的发展与日益成熟，一大批新型的电力系统故障录波装置和SCADA系统源源不断地被引入电力系统，由微波信道(或电力载波、公用电话线等信道)将大批量数据传送到电网调度中心，是目前广为采用的方法。波特率不可能太高，所需通信时间太长的问题已成为一大难题。解决这一难题的有效途径是数据的压缩与解压技术，即将发送端待传输的数据进行压缩，而接收端将接收到的压缩数据解压以获得原始数据。如传输电力系统某一波形数据文件的长度为23 376字节，若不采用压缩而直接传输，所需时间为40 min，若采用自适应的哈夫曼数据压缩与解压技术压缩后再传输，需22 min左右(与波形数据有关)。
　　其次，尽管计算机存储器的价格有降低的趋势，但在数据库应用系统中，数据存储仍然占有相当大的额外费用。因此，在数据库系统中，对数据进行压缩是减少数据存储费用和提高性能的一个很有效的办法。
　　数据压缩技术方法很多，本文论述一种比较实用的自适应哈夫曼数据压缩与解压方法，该方法已被故障录波器所采用。
1　自适应哈夫曼数据压缩与解压原理
　　哈夫曼编码技术是一种比较常用的变长编码方法，最早由Huffman D提出。它采用的是一种优化静态编码方法，由该算法产生的二叉树具有最小的加权长之和∑WjLj，其中Wj是哈夫曼树中第j个叶结点的重量，Lj为该叶结点到树根的距离。静态哈夫曼方法的最大缺点就是它需要对原始数据进行两遍扫描：第一遍统计原始数据中各字符出现的频率，利用得到的频率值创建哈夫曼树并将树的有关信息保存起来，便于解压使用；第二遍扫描则根据前面得到的哈夫曼树对原始数据进行编码，并将编码信息存储起来。此法如果用于网络通信中，将会引起较大的延时。
　　针对上述问题，Faller等人提出了自适应即动态哈夫曼编码方法，它对数据编码的依据是动态变化的哈夫曼树，也就是说，对t+1个字符编码是根据原始数据中前t个字符得到的哈夫曼树来进行的。压缩与解压子程序具有相同的算法修改哈夫曼树，因而该方法不需要为解压而保存树的有关信息。压缩与解压一个字符所需的时间与该字符的编码长度成正比，因而该过程可以实时进行。
　　自适应哈夫曼编码的关键，就是如何将前t个字符的哈夫曼树调整成一棵前t+1个字符的哈夫曼树。为了解决上述问题，我们分两步进行。
　　第一步， 我们把前t个字符的哈夫曼树转换成它的另一种形式， 只需在该树第二步中简单地把由根到叶结点ait+1路径上的所有结点重量加1， 就可以变成前t+1个字符的哈夫曼树。 其过程就是以叶结点ait+1为初始的当前结点， 重复地将当前结点与具有同样重量的序号最大的结点进行交换，并使后者的父结点成为新的当前结点，直到遇到根结点为止。
　　第二步通过将根到叶结点ait+1路径上的所有结点重量加1， 该树就变成了前t+1个字符的哈夫曼树。
2　自适应哈夫曼编码及解码流程及其说明
　　自适应哈夫曼编码流程如图1所示，其解码流程如图2所示。