霍夫曼编码(含源程序)

多媒体技术根底实验报告

——霍夫曼编码

学院：电子工程与光电技术学院

专业：电子信息工程

某某：

学号：

任课教师：康其桔

1 / 21

word 实验时间：

一、实验内容与要求

1、使用Matlab编程实现霍夫曼编码

2、通过键盘输入字符串 3、在屏幕上显示编码结果

二、实验原理

霍夫曼编码是霍夫曼在1952年提出和描述的“从下到上〞的熵编码方法。根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少。其根本步骤为： (1) 将压缩的各字符的出现概率按减少(或增加)的顺序进展排列。

(2) 将两个最小的概率进展组合相加得到一个新概率将这一新概率与其它概率一起继续执行1 和2 的操作直至最后概率为1.0。 (3) 对每对组合中的概率较大者指定为1,较小者指定为0。 (4) 画出由每个信源符号概率到处的路径记下路径的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)。霍夫曼编码的过程如

1

B:11 2 / 21 1

A:10 E:00

word 下： B(10/30) A(8/30) E(5/30) D(4/30)

0

C(3/30)

1 0 0

1 7/30 12/30

18/30 0

30/30 霍夫曼编码后平均码长为2(10/308/305/30)3(4/303/30)2.23b 。而信源熵H2.19b。由此，我们可以看出，霍夫曼编码结果已经很接近理想信源熵。

三、设计方案

设计的流程图如下： 统计字符种类与概率

霍夫曼编码 霍夫曼解码 读入字符串并去除空格 四、各模块设计

〔一〕读入字符串并去除空格

在Matalb中使用语句inputstring=input('请输入需要编码的字符:','s')，输入的字

符串存入char型数组inputstring中。 去除空格的思想为：

输出数组inputletters 3 / 21 word

i>length(inputletters)?

i=i+1 判断数组inputstring的第i个字符 i=i+1，spacenumber= spacenumber+1 是空格？ 是 否

inputletters(i-spacenumber)=inputstring(i);

输出的inputletters数组存储的是输入字符串去除空格后的字符集的ASCII值，如果需要显示字符需要用语句：disp(char(inputletters))。这一局部代码如下：

inputstring=input('请输入需要编码的字符:','s');%输入字符并存储

4 / 21

word spacenumber=0; %存储空格数目 for i=1:length(inputstring) if abs(inputstring(i))==32 spacenumber=spacenumber+1; continue else

inputletters(i-spacenumber)=inputstring(i); end end

disp(['去除空格后字符为：',char(inputletters)])

〔二〕统计字符种类与概率

统计字符的种类，需要去除输入字符中的重复字符，并存入数组letters中，其根本流程图如下：

letters(1)=inputletters(1) 从第m个元素判断是否是letters中元

m=m+1 是 素 否 letters(length(letters)+1) =inputletters(m) 5 / 21

word

输出矩阵letters m>length(inputletters)? 这一局部的程序如下：

letters(1)=inputletters(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); end end

概率的统计即是统计letters中每个元素在inputletters出现的次数，除以总次数即可得到每个字符出现的概率。概率统计的程序如下：

for p=1:length(letters)

6 / 21

word repeatn=0; %计算重复次数 for q=1:length(inputletters) if letters(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); for i=1:length(huffmanprob)

huffmanletters(i)=letters(sort_index(i)); %用来霍夫曼编码的字符集 end

disp('----------------------------字符与概率-------------------------------') for i= 1:length(huffmanletters)

fprintf(\\n',char(huffmanletters(i)),huffmanprob(i)) end

〔三〕霍夫曼编码

根据实验原理，在使用Matlab编程实现霍夫曼编码的过程中，需要定义一个元胞数组huffmantabel来存储霍夫曼码表。这个元胞数组的长度与huffman -letters中字符相对应。同时还需定义一个元胞数组numorder来存储每个字符的概率在原概率矩阵中的位置。其根本流程图如下：

7 / 21

word

while length(numorder)>1

[temp,ind]=sort(huffmanprob);

pminorder=numorder{ind(1)}; pmin=huffmanprob(ind(1)); pnminorder=numorder{ind(2)}; pnmin=huffmanprob(ind(2)); for i=1:length(pminorder)

huffmantabel{pminorder(i)}=[1,huffmantabel{pminorder(i)}]; end

for j=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

8 / 21

numorder的长度是否大于1 否 输出huffmantabel

word

将最小概率对应numorder中的

9 / 21

将最小概率对应huffmapro中的两个数相加，放到数组最后，并

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

是

word 〔四〕霍夫曼解码

在进展霍夫曼解码的过程中，需要将霍夫曼码序列中的元素与霍夫曼码表中的元素进展比拟，假如一样如此输出相对应的字符。由于考虑到霍夫曼码长可变，我们可以归纳每个霍夫曼码的特点，每个霍夫曼码可以用其码长以与十进制数值唯一表示，将其十进制与码长存入一个新的元胞数组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=huffmantabel{i}; %temparray是一个临时的矩阵 huffmandec{i}=[bin2dec(num2str(temparray)),length(temparray)]; %用霍夫曼码表的十进制值与长度形成霍夫曼码的唯一标志 end

实现霍夫曼解码的流程图如下：

10 / 21 huffmancodep是否为空，i=0 是

输出解码结果decode

-letters

word

i=i+1

将A对应huffmantabel中位置所对应的

11 / 21

字符存入decodeletters，删除huffmancode中的前i个字符

有

元胞数组huffmantabel中是否有A？ 没有 计算前i个二进制数对应的十进制数，并形成矩阵A 输入huffmancodep的第i个字符 否

word

这一过程所对应的Matlab源程序为：

decodeletters=[];

while isempty(huffmancodep)==0 tempsum=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 end end

if isequal(decodeletters,inputletters)==1 disp('经比拟解码输出结果与输入一样') end

在完成霍夫曼解码之后经过简单的计算即可求出信源熵，压缩比，以与平均码长。

五、结果演示

以书本例2.2为例，运行程序，输入A〔15个〕、B〔7个〕、C〔6个〕、D〔6个〕、E〔5个〕，理论结果为

12 / 21

word A〔0〕 B〔1 1 1〕

C〔1 1 0〕 D〔101〕 E〔1 0 0〕 压缩比为： 信源熵为2.1857 平均码长为：

而经过程序计算的结果为： 13 / 21

word

经比拟，所得结果与例2.2结果一样，即程序运行结果正确

六、源程序

%目的：从键盘输入字符集使用huffman编码并解码 % % 更改记录

% Date Programmer Description of change % ==== ========= ================ % 5/11 Original code %

%重要变量定义：

14 / 21

word %inputstring:输入字符串

%inputletters:除去空格后的字符串存入的数组 %huffmanletters:用来霍夫曼编码的字符集 %huffmanprob:字符集相对应的概率

%huffmantabel:霍夫曼码表，与字符集顺序对应 %huffmancode:霍夫曼编码结果

%decodeletters:霍夫曼解码输出的字符集 %pratio:压缩比

%--------------------------------开始编码---------------------------------

clc clear all

inputstring=input('请输入需要编码的字符:','s');%输入字符并存储 spacenumber=0; %存储空格数目

%================================去除空格==================================

for i=1:length(inputstring) if abs(inputstring(i))==32 spacenumber=spacenumber+1; continue else

inputletters(i-spacenumber)=inputstring(i); end end

15 / 21

word disp(['去除空格后字符为：',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; end end

if repeatn==0

letters(length(letters)+1)=inputletters(m); end end

%disp(['输入无重复字符为：',char(letters)])

%=============================统计概率=====================================

for p=1:length(letters)

repeatn=0; %计算重复次数 for q=1:length(inputletters) if letters(p)==inputletters(q)

16 / 21

word 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)=letters(sort_index(i)); %用来霍夫曼编码的字符集 end

%============================输出字符与概率================================

disp('----------------------------字符与概率-------------------------------') for i= 1:length(huffmanletters)

fprintf(\\n',char(huffmanletters(i)),huffmanprob(i)) end

%============================开始霍夫曼编码================================

huffmantabel=cell(1,length(huffmanletters)); %定义元胞数组用来存储huffman码表

17 / 21

word numorder_temp=1:length(huffmanletters);

numorder=num2cell(numorder_temp); %将1-...这一系列数转变为元胞数组 while length(numorder)>1

[temp,ind]=sort(huffmanprob); %排序，不需要结果，只需要最小概率在原概率中位置

pminorder=numorder{ind(1)}; %根据ind得出最小概率元胞数组对应位置，此位置对应编码字符 pmin=huffmanprob(ind(1)); pnminorder=numorder{ind(2)}; pnmin=huffmanprob(ind(2)); for i=1:length(pminorder)

huffmantabel{pminorder(i)}=[1,huffmantabel{pminorder(i)}]; end

for j=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('----------------------------霍夫曼码表-------------------------------') for i=1:length(huffma nletters)

18 / 21

word %fprintf('字符：%-4s概率：%f\\n',char(huffmanletters(i)),num2str(huffmantabel{i})) disp(['字母：' char(huffmanletters(i)) ' ''霍夫曼码：' num2str(huffmantabel{i})]) end

%==============================形成霍夫曼码================================

disp('------------------------------霍夫曼码-------------------------------') huffmancode=[]; %huffmancode用来存储huffman码 for i=1:length(inputletters)

c1=find(huffmanletters==inputletters(i)); huffmancode=[huffmancode,huffmantabel{c1(1)}];

end

for i=1:ceil(length(huffmancode)/10)

disp(num2str(huffmancode((i-1)*20+1:min(i*20,length(huffmancode))))) end

%==============================霍夫曼解码================================

huffmancodep=huffmancode;

%将十进制霍夫曼码组元胞数组元素变成十进制数组方便解码 for i=1:length(huffmanletters)

temparray=huffmantabel{i}; %temparray是一个临时的矩阵 huffmandec{i}=[bin2dec(num2str(temparray)),length(temparray)]; %用霍夫曼码表的十进制值与长度形成霍夫曼码的唯一标志

19 / 21

word end %开始解码 decodeletters=[];

while isempty(huffmancodep)==0 tempsum=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 end end

disp('------------------------------霍夫曼解码-------------------------------') disp(char(decodeletters)) %判断解码结果与输入是否一样

if isequal(decodeletters,inputletters)==1 disp('经比拟解码输出结果与输入一样') end

%==============================计算压缩比================================

20 / 21

word disp('------------------------------压缩比-------------------------------') bitsone=ceil(log2(length(huffmanletters)));%一个字符需要用几位二进制表示 bitsrequired=length(inputletters)*bitsone; %理论上需要的总二进制位数 bitsactual=length(huffmancode); %huffman编码用到的二进制位数 pratio=bitsrequired/bitsactual; %压缩比 fprintf(\\n',pratio)

21 / 21