哈夫曼编码

通信工程学院

《信息论与编码》大作业

课

程 名 称 信息论与编码

学 生 班 级 电子信息121

学 生 姓 名 顾 健

实验成绩评定

指导教师签字

年 月 日

基于C++语言的哈夫曼(Haffman)编码

哈夫曼(Haffman)编码是一种常用的压缩编码方法，是哈夫曼于1952年为压缩文本文件建立的。它的基本原理是按照概率大小顺序排列信源符号，并设法按逆顺序分配码字字长，使编码的码字为可辨识的。哈夫曼码是最佳码。

二进制哈夫曼码的编码步骤如下：

(1) 将q个信源符号按概率分布p(si)的大小，以递减次序排列起来，设

p1p2p3•••pq

(2) 用0和1码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个符号，从而得到只包含q-1个符号的新信源，称为S信源的缩减信源S1。

(3) 把缩减信源S1的符号仍按概率大小以递减次序排列，再将最后两个概率最小的符号合并成一个符号，并分别用0和1码符号表示，这样又形成了q-2个符号的缩减信源S2。 (4) 依此继续下去，直至最后只剩两个符号为止。将这最后两个信源符号分别用0和1码符号表示。然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即对应的码字。

下面举一个具体的Huffman编码的例子(如图1所示)：

信源符号 概率 信源缩减过程 编码 码长 S1 0.4 0.4 0.4 0.6 0 1.0 00 2 S2 0.2 0.2 0.4 0 0.4 1 10 2 S3 0.2 0.2 0 0.2 1 11 2 S4 0.15 0 0.2 1 010 3 S5 0.05 1 011 3 图1 Huffman编码示例 它的平均码长为

Lp(si)li0.420.220.220.1530.0532.2(码符号/信源符号)

i15信息熵为

H(S)-p(si)log(si)2.08(比特/信源符号)

i15编码效率为

H(S)2.08100%94.5% L2.2哈夫曼编码方法得到的码并非是唯一的。造成非唯一的原因是：

(1) 任意的，每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意

的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。

(2) 对信源进行缩减时，两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。 算法的实现：

(1) 对于Huffman编码问题，在构造Huffman树时，要求能方便地实现从父结点到左右孩子结点的操作，在进行Huffman编码时，又要求能方便地实现从孩子结点到父结点的操作。因此，设计Huffman树的结点存储结构为父亲孩子存储结构。

根据数据结构理论可知，二叉数结点的父亲孩子存储结构可用仿真指针实现。另外，每个结点还要有权值域。其元素结构如下：

weight parent leftchild rightchild

由Huffman编码过程可见，从Huffman树求叶子结点的Huffman编码实际上是从叶子结点到根结点路径分支的逐个遍历，每经过一个分支就得到一位Huffman编码值。因此，需要一个数组bit[MaxBit]保存每个叶子结点到根结点路径所对应的Huffman编码。由于是不等长编码，需要一个数据域len表示每个Huffman编码的长度。这样，每个叶子结点的Huffman编码是从数组bit的起始位置start开始到数组结束位置中存放的0到1的序列，data对应的是被编码的字符。存放Huffman编码的数据元素结构如下： len data Bit[0] Bit[1] ...... Bit[MaxBit-1] (2) 算法步骤如下： 1) 定义哈夫曼树的结点结构huffnode。 2) 定义哈夫曼编码的结构huffcode。 3) 数组初始化。 4) 构造哈夫曼树。

① 构造n棵只有一个根结点的二叉树，并找出根结点权值最小的两棵树； ② 将找出的两棵树合并为一颗子树。 5) 求各字符的哈夫曼编码。 6) 输出字符的哈夫曼编码。

要求：对任意的符号序列进行哈夫曼编码，并给出编码效率。

哈夫曼编码的c++程序：

/*******************哈夫曼编码*******************/ #include #include #include #define n 100 #define m 2*n-1 //码结点的存储结构 typedef struct { char ch; char bits[9]; int len;

}CodeNode;

typedef CodeNode HuffmanCode[n+1]; //树结点的存储结构 typedef struct { int weight; int lchild,rchild,parent; }HTNode;

typedef HTNode HuffmanTree[m+1]; int num;

//挑选权值最小的两个结点

void select(HuffmanTree HT,int k,int &s1,int &s2) { int i,j; int minl=32767; for(i=1;i<=k;i++) if(HT[i].weight//统计输入字符和串

int jsq(char *s,int cnt[],char str[]) { char *p; int i,j,k=0; int temp[257]; for(i=0;i<257;i++) temp[i]=0; for(p=s;*p!='\\0';p++) temp[*p]++; for(i=0,j=0;i<=256;i++) if(temp[i]!=0) {

j++; str[j]=i; cnt[j]=temp[i]; } num=j; return j; }

//建立哈夫曼树

void chuffmanTree(HuffmanTree&HT,HuffmanCode&HC,int cnt[],char str[]) { int i,s1,s2; for(i=1;i<=2*num-1;i++) { HT[i].lchild=0; HT[i].rchild=0; HT[i].parent=0; HT[i].weight=0; } for(i=1;i<=num;i++) HT[i].weight=cnt[i]; for(i=num+1;i<=2*num-1;i++) { select(HT,i-1,s1,s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } for(i=1;i<=num;i++) HC[i].ch=str[i]; }

//给哈夫曼树的每个叶子结点分配二进制码

void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC) { int c,p,i; char cd[n]; int start; cd[num]='\\0'; for(i=1;i<=num;i++)//1到num为叶子结点，每个结点都有一个二进制编码串 { start=num; c=i; while((p=HT[c].parent)>0)

{ start--; cd[start]=(HT[p].lchild==c)?'0':'1'; c=p; } strcpy(HC[i].bits,&cd[start]); HC[i].len=num-start; } }

//译码

void decode(HuffmanCode HC,char receive[],char s[]) { char str[268]; char cd[9]; int i,j,k=0,p=0,cjs; while(receive[p]!='\\0') { cjs=0; for(i=0;i//输出字符串的二进制编码

void coding(HuffmanCode HC,char str[],char get[]) { int i,j=0; while(str[j]!='\\0') { for(i=1;i<=num;i++) if(HC[i].ch==str[j])

{ strcat(get,HC[i].bits); break; } j++; } strcat(get,\"\\0\"); }

//计算编码效率

double code_ratio(char st[],int cn[],HuffmanCode HC) { double up=0.0,down=0.0,temp=0.0; int i=1,len=strlen(st); for(i;i<=num;i++) { temp=cn[i]/double(len); up-=temp*(log(temp)/log(2)); down+=temp*HC[i].len; } return(up/down)*100; }

void main() { char str[257];//str用于在统计输入序列中的字符时用，存放是什么字符，1到256 char st[10000],s[10000];//st用来接受输入的字符串，s用来接受解压的字符串 int cn[257]; //cn用来接受统计后的每个字符的频率，1到256 HuffmanTree HT; HuffmanCode HC; printf(\"输入要编码的字符串：\"); scanf(\"%s\ num=jsq(st,cn,str);//统计文件中的字符 str[num+1]='\\0'; chuffmanTree(HT,HC,cn,str);//建立哈夫曼树 HuffmanEncoding(HT,HC);//根据哈夫曼建立哈夫曼编码 printf(\"共有%d种符号\\n\ for(int i=1;i<=num;i++) printf(\"字符%c次数为%d,编码为%s\\n\ char get[10000]; get[0]='\\0'; coding(HC,st,get); printf(\"上述字符串的哈夫曼码为%s\\n\ printf(\"编码效率为%f%%\\n\ printf(\"输入二进制码开始译码：\"); char receive[10000];

scanf(\"%s\ decode(HC,receive,s);//译码 printf(\"译码得：%s\\n\}

代码验证情况如下：