论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

　　四、基于哈夫曼树与哈夫曼编码的数据压缩算法

　　所谓数据压缩，目的在于对需要压缩的数据文件进行可逆编码，使编码的长度小于原数据的长度，通过对哈夫曼编码的研究，我们认识到只要给定字符的概率分布，哈夫曼编码算法能够计算出代码，对于给定概率分布的无前缀代码，产生的编码可以很好的达到数据压缩目标。

　　在哈夫曼编码算法中，编码过程是从叶子结点出发寻找从叶子到根的路径，而译码过程则是从根结点出发，按照0或1确定访问子结点的路径，直到叶结点，从而求得对应的字符。

　　文件由若干个字节组成，一个字节有8bits，故有28=256种字节构成形式，对应字节码为0-255。按此256种字节出现频率可构造haffman树进行重新编码，编码后每字节的新编码平均长度将<=8bits，将每个字节对应了压缩编码写到新文件中，从而达到压缩文件的目的。我们可以采用如下步骤实现基于哈夫曼编码的数据压缩算法：

　　1.扫描源文件所有数据，并统计文件中每个字符出现的频率。

　　2.以每个字符与频率组合建立二叉树结点。

　　3.建立哈夫曼树。

　　4.将哈夫曼树信息写入输出文件，以备解压缩使用。

　　5.再度扫描源文件，将源文件的数据生成对应哈夫曼编码，写入到输出文件。对文件做标示，最终完成源文件的压缩。

　　上面这一算法是根据经典的哈夫曼编码思想引出，压缩时首先扫描源文件，根据源文件中数据出现频率生成字符频率表，据此构造哈夫曼树并生成长短不一的编码，再将哈夫曼编码写入压缩文件，对文件做出标示后完成压缩过程，解压缩时只要逆转编码过程即可。

　　这样的压缩算法能够以较高压缩率完成文件的压缩，不过分析算法步骤后发现，这一算法有明显缺陷，在于需要对源文件进行两次扫描，第一次扫描目的在于统计并建立频率表，以便解压缩使用，第二次扫描目的在于得到哈夫曼编码。如果源文件较大，扫描两次所引发的低效率不容忽视，同时重复扫描也增加了磁盘访问，再次降低压缩效率。

　　因此我们需要改进和优化基于哈夫曼编码的压缩算法，分析前述算法，我们找到效率的瓶颈在于哈夫曼树的建立方式，如果我们能够动态建立哈夫曼树，那么对于源文件的扫描就无需两遍，从而带来效率的提高。

　　那么应当如何构建动态变化的哈夫曼树呢？我们可以考虑从如下角度入手：即动态哈夫曼编码树的建立过程中，第i+1个字符的编码由原始数据中前i个字符所建立的哈夫曼树为依据进行。如何动态建立哈夫曼树，关键在于如何将前i个字符所建立的哈夫曼树调整为前i+1个字符所建立的哈夫曼树，这一关键问题有待进一步研究和思考。

　　参考文献

　　[1]朱怀宏.吴楠.夏黎春，利用优化哈夫曼编码进行数据压缩的探索[J]，微机发展，2002（第05期）

　　[2]蔡茂蓉.姜龙.丁光辉.杨文辉，哈夫曼树的实现及其在文件压缩中的应用[J]，现代计算机（专业版），2008（第11期）