霍夫曼编码(含源程序)

多媒体技术基础实验报告霍夫曼编码学院：电子工程与光电技术学院专业：电子信息工程姓名：学号：任课老师：康其桔实验时间：精品资料一、实验内容及要求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 次)。各个11b:11字符出现的概率为 b(10/30) 、a(8/30) 、e(5/30) 、d(4a/3:100) 、c(3/30) 。霍夫曼编码e:00的过程如下：b(10/30)0a(8/30)0e(5/30)118/300130/30d:011 c:010d(4/30) c(3/30)12/3007/30霍夫曼编码后平均码长为2(10 / 308 / 305 / 30)3(4 / 303 / 30)2.23b。而信源熵 h2.19b。由此，我们可以看出，霍夫曼编码结果已经很接近理想信源熵。三、设计方案设计的流程图如下：读入字符串并去除空格统计字符种类及概率霍夫曼编码霍夫曼解码输出数组inputlettersilength(inputletters)?i=i+1判断数组inputstring的第 i 个字符i=i+1， spacenumber=spacenumber+1是空格？是否四、各模块设计（一）读入字符串并去除空格在matalb 中使用语句 inputstring=input(请输入需要编码的字符:,s) ，输入的字符串存入 char 型数组 inputstring 中。去除空格的思想为：inputletters(i-sp acenumber)=inputs tring(i);输出的 inputletters 数组存储的是输入字符串去除空格后的字符集的ascii 值，如果需要显示字符需要用语句：disp(char(inputletters)。这一部分代码如下： inputstring=input(请输入需要编码的字符:,s);% 输入字符并存储spacenumber=0;% 存储空格数目for i=1:length(inputstring)if abs(inputstring(i)=32spacenumber=spacenumber+1;continueelseinputletters(i-spacenumber)=inputstring(i);endenddisp( 去除空格后字符为：,char(inputletters)（二）统计字符种类及概率统计字符的种类， 需要去除输入字符中的重复字符， 并存入数组 letters 中， 其基本流程图如下：letters(1)=inputletters(1)从第 m个元素判断是否是元素letters中m=m+1是否letters(length(letters)+1)=inputletters(m)mlength(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;endendif repeatn=0letters(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;endendletterp(p)=repeatn/length(inputletters);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);% 用来霍夫曼编码的字符集enddisp(-字符及概率)for i= 1:length(huffmanletters)fprintf( 字符： %-4s 概率： %5.4fn,char(huffmanletters(i),huffmanprob(i)end（三）霍夫曼编码根据实验原理，在使用 matlab 编程实现霍夫曼编码的过程中，需要定义一个元胞数组 huffmantabel 来存储霍夫曼码表。这个元胞数组的长度与huffman-letters 中字符相对应。同时还需定义一个元胞数组numorder 来存储每个字符的概率在原概率矩阵中的位置。其基本流程图如下：while length(numorder)1temp,ind=sort(huffmanprob);输出 huffmantabel否numorder 的长度是否大于1pminorder=numorderind(1);pmin=huffmanprob(ind(1);pnminorder=numorderind(2);pnmin=huffmanprob(ind(2);for i=1:length(pminorder)huffmantabelpminorder(i)=1,huffmantabelpminorder(i);endfor j=1:length(pnminorder)huffmantabelpnminorder(j)=0,huffmantabelpnminorder(j);endnumorder(ind(1:2)=;numorderlength(numorder)+1=pminorder,pnminorder;huffmanprob(ind(1:2)=;huffmanprob(length(huffmanprob)+1)=pmin+pnmin;end是对 huffmanprob 排序将最小的两个概率对应的huffmantabel ，最小的一个左边添0 ，较小的一个左边添1将最小概率对应numorder 中的两个数组合成一个，放到元胞数组最后，并将原数组删除将最小概率对应huffmapro 中的两个数相加，放到数组最后，并将原来的数删除注：sort 函数可得到排序后数组中每个元素在 huffamprob中的次序注：关于最小的两个概率是如何对应huffmantabel的：这样对应的关键在于huffmanprob与 numorder 中的数字是对应的数字与字符相对应，即与huffmantabel 相对应。我们可以这么理解，numorder 中的数字相当于给每个字符变了号，无论numorder 次序如何变化， 这个编号不会变。根据这个编号可以对相应字符进行霍夫曼编码，存入相应的huffmantabel中，而比较关键的是概率与这些编号是相对应的， 无论如何改变排序。例如，在对最小两个 概率对应数组删除时，都将新生成的元素放到最后（四）霍夫曼解码在进行霍夫曼解码的过程中， 需要将霍夫曼码序列中的元素与霍夫曼码表中的元素进行比较， 若一样则输出相对应的字符。由于考虑到霍夫曼码长可变，我们可以归纳每个霍夫曼码的特点， 每个霍夫曼码可以用其码长以及十进制数值唯一表示，将其十进制及码长存入一个新的元胞数组huffmandec 中，将霍夫曼码元中的一位位取出，算出其十进制对应的值tempsum 及二进制长度 i存入一个数组a中，使用语句 c2=find(cellfun(t)all(a(:)=t(:),huffmandec);即可找到元胞数组huffmandec 中与数组 a相同的数组的位置。利用这个次序即可找到对应的huffmanletters 数组中的字符删除后的数组重新赋值给huffmanletter- s ，将这个字符存入 decodeletters ，将刚刚统计的 i个二进制删除并用语句isequal(decodeletters,inputletters)判断解码输出的结果与输入是否相同。将二进制霍夫曼码表转变为十进制霍夫曼码表并与长度一起存入元胞数组的语句如下：for i=1:length(huffmanletters)temparray=huffmantabeli;%temparray是一个临时的矩阵huffmandeci=bin2dec(num2str(temparray),length(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)=0tempsum=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)=0decodeletters=decodeletters huffmanletters(c2(1);huffmancodep(1:i)=;break;endendendif isequal(decodeletters,inputletters)=1disp( 经比较解码输出结果与输入相同)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 编码并解码% 更改记录% dateprogrammerdescription of change% =% 5/11original code% 重要变量定义：%inputstring:输入字符串%inputletters:除去空格后的字符串存入的数组%huffmanletters:用来霍夫曼编码的字符集%huffmanprob:字符集相对应的概率%huffmantabel:霍夫曼码表，与字符集顺序对应%huffmancode:霍夫曼编码结果%decodeletters:霍夫曼解码输出的字符集%compratio:压缩比%-开始编码 -clcclear allinputstring=input(spacenumber=0;请输入需要编码的字符:,s);% 输入字符并存储% 存储空格数目%=去除空格=for i=1:length(inputstring)if abs(inputstring(i)=32spacenumber=spacenumber+1;continueelseinputletters(i-spacenumber)=inputstring(i);endenddisp( 去除空格后字符为：,char(inputletters)%fprintf( 去除空格后字符：%s,char(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;endendif repeatn=0letters(length(letters)+1)=inputletters(m);endend%disp( 输入无重复字符为：,char(letters)%=统计概率=for p=1:length(letters)repeatn=0;% 计算重复次数for q=1:length(inputletters)if letters(p)=inputletters(q)repeatn=repeatn+1;endendletterp(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)=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);numorder=num2cell(numorder_temp);% 将1-. 这一系列数转变为元胞数组while length(numorder)1temp,ind=sort(huffmanprob);% 排序，不需要结果，只需要最小概率在原概率中位置pminorder=numorderind(1);% 根据 ind 得出最小概率元胞数组对应位置，此位置对应编码字符pmin=huffmanprob(ind(1);pnminorder=numorderind(2);pnmin=huffmanprob(ind(2);for i=1:length(pminorder)huffmantabelpminorder(i)=1,huffmantabelpminorder(i);endfor j=1:length(pnminorder)huffmantabelpnminorder(j)=0,huffmantabelpnminorder(j);endnumorder(ind(1:2)=;numorderlength(numorder)+1=pminorder,pnminorder;huffmanprob(ind(1:2)=;huffmanprob(length(huffmanprob)+1)=pmin+pnmin;end%=输出霍夫曼码表=disp(-霍夫曼码表)for i=1:length(huffmanletters)%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;% 将十进制霍夫曼码组元胞数组元素变成十进