哈夫曼编码信息论大作业模板.docx

哈夫曼编码

哈夫曼编码

1.前言:

Haffman算法是个简单而高效的贪心算法，主要用来创建最优二叉树.可以在通讯时，对于

出现频率较高的字符，用较少的比特数便可以进行通讯.从而节省通讯线路的资源消耗。该算法在各类数据结构,算法,组合数学，离散数学，图论等主题的书籍中都有所涉及。故本文不再赘述，本文致力于用Haffman算法实现压缩与解压缩,采用的语言为C语言，编译环境VC++6.0.

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

这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式，这种空间上的消耗带来了算法实现上的便捷。

由于对于最后生成的Haffman树，其所有叶子结点均为从一个内部树扩充出去的，所以，当外部叶子结点数为m个时，内部结点数为m-1.整个Haffman树的需要的结点数为2m-1.

2压缩过程的实现:

压缩过程的流程是清晰而简单的:

1创建Haffman树à2打开需压缩文件à3将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出à4文件压缩结束。

其中，步骤1和步骤3是压缩过程的关键。

步骤1:这里所要做工作是得到Haffman数中各叶子结点字符出现的频率并进行创建.

统计字符出现的频率可以有很多方法:如每次创建前扫描被创建的文件，“实时”的生成

各字符的出现频率;或者是创建前即做好统计.本文采用后一种的方案,统计了十篇不同的文章中字符出现的频率。当前，也可以根据被压缩文件的特性有针对性的进行统计，如要压缩C语言的源文件，则可事先对多篇C语言源文件中出现的字符进行统计,这样，会创建出高度相对较“矮”的Haffman树，从而提高压缩效果。

创建Haffman树的算法前文已有陈述，这里就不再重复了。

步骤3:将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出.

这是本压缩程序中最关键的部分:这里涉及“转换”和“输出”两个关键步骤:

2.算术编码“转换”部分大可不必去通过遍历Haffman树来找到每个字符对应的哈夫曼编码，可以将每个Haffman码值及其对应的ascii

2.算术编码

算术编码是把一个信源表示为实轴上0和1之间的一个区间，信源集合

中的每一个元素都用来缩短这个区间。

设计思想:其算法的主要算法基本思想：首先就是构造一个结构体用于存储信源的相关信息（包括信源符号，信源概率，编码的上下限）；接着就是初始化信源的相关信息，如初始化编码间隔；利用算术编码的原理构造编码方法，最后实现编码。

调试分析：此算法主要就是算术编码方法的构造，利用算法中Initial_message()函数初始化以后，根据初始化间隔完成编码序列的编码。在调试的过程中经常遇到一些小问题，通过一步步的调试以及修改，问题一个的解决了。同时也遇到比较大的问题，就是编码方法过程的实现，最大的体会就是必须深入理解次编码方法的原理。

流程图

开始

开始

输入信源符号及其概率

初始化信源符号的初始间隔

初始化信源符号的初始间隔

输入要编码的序列

进行算术编码

输出编码结果

结束

测试结果：

” “E＼·

桌面＼茛术编码＼Debug戏积考旨码．exe" 1三』回［汉·|

．

．

石争干，\

石争干，\Lf··'i信须芍号及其概幸，

a 0.2

b0.'4

C0.1

d0.3

言汗符号概幸

abc

d

0.200000

9斗0QG00

o.100000

0.300600

了咕编码间隔

[G.000000,0.200000)

[G.200000.0.6G0000)

IO.600000,0，了00000)[0.700000,1,000000)

清雏.．＼一长'，理为7殁编码们了刓dbacabd

d

[0.700000,1.000000J

b

[0.760000,0.880000)

a

[0.7fi0000,0.78从600)

C

C

[0.TT斗斗00,0.776800)

a

[0.774斗00,0.774880)

b

[0.77斗斗96.0.771.f688)

d[0.774G30,0.774G88)11Prssanuku tocontinu

源程序清单：#include<stdio.h>#include<string.h>#include<conio.h>

#defineN4/