霍夫曼编码含源程序.docx
《霍夫曼编码含源程序.docx》由会员分享，可在线阅读，更多相关《霍夫曼编码含源程序.docx（22页珍藏版）》请在冰点文库上搜索。
霍夫曼编码含源程序
多媒体技术基础实验报告
——霍夫曼编码
学院：
电子工程与光电技术学院
专业：
电子信息工程
姓名：
学号：
任课老师：
康其桔
实验时间：
一、实验内容及要求
1、使用Matlab编程实现霍夫曼编码
2、通过键盘输入字符串
3、在屏幕上显示编码结果
二、实验原理
霍夫曼编码是霍夫曼在1952年提出和描述的“从下到上”的熵编码方法。
根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。
这些元素（如字母）出现的次数越多，其编码的位数就越少。
其基本步骤为：
（1）将压缩的各字符的出现概率按减少（或增加）的顺序进行排列。
（2）将两个最小的概率进行组合相加得到一个新概率将这一新概率与其它概率一起继续执行1和2的操作直至最后概率为1.0。
（3）对每对组合中的概率较大者指定为1,较小者指定为0。
（4）画出由每个信源符号概率到1.0处的路径记下路径的1和0。
（5）对每个信源符号由从右到左写出1/0序列，对概率较高的标1，对概率较低的标0（或对概率较高的标0，对概率较低的标1），就得到了对应的Huffman码。
下面举个例子来说明霍夫曼编码的具体过程。
设需要编码的信息为：
BACDEBACDEBACDEBADEBAEBABABABB,统计各个字符出现的次数分别为B（10次）、A（8次）、C（3次）、D（4次）、E（5次）。
各个字符出现的概率为B（10/30）、A（8/30）、E（5/30）、D（4/30）、C（3/30）。
霍夫曼编码的过程如下：
B（10/30）
A（8/30）
E（5/30）
D（4/30）
C（3/30）
霍夫曼编码后平均码长为
。
而信源熵
。
由此，我们可以看出，霍夫曼编码结果已经很接近理想信源熵。
三、设计方案
设计的流程图如下：
四、各模块设计
（一）读入字符串并去除空格
在Matalb中使用语句inputstring=input（'请输入需要编码的字符:
','s'），输入的字符串存入char型数组inputstring中。
去除空格的思想为：
输出的inputletters数组存储的是输入字符串去除空格后的字符集的ASCII值，如果需要显示字符需要用语句：
disp（char（inputletters））。
这一部分代码如下：
inputstring=input（'请输入需要编码的字符:
','s'）;%输入字符并存储
spacenumber=0;%存储空格数目
fori=1:
length（inputstring）
ifabs（inputstring（i））==32
spacenumber=spacenumber+1;
continue
else
inputletters（i-spacenumber）=inputstring（i）;
end
end
disp（['去除空格后字符为：
',char（inputletters）]）
（二）统计字符种类及概率
统计字符的种类，需要去除输入字符中的重复字符，并存入数组letters中，其基本流程图如下：
这一部分的程序如下：
letters
（1）=inputletters
（1）;
form=2:
length（inputletters）
repeatn=0;%定义一个数记录是否有重复
forn=1:
length（letters）
ifletters（n）==inputletters（m）
repeatn=repeatn+1;
end
end
ifrepeatn==0
letters（length（letters）+1）=inputletters（m）;
end
end
概率的统计即是统计letters中每个元素在inputletters出现的次数，除以总次数即可得到每个字符出现的概率。
概率统计的程序如下：
forp=1:
length（letters）
repeatn=0;%计算重复次数
forq=1:
length（inputletters）
ifletters（p）==inputletters（q）
repeatn=repeatn+1;
end
end
letterp（p）=repeatn/length（inputletters）;
end
对得到概率letterp进行降序排序得到huffmanprob，并使字符集与概率相对应生成字符集huffamnletters。
这一过程主要是为了方便输出字符集的输出。
这一部分的程序如下：
[huffmanprob,sort_index]=sort（letterp）;%用来霍夫曼编码的概率
huffmanprob=（fliplr（huffmanprob））';
sort_index=fliplr（sort_index）;
fori=1:
length（huffmanprob）
huffmanletters（i）=letters（sort_index（i））;%用来霍夫曼编码的字符集
end
disp（'----------------------------字符及概率-------------------------------'）
fori=1:
length（huffmanletters）
fprintf（'字符：
%-4s概率：
%5.4f\n',char（huffmanletters（i））,huffmanprob（i））
end
（三）霍夫曼编码
根据实验原理，在使用Matlab编程实现霍夫曼编码的过程中，需要定义一个元胞数组huffmantabel来存储霍夫曼码表。
这个元胞数组的长度与huffman-letters中字符相对应。
同时还需定义一个元胞数组numorder来存储每个字符的概率在原概率矩阵中的位置。
其基本流程图如下：
whilelength（numorder）>1
[temp,ind]=sort（huffmanprob）;
pminorder=numorder{ind
（1）};pmin=huffmanprob（ind
（1））;
pnminorder=numorder{ind
（2）};
pnmin=huffmanprob（ind
（2））;
fori=1:
length（pminorder）
huffmantabel{pminorder（i）}=[1,huffmantabel{pminorder（i）}];
end
forj=1:
length（pnminorder）
huffmantabel{pnminorder（j）}=[0,huffmantabel{pnminorder（j）}];
end
numorder（ind（1:
2））=[];
numorder{length（numorder）+1}=[pminorder,pnminorder];
huffmanprob（ind（1:
2））=[];
huffmanprob（length（huffmanprob）+1）=pmin+pnmin;
end
（四）霍夫曼解码
在进行霍夫曼解码的过程中，需要将霍夫曼码序列中的元素与霍夫曼码表中的元素进行比较，若一样则输出相对应的字符。
由于考虑到霍夫曼码长可变，我们可以归纳每个霍夫曼码的特点，每个霍夫曼码可以用其码长以及十进制数值唯一表示，将其十进制及码长存入一个新的元胞数组huffmandec中，将霍夫曼码元中的一位位取出，算出其十进制对应的值tempsum及二进制长度i存入一个数组A中，使用语句c2=find（cellfun（@（t）all（A（:
）==t（:
））,huffmandec））;即可找到元胞数组huffmandec中与数组A相同的数组的位置。
利用这个次序即可找到对应的huffmanletters数组中的字符删除后的数组重新赋值给huffmanletter-s，将这个字符存入decodeletters，将刚刚统计的i个二进制删除并用语句isequal（decodeletters,inputletters）判断解码输出的结果与输入是否相同。
将二进制霍夫曼码表转变为十进制霍夫曼码表并与长度一起存入元胞数组的语句如下：
fori=1:
length（huffmanletters）
temparray=huffmantabel{i};%temparray是一个临时的矩阵
huffmandec{i}=[bin2dec（num2str（temparray））,length（temparray）];
%用霍夫曼码表的十进制值及长度形成霍夫曼码的唯一标志
end
实现霍夫曼解码的流程图如下：
这一过程所对应的Matlab源程序为：
decodeletters=[];
whileisempty（huffmancodep）==0
tempsum=0;
fori=1:
length（huffmancodep）
tempsum=tempsum*2+huffmancodep（i）;
A=[tempsumi];
c2=find（cellfun（@（t）all（A（:
）==t（:
））,huffmandec））;
ifisempty（c2）==0
decodeletters=[decodelettershuffmanletters（c2
（1））];
huffmancodep（1:
i）=[];
break;
end
end
end
ifisequal（decodeletters,inputletters）==1
disp（'经比较解码输出结果与输入相同'）
end
在完成霍夫曼解码之后经过简单的计算即可求出信源熵，压缩比，以及平均码长。
五、结果演示
以书本例2.2为例，运行程序，输入A（15个）、B（7个）、C（6个）、D（6个）、E（5个），理论结果为
A（0）
B（111）
C（110）
D（101）
E（100）
压缩比为：
1.34
信源熵为2.1857
平均码长为：
2.2308
而经过程序计算的结果为：
经比较，所得结果与例2.2结果相同，即程序运行结果正确
六、源程序
%代码文件:
myhuffman.m
%目的：
从键盘输入字符集使用huffman编码并解码
%
%更改记录
%DateProgrammerDescriptionofchange
%=============================
%5/11Originalcode
%
%重要变量定义：
%inputstring:
输入字符串
%inputletters:
除去空格后的字符串存入的数组
%huffmanletters:
用来霍夫曼编码的字符集
%huffmanprob:
字符集相对应的概率
%huffmantabel:
霍夫曼码表，与字符集顺序对应
%huffmancode:
霍夫曼编码结果
%decodeletters:
霍夫曼解码输出的字符集
%compratio:
压缩比
%--------------------------------开始编码---------------------------------
clc
clearall
inputstring=input（'请输入需要编码的字符:
','s'）;%输入字符并存储
spacenumber=0;%存储空格数目
%================================去除空格==================================
fori=1:
length（inputstring）
ifabs（inputstring（i））==32
spacenumber=spacenumber+1;
continue
else
inputletters（i-spacenumber）=inputstring（i）;
end
end
disp（['去除空格后字符为：
',char（inputletters）]）
%fprintf（'去除空格后字符：
%s',char（letters））
%==========================统计输入字符种类=================================
letters
（1）=inputletters
（1）;
form=2:
length（inputletters）
repeatn=0;%定义一个数记录是否有重复
forn=1:
length（letters）
ifletters（n）==inputletters（m）
repeatn=repeatn+1;
end
end
ifrepeatn==0
letters（length（letters）+1）=inputletters（m）;
end
end
%disp（['输入无重复字符为：
',char（letters）]）
%=============================统计概率=====================================
forp=1:
length（letters）
repeatn=0;%计算重复次数
forq=1:
length（inputletters）
ifletters（p）==inputletters（q）
repeatn=repeatn+1;
end
end
letterp（p）=repeatn/length（inputletters）;
end
%=============================排序并对应===================================
[huffmanprob,sort_index]=sort（letterp）;%用来霍夫曼编码的概率
huffmanprob=（fliplr（huffmanprob））';
sort_index=fliplr（sort_index）;
fori=1:
length（huffmanprob）
huffmanletters（i）=letters（sort_index（i））;%用来霍夫曼编码的字符集
end
%============================输出字符及概率================================
disp（'----------------------------字符及概率-------------------------------'）
fori=1:
length（huffmanletters）
fprintf（'字符：
%-4s概率：
%5.4f\n',char（huffmanletters（i））,huffmanprob（i））
end
%============================开始霍夫曼编码================================
huffmantabel=cell（1,length（huffmanletters））;%定义元胞数组用来存储huffman码表
numorder_temp=1:
length（huffmanletters）;
numorder=num2cell（numorder_temp）;%将1-...这一系列数转变为元胞数组
whilelength（numorder）>1
[temp,ind]=sort（huffmanprob）;%排序，不需要结果，只需要最小概率在原概率中位置
pminorder=numorder{ind
（1）};%根据ind得出最小概率元胞数组对应位置，此位置对应编码字符
pmin=huffmanprob（ind
（1））;
pnminorder=numorder{ind
（2）};
pnmin=huffmanprob（ind
（2））;
fori=1:
length（pminorder）
huffmantabel{pminorder（i）}=[1,huffmantabel{pminorder（i）}];
end
forj=1:
length（pnminorder）
huffmantabel{pnminorder（j）}=[0,huffmantabel{pnminorder（j）}];
end
numorder（ind（1:
2））=[];
numorder{length（numorder）+1}=[pminorder,pnminorder];
huffmanprob（ind（1:
2））=[];
huffmanprob（length（huffmanprob）+1）=pmin+pnmin;
end
%==============================输出霍夫曼码表===============================
disp（'----------------------------霍夫曼码表-------------------------------'）
fori=1:
length（huffmanletters）
%fprintf（'字符：
%-4s概率：
%f\n',char（huffmanletters（i））,num2str（huffmantabel{i}））
disp（['字母：
'char（huffmanletters（i））'''霍夫曼码：
'num2str（huffmantabel{i}）]）
end
%==============================形成霍夫曼码================================
disp（'------------------------------霍夫曼码-------------------------------'）
huffmancode=[];%huffmancode用来存储huffman码
fori=1:
length（inputletters）
c1=find（huffmanletters==inputletters（i））;
huffmancode=[huffmancode,huffmantabel{c1
（1）}];
end
fori=1:
ceil（length（huffmancode）/10）
disp（num2str（huffmancode（（i-1）*20+1:
min（i*20,length（huffmancode）））））
end
%==============================霍夫曼解码================================
huffmancodep=huffmancode;
%将十进制霍夫曼码组元胞数组元素变成十进制数组方便解码
fori=1:
length（huffmanletters）
temparray=huffmantabel{i};%temparray是一个临时的矩阵
huffmandec{i}=[bin2dec（num2str（temparray））,length（temparray）];
%用霍夫曼码表的十进制值及长度形成霍夫曼码的唯一标志
end
%开始解码
decodeletters=[];
whileisempty（huffmancodep）==0
tempsum=0;
fori=1:
length（huffmancodep）
tempsum=tempsum*2+huffmancodep（i）;
A=[tempsumi];
c2=find（cellfun（@（t）all（A（:
）==t（:
））,huffmandec））;
ifisempty（c2）==0
decodeletters=[decodelettershuffmanletters（c2
（1））];
huffmancodep（1:
i）=[];
break;
end
end
end
disp（'------------------------------霍夫曼解码-------------------------------'）
disp（char（decodeletters））
%判断解码结果与输入是否相同
ifisequal（decodeletters,inputletters）==1
disp（'经比较解码输出结果与输入相同'）
end
%==============================计算压缩比================================
disp（'------------------------------压缩比-------------------------------'）
bitsone=ceil（log2（length（huffmanletters）））;%一个字符需要用几位二进制表示
bitsrequired=length（inputletters）*bitsone;%理论上需要的总二进制位数
bitsactual=length（huffmancode）;%huffman编码用到的二进制位数
compratio=bitsrequired/bitsactual;%压缩比
fprintf（'压缩比：
%5.4f\n',compratio）
WelcomeTo
Download!
!
!
欢迎您的下载，资料仅供参考！
升级会员 