哈夫曼编码c实现

中南大学

信息论编码实验报告

专业班级:电子信息1002 指导老师：赵颖 姓名:付永军 学号:0909100707

1

目录

一.实验目的 ..................................................................................... 3 二、实验内容 .................................................................................. 3 三、实验原理 .................................................................................. 4 1.1使用MATLAB 实现香农码编码。 ...................................... 4 1.2、使用MATLAB 实现HUFFMAN 编码. ............................... 7 2.1、使用C++实现香农码编码 ................................................ 9 1）香农编码原理 ......................................................................... 9 2）编码步骤 ............................................................................... 10 2.2、使用C++实现HUFFMAN 编码....................................... 14 四．实验结果 ................................................................................ 17

2

一.实验目的

1. 掌握香农码和 Huffman 编码原理和过程。

2. 熟悉 matlab 软件的基本操作，练习使用matlab 实现香农码和Huffman 编码。

3. 熟悉 C/C++语言，练习使用C/C++实现香农码和Huffman 编码。 4. 应用 Huffman 编码实现文件的压缩和解压缩。

二、实验内容

1、使用matlab 实现香农码和Huffman 编码，并自己设计测试案例。 2、使用C\\C++实现香农码和Huffman 编码，并自己设计测试案例。 3、可以用任何开发工具和开发语言，尝试实现Huffman 编码应用在数据文

件的压缩和解压缩中，并自己设计测试案例。

3

三、实验原理

1.1使用matlab 实现香农码编码。

编程方法：

据课本上的介绍编码香农码的方法。

首先，给定信源符号概率，要先判断信源符号概率是否满足概率分布，即各概率之和是否为1，如果不为1就没有继续进行编码的必要，虽然任可以正常编码，但编码失去了意义。

其次，对信源符号概率进行从小到大的排序，以便进行下一步。从第一步就知道信源符号的个数n，于是构造一个nx4的零矩阵D，以便储存接下来运算的结果。把排好序的信源符号概率以列的形式赋给D的第一列。

再次，做编码的第二步，求信源符号概率的累加概率（方法见程序），用来编写码字。

接着求各信源符号概率对应的自信息量，用于求解码长k。 然后，我们对刚求的自信息量对无穷方向取最小正整数，得到的最小正整数就是该信源符号所对应编码的码长k，有了码长，接下来就可以求解码字。

最后，对所求到的累加概率求其二进制，取其小数点后的数，所取位数由该信源符号对应的码长决定，所用的步骤结束，依次得到各信源符号的香农编码。

4

程序展现：

clc; clear;

A=[0.4,0.3,0.1,0.09,0.07,0.04]; A=fliplr(sort(A));%降序排列 [m,n]=size(A);

for i=1:n

B(i,1)=A(i);%生成B的第1列 end

%生成B第2列的元素 a=sum(B(:,1))/2;

for k=1:n-1

if abs(sum(B(1:k,1))-a)<=abs(sum(B(1:k+1,1))-a) break; end end

for i=1:n%生成B第2列的元素 if i<=k B(i,2)=0; else

B(i,2)=1; end

end

%生成第一次编码的结果

END=B(:,2)'; END=sym(END);

%生成第3列及以后几列的各元素 j=3;

while (j~=0) p=1;

while(p<=n) x=B(p,j-1); for q=p:n if x==-1 break; else

if B(q,j-1)==x y=1; continue; else

y=0;

5

break; end end end if y==1 q=q+1; end

if q==p|q-p==1 B(p,j)=-1; else

if q-p==2 B(p,j)=0;

END(p)=[char(END(p)),'0']; B(q-1,j)=1;

END(q-1)=[char(END(q-1)),'1']; else

a=sum(B(p:q-1,1))/2; for k=p:q-2

if abs(sum(B(p:k,1))-a)<=abs(sum(B(p:k+1,1))-a); break; end

end

for i=p:q-1 if i<=k

B(i,j)=0;

END(i)=[char(END(i)),'0']; else

B(i,j)=1;

END(i)=[char(END(i)),'1']; end end end end p=q; end C=B(:,j); D=find(C==-1); [e,f]=size(D); if e==n j=0; else j=j+1; end end

6

A

END for i=1:n

[u,v]=size(char(END(i))); L(i)=v; end

avlen=sum(L.*A)

1.2、使用matlab 实现Huffman 编码.

huffman编码具体实现原理：

1>在输入的概率矩阵p正确的前提条件下,对p进行排序，并用矩阵L记录p排序之前各元素的顺序，然后将排序后的概率数组p的前两项，即概率最小的两个数加和，得到新的一组概率序列，重复以上过程，最后得到一个记录概率加和过程的矩阵p以及每次排序之前概率顺序的矩阵a。

2>新生成一个n-1行n列，并且每个元素含有n个字符的空白矩阵，然后进行huffman编码：

? 将c矩阵的第n-1行的第一和第二个元素分别令为0和1（表示在编码时，根节点之下的概率较小的元素后补0，概率较大的元素后补1，后面的编码都遵守这个原则）

? 然后对n-i-1的第一、二个元素进行编码，首先在矩阵a中第n-i行找到值为1所在的位置，然后在c矩阵中第n-i行中找到对应位置的编码（该编码即为第n-i-1行第一、二个元素的根节点），则矩阵c的第n-i行的第一、二个元素的n-1的字符为以上求得

7

的编码值，根据之前的规则，第一个元素最后补0，第二个元素最后补1，则完成该行的第一二个元素的编码，

? 最后将该行的其他元素按照“矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值”的原则进行赋值，重复以上过程即可完成huffman编码。

3>计算信源熵和平均码长，其比值即为编码密码效率。 程序展现

p=input('please input a number:') %提示输入界面 n=length(p); for i=1:n if p(i)<0

fprintf('\\n The probabilities in huffman can not less than 0!\\n');

p=input('please input a number:') %如果输入的概率数组中有小于0的值，则重新输入

概率数组 end end

if abs(sum(p)-1)>0

fprintf('\\n The sum of the probabilities in huffman can more than 1!\\n');

p=input('please input a number:') %如果输入的概率数组总和大于1，则重新输入概

率数组 end

q=p;

a=zeros(n-1,n); %生成一个n-1行n列的数组

for i=1:n-1

[q,l]=sort(q) %对概率数组q进行从小至大的排序，并且用l数组返回一个数组，该数组表示概率数组q排序前的顺序编号

a(i,:)=[l(1:n-i+1),zeros(1,i-1)] %由数组l构建一个矩阵，该矩阵表明概率合并时的顺

序，用于后面的编码

q=[q(1)+q(2),q(3:n),1]; %将排序后的概率数组q的前两项，即概率最小的两

个数加和，得到新的一组概率序列 end

for i=1:n-1

c(i,1:n*n)=blanks(n*n); %生成一个n-1行n列，并且每个元素的的长度为n的空白

数组，c矩阵用于进行huffman编码，并且在编码中与a矩阵有一定的对应关系

8

end

c(n-1,n)='0'; %由于a矩阵的第n-1行的前两个元素为进行huffman编码加和运算

时所得的最

c(n-1,2*n)='1'; 后两个概率，因此其值为0或1，在编码时设第n-1行的第一个空

白字符为0，第二个空白字符1。 for i=2:n-1

c(n-i,1:n-1)=c(n-i+1,n*(find(a(n-i+1,:)==1))-(n-2):n*(find(a(n-i+1,:)==1))) %矩阵c的第n-i

的第一个元素的n-1的字符赋值为对应于a矩阵中第n-i+1行中值为1的位置在c矩阵中的编码值

c(n-i,n)='0' %根据之前的规则，在分支的第一个元素最后补0 c(n-i,n+1:2*n-1)=c(n-i,1:n-1) %矩阵c的第n-i的第二个元素的n-1的字符与第n-i行的

第一个元素的前n-1个符号相同，因为其根节点相同 c(n-i,2*n)='1' %根据之前的规则，在分支的第一个元素最后补1 for j=1:i-1

c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(a(n-i+1,:)==j+1)-1)+1:n*find(a(n-i+1,:)==j+1)) %矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1

end

end %完成huffman码字的分配

for i=1:n

h(i,1:n)=c(1,n*(find(a(1,:)==i)-1)+1:find(a(1,:)==i)*n) %用h表示最后的huffman编码，矩

阵h的第i行的元素对应于矩阵c的第一行的第i个元素

ll(i)=length(find(abs(h(i,:))~=32)) %计算每一个huffman编码的长度 end

l=sum(p.*ll); %计算平均码长 fprintf('\\n huffman code:\\n');

h

hh=sum(p.*(-log2(p))); %计算信源熵 fprintf('\\n the huffman effciency:\\n');

t=hh/l %计算编码效率

的前面一个元素的位置在c矩阵中的编码值

2.1、使用C++实现香农码编码

1）香农编码原理

香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。

9

如何构造这种码？香农第一定理指出，选择每个码字的长度Ki满足下式

I(xi)≤K﹤I(xi)+1, ?i 就可以得到这种码。这种编码方法就是香农编码。 2）编码步骤

香农编码法冗余度稍大，实用性不大，但有重要的理论意义。编码步骤如下：

（1） 将信源消息符号按其出现的概率大小依次排列 p（x1）≥p（x2）≥?≥p（xn） （2） 确定满足下列不等式整数码长Ki：

-log2p(xi)≤Ki＜-log2p(xi)+1 （3） 为了编成唯一可译码，计算第i个消息的累加概率 Pi=?p(xk)

k?1i?1（4） 将累加概率Pi变成二进制数。

取Pi二进制数的小数点后Ki位即为该消息符号的二进制码字 程序实现

#include #include #include

#define max_CL 10 /*maxsize of length of code*/ #define max_PN 6 /*输入序列的个数*/ typedef float datatype;

typedef struct SHNODE {

datatype pb; /*第i个消息符号出现的概率*/ datatype p_sum; /*第i个消息符号累加概率*/ int kl; /*第i个消息符号对应的码长*/ int code[max_CL]; /*第i个消息符号的码字*/

10

node_len[i]=q; return; }

stk[q++] = '0';

traverse_tree(tree[i].rnode); q--;

stk[q++] = '1';

traverse_tree(tree[i].lnode); q--; } int main()

{

int i = 0,tmp_total=0; double check = 0; node x; memset(tree, 0, sizeof(tree)); memset(used, 0, sizeof(used));

memset(node_len,0,sizeof(node_len));

printf(\输入符号个数:\\n\

scanf(\ if (total <= 0 || total > N / 2) { printf(\ return 1; }

printf(\输入符号概率:\\n\ tmp_total=total;

while (tmp_total--) {

scanf(\

if (x.probobility < 0 || x.probobility > 1) { printf(\ return 2;

}

check += x.probobility; x.lnode = -1; x.rnode = -1; tree[p++] = x; }

if (fabs(check - 1) > 1e-15) {

printf(\ return 2;

}

create_tree();

printf(\

16

traverse_tree(p - 1); print_avg_len(); return 0; }

四．实验结果

1、 使用matlab 实现香农码和Huffman 编码 （1）

（2）

17

2、 使用C++实现香农码和Huffman 编码 （1）

（2）

18

19

本文来源：https://www.bwwdw.com/article/pee8.html