霍夫曼编码(含源程序)

1、多媒体技术基础实验报告  霍夫曼编码学院：电子工程与光电技术学院 专业：电子信息工程姓名： 学号： 任课老师：康其桔实验时间：一、实验内容及要求 1、使用Matlab编程实现霍夫曼编码2、通过键盘输入字符串3、在屏幕上显示编码结果二、实验原理 霍夫曼编码是霍夫曼在1952年提出和描述的“从下到上”的熵编码方法。根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少。其基本步骤为：(1) 将压缩的各字符的出现概率按减少(或增加)的顺序进行排列。(2) 将两个最小的概率进行组合相加得到一个新概率将这一新概率与其它概率一起继

2、续执行1 和2 的操作直至最后概率为1.0。(3) 对每对组合中的概率较大者指定为1,较小者指定为0。(4) 画出由每个信源符号概率到1.0处的路径记下路径的1和0。(5) 对每个信源符号由从右到左写出1/0序列，对概率较高的标1，对概率较低的标0(或对概率较高的标0，对概率较低的标1)，就得到了对应的Huffman码。 下面举个例子来说明霍夫曼编码的具体过程。11B:11A:10E:00D:011C:010 设需要编码的信息为：BACDEBACDEBACDEBADEBAEBABABABB,统计各个字符出现的次数分别为B(10次)、A(8次)、C(3次)、D(4次)、E(5次)。各个字符出现的

3、概率为B(10/30)、A(8/30)、E(5/30)、D(4/30)、C(3/30)。霍夫曼编码的过程如下：018/30 B(10/30)0030/30 A(8/30)11 E(5/30)012/307/30 D(4/30) C(3/30) 霍夫曼编码后平均码长为。而信源熵。由此，我们可以看出，霍夫曼编码结果已经很接近理想信源熵。三、设计方案 设计的流程图如下：统计字符种类及概率霍夫曼编码霍夫曼解码读入字符串并去除空格四、各模块设计（一）读入字符串并去除空格 在Matalb中使用语句inputstring=input('请输入需要编码的字符:','s')，输入

4、的字符串存入char型数组inputstring中。 去除空格的思想为：输出数组inputlettersi>length(inputletters)?i=i+1i=i+1，spacenumber= spacenumber+1判断数组inputstring的第i个字符是是空格？否inputletters(i-spacenumber)=inputstring(i);输出的inputletters数组存储的是输入字符串去除空格后的字符集的ASCII值，如果需要显示字符需要用语句：disp(char(inputletters)。这一部分代码如下：inputstring=input('请输

5、入需要编码的字符:','s');%输入字符并存储 spacenumber=0; %存储空格数目 for i=1:length(inputstring) if abs(inputstring(i)=32 spacenumber=spacenumber+1; continue else inputletters(i-spacenumber)=inputstring(i); endenddisp('去除空格后字符为：',char(inputletters)（二）统计字符种类及概率统计字符的种类，需要去除输入字符中的重复字符，并存入数组letters中，其基本流

6、程图如下：letters(1)=inputletters(1)m=m+1从第m个元素判断是否是letters中元素是否letters(length(letters)+1)=inputletters(m)m>length(inputletters)?输出矩阵letters这一部分的程序如下：letters(1)=inputletters(1);for m=2:length(inputletters) repeatn=0; %定义一个数记录是否有重复 for n=1:length(letters) if letters(n)=inputletters(m) repeatn=repeatn+1

7、; end end if repeatn=0 letters(length(letters)+1)=inputletters(m); endend概率的统计即是统计letters中每个元素在inputletters出现的次数，除以总次数即可得到每个字符出现的概率。概率统计的程序如下：for p=1:length(letters) repeatn=0; %计算重复次数 for q=1:length(inputletters) if letters(p)=inputletters(q) repeatn=repeatn+1; end end letterp(p)=repeatn/length(inp

8、utletters);end对得到概率letterp进行降序排序得到huffmanprob，并使字符集与概率相对应生成字符集huffamnletters。这一过程主要是为了方便输出字符集的输出。这一部分的程序如下：huffmanprob,sort_index = sort(letterp); %用来霍夫曼编码的概率huffmanprob=(fliplr(huffmanprob)'sort_index=fliplr(sort_index);for i=1:length(huffmanprob) huffmanletters(i)=letters(sort_index(i); %用来霍夫曼

9、编码的字符集enddisp('-字符及概率-')for i= 1:length(huffmanletters) fprintf('字符：%-4s概率：%5.4fn',char(huffmanletters(i),huffmanprob(i)end（三）霍夫曼编码 根据实验原理，在使用Matlab编程实现霍夫曼编码的过程中，需要定义一个元胞数组huffmantabel来存储霍夫曼码表。这个元胞数组的长度与huffman -letters中字符相对应。同时还需定义一个元胞数组numorder来存储每个字符的概率在原概率矩阵中的位置。其基本流程图如下： while l

10、ength(numorder)>1 temp,ind=sort(huffmanprob); pminorder=numorderind(1); pmin=huffmanprob(ind(1); pnminorder=numorderind(2); pnmin=huffmanprob(ind(2); for i=1:length(pminorder) huffmantabelpminorder(i)=1,huffmantabelpminorder(i); end for j=1:length(pnminorder) huffmantabelpnminorder(j)=0,huffmanta

11、belpnminorder(j); end numorder(ind(1:2)=; numorderlength(numorder)+1=pminorder,pnminorder; huffmanprob(ind(1:2)=; huffmanprob(length(huffmanprob)+1)=pmin+pnmin;end输出huffmantabel否numorder的长度是否大于1是注：sort函数可得到排序后数组中每个元素在huffamprob中的次序对huffmanprob排序将最小的两个概率对应的huffmantabel，最小的一个左边添0，较小的一个左边添1注：关于最小的两个概率是

12、如何对应huffmantabel的：这样对应的关键在于huffmanprob与numorder中的数字是对应的数字与字符相对应，即与huffmantabel相对应。我们可以这么理解，numorder中的数字相当于给每个字符变了号，无论numorder次序如何变化，这个编号不会变。根据这个编号可以对相应字符进行霍夫曼编码，存入相应的huffmantabel中，而比较关键的是概率与这些编号是相对应的，无论如何改变排序。例如，在对最小两个概率对应数组删除时，都将新生成的元素放到最后将最小概率对应numorder中的两个数组合成一个，放到元胞数组最后，并将原数组删除将最小概率对应huffmapro中的

13、两个数相加，放到数组最后，并将原来的数删除（四）霍夫曼解码在进行霍夫曼解码的过程中，需要将霍夫曼码序列中的元素与霍夫曼码表中的元素进行比较，若一样则输出相对应的字符。由于考虑到霍夫曼码长可变，我们可以归纳每个霍夫曼码的特点，每个霍夫曼码可以用其码长以及十进制数值唯一表示，将其十进制及码长存入一个新的元胞数组huffmandec中，将霍夫曼码元中的一位位取出，算出其十进制对应的值tempsum及二进制长度i存入一个数组A中，使用语句c2=find(cellfun(t)all(A(:)=t(:),huffmandec);即可找到元胞数组huffmandec中与数组A相同的数组的位置。利用这个次序即

14、可找到对应的huffmanletters数组中的字符删除后的数组重新赋值给huffmanletter- s，将这个字符存入decodeletters，将刚刚统计的i个二进制删除并用语句isequal(decodeletters,inputletters)判断解码输出的结果与输入是否相同。将二进制霍夫曼码表转变为十进制霍夫曼码表并与长度一起存入元胞数组的语句如下：for i=1:length(huffmanletters) temparray=huffmantabeli; %temparray是一个临时的矩阵 huffmandeci=bin2dec(num2str(temparray),leng

15、th(temparray); %用霍夫曼码表的十进制值及长度形成霍夫曼码的唯一标志end实现霍夫曼解码的流程图如下：输出解码结果decode-letters是huffmancodep是否为空，i=0否i=i+1输入huffmancodep的第i个字符计算前i个二进制数对应的十进制数，并形成矩阵A没有元胞数组huffmantabel中是否有A？有将A对应huffmantabel中位置所对应的字符存入decodeletters，删除huffmancode中的前i个字符这一过程所对应的Matlab源程序为：decodeletters=;while isempty(huffmancodep)=0 te

16、mpsum=0; for i=1:length(huffmancodep) tempsum=tempsum*2+huffmancodep(i); A=tempsum i; c2=find(cellfun(t)all(A(:)=t(:),huffmandec); if isempty(c2)=0 decodeletters=decodeletters huffmanletters(c2(1); huffmancodep(1:i)=; break; end endendif isequal(decodeletters,inputletters)=1 disp('经比较解码输出结果与输入相同

17、')end在完成霍夫曼解码之后经过简单的计算即可求出信源熵，压缩比，以及平均码长。五、结果演示 以书本例2.2为例，运行程序，输入A（15个）、B（7个）、C（6个）、D（6个）、E（5个），理论结果为 A（0） B（1 1 1）C（1 1 0）D（1 0 1）E（1 0 0）压缩比为：1.34信源熵为2.1857平均码长为：2.2308而经过程序计算的结果为：经比较，所得结果与例2.2结果相同，即程序运行结果正确六、源程序%代码文件:myhuffman.m%目的：从键盘输入字符集使用huffman编码并解码% 更改记录% Date Programmer Description of

18、change% = = =% 5/11 Original code%重要变量定义：%inputstring:输入字符串%inputletters:除去空格后的字符串存入的数组%huffmanletters:用来霍夫曼编码的字符集%huffmanprob:字符集相对应的概率%huffmantabel:霍夫曼码表，与字符集顺序对应%huffmancode:霍夫曼编码结果%decodeletters:霍夫曼解码输出的字符集%compratio:压缩比 %-开始编码- clcclear allinputstring=input('请输入需要编码的字符:','s');%输

19、入字符并存储 spacenumber=0; %存储空格数目 %=去除空格= for i=1:length(inputstring) if abs(inputstring(i)=32 spacenumber=spacenumber+1; continue else inputletters(i-spacenumber)=inputstring(i); endenddisp('去除空格后字符为：',char(inputletters)%fprintf('去除空格后字符：%s',char(letters) %=统计输入字符种类= letters(1)=inputlet

20、ters(1);for m=2:length(inputletters) repeatn=0; %定义一个数记录是否有重复 for n=1:length(letters) if letters(n)=inputletters(m) repeatn=repeatn+1; end end if repeatn=0 letters(length(letters)+1)=inputletters(m); endend%disp('输入无重复字符为：',char(letters) %=统计概率= for p=1:length(letters) repeatn=0; %计算重复次数 for

21、 q=1:length(inputletters) if letters(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);for i=1:length(huffmanprob) huffmanletters(i)=

22、letters(sort_index(i); %用来霍夫曼编码的字符集end %=输出字符及概率= disp('-字符及概率-')for i= 1:length(huffmanletters) fprintf('字符：%-4s概率：%5.4fn',char(huffmanletters(i),huffmanprob(i)end %=开始霍夫曼编码= huffmantabel=cell(1,length(huffmanletters); %定义元胞数组用来存储huffman码表 numorder_temp=1:length(huffmanletters);numo

23、rder=num2cell(numorder_temp); %将1-.这一系列数转变为元胞数组while length(numorder)>1 temp,ind=sort(huffmanprob); %排序，不需要结果，只需要最小概率在原概率中位置 pminorder=numorderind(1); %根据ind得出最小概率元胞数组对应位置，此位置对应编码字符 pmin=huffmanprob(ind(1); pnminorder=numorderind(2); pnmin=huffmanprob(ind(2); for i=1:length(pminorder) huffmantabe

24、lpminorder(i)=1,huffmantabelpminorder(i); end for j=1:length(pnminorder) huffmantabelpnminorder(j)=0,huffmantabelpnminorder(j); end numorder(ind(1:2)=; numorderlength(numorder)+1=pminorder,pnminorder; huffmanprob(ind(1:2)=; huffmanprob(length(huffmanprob)+1)=pmin+pnmin;end %=输出霍夫曼码表= disp('-霍夫曼码

25、表-')for i=1:length(huffma nletters) %fprintf('字符：%-4s概率：%fn',char(huffmanletters(i),num2str(huffmantabeli) disp('字母：' char(huffmanletters(i) ' ' '霍夫曼码：' num2str(huffmantabeli)end %=形成霍夫曼码= disp('-霍夫曼码-')huffmancode=; %huffmancode用来存储huffman码for i=1:length(inputletters) c1=find(huffmanletters=inputletters(i); huffmancode=huffmancode,huffmantabelc1(1); endfor i=1:ceil(length(huffmancode)/10)disp(num2str(huffmancode(i-1)*20+1:min(i*20,length(huffmancode)end %=霍夫曼解码= huffmancodep=huffmancode;%将十进制霍夫曼码组元胞数组元素变成十进制