哈夫曼编码的实现及应用

第２７卷第４期　２００８年１２月　武汉工业学院学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｗｕｈａｎ　Ｐｏｌｙｔｅｃｈｎｉｃ　Ｕｎｉｖｅｒｓｉｔｙ　ＶｏＬ　２７Ｎｏ．４　ＤｅＣ．２０Ｏ８　

文章编号：１００９－４８８１（２００８）０４－００４６－０４　

通过哈夫曼编码实现文件的压缩与解压　

王防修，周康　

（武汉工业学院数理科学系，湖　Ｅ武汉４３００２３）　

摘要：从介绍常见压缩与解压软件出发，通过分析哈夫曼编码能够压缩一般文件的原理，详　

细说明了通过哈夫曼编码实现文件的压缩与解压的过程，并通过几个不同类型文件的压缩效　果进行检验。同时说明了伪哈夫曼编码表文件能够增强压缩文件的安全性。　

关键词：哈夫曼编码；压缩；解压；二叉排序树；码字　中图分类号：ＴＰ　３１　文献标识码：Ａ　

Ｏ　引言　

为了节省存储空间和提高信息传输的效率，目　

前国内外已经开发出了ＰＫＺＩＰ、ＡＲＴ、ＡＲＣ、ＬＨＡ、　

ＷＩＮＺＩＰ等对文件进行压缩与解压　的软件，这些　

软件的通用性较好，操作也比较方便，同时也可以对　

信息起到一定的安全保护作用。然而，这些压缩与　

解压软件都是基于Ｌｚｗ码的改进算法的基础上开　发的。事实上，哈夫曼编码　作为一种变长编码技　

术，由于它能充分利用短码，所以同样可以根据它来　

开发相应的压缩与解压软件，并且这种压缩与解压　

软件简单易用，安全保密性能好。　

本文所述的压缩与解压软件的开发，采用了哈　

夫曼编码技术，同时结合了哈夫曼编码表的查询技　

术，解决了变长编码的存储困难、程序应变能力较差　及程序设计比较复杂等问题。而且文件的压缩比和　

信息的安全性都得到很大的提高。　

１基本原理　

１．１文件能够被压缩的理论依据　定义１对于给定的信源和码符号集，若有一　个唯一可译码，其平均码长Ｚ小于所有其他唯一可　

译码，则称这种码为紧致码或最佳码。　

定理１　哈夫曼编码是紧致码…。　

收稿日期：２００８－０７—１１　基金项目：湖北省自然科学基金项目（２００７ＡＢＡ４０７）。　作者简介：王防修（１９７３一），男，湖北省蕲春县人，讲师。　计算机文件是以字节为单位组成的，每个字节　的取值从０到２５５。每个字节都看成字符，共２５６　

建筑大学

电气与电子信息工程学院

信息理论与编码课程设计报告

设计题目：哈夫曼编码的分析与实现

专业班级： 电子信息工程 101

学生： _____________________________

学 号： ________________________________

扌指导教师： 吕卅 王超 ________________

设计时间： 2013.11.18 — 2013.11.29

教师评语： 成绩 评阅教师 日期

、设计的作用、目的

《信息论与编码》是一门理论与实践密切结合的课程 , 课程设计是其实践性 教学环节之一， 同时也是对课堂所学理论知识的巩固和补充。 其主要目的是加深 对理论知识的理解， 掌握查阅有关资料的技能， 提高实践技能， 培养独立分析问 题、解决问题及实际应用的能力。

通过完成具体编码算法的程序设计和调试工作， 提高编程能力， 深刻理解信 源编码、信道编译码的基本思想和目的， 掌握编码的基本原理与编码过程， 增强 逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际 问题的能力，逐步熟悉开展科学实践的程序和方法

二、设计任务及要求

通过课程设计各环节的实践，应使学生达到如下要求：

1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；

2. 掌握哈夫曼编码 / 费诺编码方法的基本步骤及优缺点；

3. 深刻理解信道编码的基本思想与目的， 理解线性分组码的基本原理与编 码过程；

4. 能够使用MATLA或其他语言进行编程，编写的函数要有通用性。

三、 设计容

一个有8个符号的信源X,各个符号出现的概率为：

X x1, x2, x3, x4, x5, x6 x7 x8

P(X) 0.4 0.18 0.1 0.1 0.07 0.06 0.05 0.04

编码方法：先将信源符号按其出现的概率大小依次排列，并取概率最小的字 母分别配以 0和1两个码元(先 0后1或者先 1后0，以后赋值固定)，再将这 两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队。 并不断重复这一过程， 直到最后两个符号配以 0和1为止。最后从最后一级开始， 向前返回得到各个信源符号所对应的码元序列，即为对应的码字。

二进制无损压缩算法是一类数据压缩算法，用于减小二进制数据的存储空间而不损失任何信息。这些算法可以应用于各种数据类型，包括文本文件、图像、音频和视频等。以下是几种常见的二进制无损压缩算法：

1. Lempel-Ziv压缩算法（LZ）：LZ系列算法是一类基于词典的压缩算法，包括LZ77和LZ78等。这些算法通过使用字典来存储先前出现过的数据片段，并使用指针来引用这些片段，从而实现压缩效果。

2. 哈夫曼编码：哈夫曼编码是一种基于出现频率的编码方式。它通过使用较短的编码来表示出现频率较高的符号，以及较长的编码来表示出现频率较低的符号，从而实现有效的压缩效果。

3. 算术编码：算术编码是一种流程式压缩技术，它根据输入数据的概率分布将整个消息映射到一个介于0和1之间的单个数字。这个数字表示了整个消息的压缩表示，可以根据概率分布进行解码还原。

4. Burrows-Wheeler变换（BWT）：BWT是一种重排输入数据的技术，通过重新排列输入数据来增加重复性，然后再将其与其他压缩算法结合使用，例如Move-to-Front编码和哈夫曼编码，以实现更好的压缩效果。

5. Lempel-Ziv-Markov链算法（LZMA）：LZMA是一种组合了LZ77和哈夫曼编码的压缩算法。它使用LZ77找到重复出现的数据片段，然后使用哈夫曼编码对这些片段进行进一步压缩。

这些算法通常会根据输入数据的特点选择最适合的压缩技术。通过使用这些技术，可以在保留数据完整性的同时大幅减少数据占用的存储空间，使数据传输更加高效。

基于哈夫曼编码的通信系统的设计与实现

一、实验目的

（1）掌握二叉树的存储结构及其相关操作。

（2）掌握构造哈夫曼树的基本思想，及其编码/译码过程。

二、实验内容

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道，每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个基于哈夫曼编码的通信系统。

一个完整的系统应具有以下功能

1）初始化处理：建立通信系统

（1）建立有100句中文的信息集合，每个句子称为一条信息。

（2）输入编码参数：

①从终端输入编码字符集大小n，字符编码长度m（设n为4，m为8）；

②从终端输入编码字符（设为A,B,C,D）;

（3）生成每条信息的字符编码，构造字符编码集合；

（4）计算每个字符编码集合中出现的概率；

（5）根据字符概率构造哈夫曼树，求出每个字符的二进制编码。

2）发送端信息编码

（1）用户从信息集合中选择一条信息，找到该信息对应的字符编码；

（2）根据该信息的字符编码，哈夫曼树求出的每个字符的二进制编码，构造出该信息的二进制编码，记录二进制比编码。

3）接受端信息译码

（1）根据得到的信息的二进制编码，利用哈夫曼树求出每个字符的二进制编码还原出信息的字符编码；

（2）根据信息的字符编码，找到对应的信息。

三、源程序代码

#include

#include

#include

char *codechar;

int ncodechar,lcodechar;

int *arraychar[100];

char *temp;

float *proba;

char pass[50];

int passl;

struct node

{

float pro;

int num;

struct node* p;