返回首页
当前位置: 主页 > 编程语言 > C/C++教程 >

利用Huffman编码实现压缩程序代码

时间:2015-07-02 11:54来源:电脑教程学习网 www.etwiki.cn 编辑:admin

本文是对Haffman算法进行的一次实践。根据ascii码文件中各ascii字符出现的频率情况创建Haffman树,再将各字符对应的哈夫曼编码写入文件中。同时,亦可根据对应的哈夫曼树,将哈夫曼编码文件解压成字符文件.

关键词: Haffman算法,压缩,解压缩

Abstract:
This article is a practice of haffman algorithm. First, I create the haffman tree based on the appearance frequency of each ascii character in the files ,then I output each ascii character’s corresponding haffman code to the zipped file. And I also make the program could unzip the haffman zipped files into the ascii files.

Key Words: Haffman Algorithm,Zip,UnZip

前言:
Haffman算法是个简单而高效的贪心算法,主要用来创建最优二叉树.可以在通讯时,对于出现频率较高的字符,用较少的比特数便可以进行通讯.从而节省通讯线路的资源消耗。

该算法在各类数据结构, 算法,组合数学,离散数学,图论等主题的书籍中都有所涉及。故本文不再赘述,本文致力于用Haffman算法实现压缩与解压缩,采用的语言为C语言,编译环境VC++6.0.

下面给出1中实现的Haffman树的结构及创建算法,有两点说明:

这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式,这种空间上的消耗带来了算法实现上的便捷。
由于对于最后生成的Haffman树,其所有叶子结点均为从一个内部树扩充出去的,所以,当外部叶子结点数为m个时,内部结点数为m-1.整个Haffman树的需要的结点数为2m-1.
/*Code1: Haffman Algorithm*/#define MAXCHAR 30000#define MAXNODE 300#define MAXNUM 150#define InfoType charstruct HtNode{ EBTreeType ww; char info; int parentIndex; int llinkIndex; int rlinkIndex;};struct HtTree{ struct HtNode ht[MAXNODE]; int rootIndex;};typedef struct HtTree* PHtTree;PHtTree haffmanAlgorithm(int m,EBTreeType* w){ PHtTree pht; int i,j; int firstMinIndex,secondMinIndex; int firstMinW,secondMinW; pht=(PHtTree)malloc(sizeof(struct HtTree)); assertF(pht!=NULL,"in haffman algorithm,mem apply failure\n"); /*Initialize the tree array*/ for(i=0;i<2*m-1;i++) { pht->ht[i].llinkIndex=-1; pht->ht[i].rlinkIndex=-1; pht->ht[i].parentIndex=-1; if(i<m) { pht->ht[i].ww=w[i]; pht->ht[i].info=(char)i; } else pht->ht[i].ww=-1; } for(i=0;i<m-1;i++)//new Inner Node Num:m-1 { firstMinW=MAXCHAR; firstMinIndex=-1; secondMinW=MAXCHAR; secondMinIndex=-1; for(j=0;j<m+i;j++) { if(pht->ht[j].ww<firstMinW&&pht->ht[j].parentIndex==-1) { //trans minFirst info to minSecond info secondMinIndex=firstMinIndex; secondMinW=firstMinW; //set new first min node. firstMinIndex=j; firstMinW=pht->ht[j].ww; } else if(pht->ht[j].ww<secondMinW&&pht->ht[j].parentIndex==-1) /*update second node info*/ { secondMinW=pht->ht[j].ww; secondMinIndex=j; } } //Construct a new node. m+i is current new node's index pht->ht[firstMinIndex].parentIndex=m+i; pht->ht[secondMinIndex].parentIndex=m+i; pht->ht[m+i].ww=firstMinW+secondMinW; pht->ht[m+i].llinkIndex=firstMinIndex; pht->ht[m+i].rlinkIndex=secondMinIndex; pht->rootIndex=m+i; } return pht;}压缩过程的实现:
压缩过程的流程是清晰而简单的:

创建Haffman树
打开需压缩文件
将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出à4文件压缩结束。
其中,步骤1和步骤3是压缩过程的关键。

步骤1:这里所要做工作是得到Haffman数中各叶子结点字符出现的频率并进行创建.统计字符出现的频率可以有很多方法:如每次创建前扫描被创建的文件,“实时”的生成各字符的出现频率;或者是创建前即做好统计.本文采用后一种的方案,统计了十篇不同的文章中字符出现的频率。当前,也可以根据被压缩文件的特性有针对性的进行统计,如要压缩C语言的源文件,则可事先对多篇C语言源文件中出现的字符进行统计,这样,会创建出高度相对较“矮”的Haffman树,从而提高压缩效果。
创建Haffman树的算法前文已有陈述,这里就不再重复了。

步骤3: 将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出.
这是本压缩程序中最关键的部分:

这里涉及“转换”和“输出”两个关键步骤:

“转换”部分大可不必去通过遍历Haffman树来找到每个字符对应的哈夫曼编码,可以将每个Haffman码值及其对应的ascii码存放于如下所示的结构体中:

typedef struct{ char asciiCode; unsigned long haffCode; int haffCodeLen;}HaffCode;创建由该结构体结点所组成的,长度为128的一维数组codeList128且codeList中的下标和asciiCode满足下面的顺序存放关系:

codeList[i].asciiCode=i;这样的话,查找某个字符inChar的haffman编码的工作便变得相当轻松了,如下:

sHaffCode=codeList[inChar].haffCode;

数组codeList128的创建可以采用某种遍历方式下的按找到的字符进行置数的方式,十分的方便:

顶一下
(0)
0%
踩一下
(0)
0%
标签(Tag):Huffman编码
------分隔线----------------------------
------分隔线----------------------------
发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
验证码:点击我更换图片
推荐内容