霍夫曼编码含源程序Word文档下载推荐.docx
《霍夫曼编码含源程序Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《霍夫曼编码含源程序Word文档下载推荐.docx（19页珍藏版）》请在冰点文库上搜索。
（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（'
）;
%输入字符并存储
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;
ifrepeatn==0
letters（length（letters）+1）=inputletters（m）;
概率的统计即是统计letters中每个元素在inputletters出现的次数，除以总次数即可得到每个字符出现的概率。
概率统计的程序如下：
forp=1:
length（letters）
%计算重复次数
forq=1:
ifletters（p）==inputletters（q）
letterp（p）=repeatn/length（inputletters）;
对得到概率letterp进行降序排序得到huffmanprob，并使字符集与概率相对应生成字符集huffamnletters。
这一过程主要是为了方便输出字符集的输出。
[huffmanprob,sort_index]=sort（letterp）;
%用来霍夫曼编码的概率
huffmanprob=（fliplr（huffmanprob））'
;
sort_index=fliplr（sort_index）;
length（huffmanprob）
huffmanletters（i）=letters（sort_index（i））;
%用来霍夫曼编码的字符集
disp（'
----------------------------字符及概率-------------------------------'
）
fori=1:
length（huffmanletters）
fprintf（'
字符：
%-4s概率：
%5.4f\n'
char（huffmanletters（i））,huffmanprob（i））
（三）霍夫曼编码
根据实验原理，在使用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）}];
forj=1:
length（pnminorder）
huffmantabel{pnminorder（j）}=[0,huffmantabel{pnminorder（j）}];
numorder（ind（1:
2））=[];
numorder{length（numorder）+1}=[pminorder,pnminorder];
huffmanprob（ind（1:
huffmanprob（length（huffmanprob）+1）=pmin+pnmin;
（四）霍夫曼解码
在进行霍夫曼解码的过程中，需要将霍夫曼码序列中的元素与霍夫曼码表中的元素进行比较，若一样则输出相对应的字符。
由于考虑到霍夫曼码长可变，我们可以归纳每个霍夫曼码的特点，每个霍夫曼码可以用其码长以及十进制数值唯一表示，将其十进制及码长存入一个新的元胞数组huffmandec中，将霍夫曼码元中的一位位取出，算出其十进制对应的值tempsum及二进制长度i存入一个数组A中，使用语句c2=find（cellfun（@（t）all（A（:
）==t（:
））,huffmandec））;
即可找到元胞数组huffmandec中与数组A相同的数组的位置。
利用这个次序即可找到对应的huffmanletters数组中的字符删除后的数组重新赋值给huffmanletter-s，将这个字符存入decodeletters，将刚刚统计的i个二进制删除并用语句isequal（decodeletters,inputletters）判断解码输出的结果与输入是否相同。
将二进制霍夫曼码表转变为十进制霍夫曼码表并与长度一起存入元胞数组的语句如下：
temparray=huffmantabel{i};
%temparray是一个临时的矩阵
huffmandec{i}=[bin2dec（num2str（temparray））,length（temparray）];
%用霍夫曼码表的十进制值及长度形成霍夫曼码的唯一标志
实现霍夫曼解码的流程图如下：
这一过程所对应的Matlab源程序为：
decodeletters=[];
whileisempty（huffmancodep）==0
tempsum=0;
length（huffmancodep）
tempsum=tempsum*2+huffmancodep（i）;
A=[tempsumi];
c2=find（cellfun（@（t）all（A（:
ifisempty（c2）==0
decodeletters=[decodelettershuffmanletters（c2
（1））];
huffmancodep（1:
i）=[];
break;
ifisequal（decodeletters,inputletters）==1
disp（'
经比较解码输出结果与输入相同'
在完成霍夫曼解码之后经过简单的计算即可求出信源熵，压缩比，以及平均码长。
五、结果演示
以书本例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
spacenumber=0;
%================================去除空格==================================
%fprintf（'
去除空格后字符：
%s'
char（letters））
%==========================统计输入字符种类=================================
%disp（['
输入无重复字符为：
char（letters）]）
%=============================统计概率=====================================
%=============================排序并对应===================================
%============================输出字符及概率================================
%============================开始霍夫曼编码================================
huffmantabel=cell（1,length（huffmanletters））;
%定义元胞数组用来存储huffman码表
numorder_temp=1:
length（huffmanletters）;
numorder=num2cell（numorder_temp）;
%将1-...这一系列数转变为元胞数组
%排序，不需要结果，只需要最小概率在原概率中位置
%根据ind得出最小概率元胞数组对应位置，此位置对应编码字符
%==============================输出霍夫曼码表===============================
----------------------------霍夫曼码表-------------------------------'
length（huffmanletters）
%fprintf（'
%f\n'
char（huffmanletters（i））,num2str（huffmantabel{i}））
disp（['
字母：
char（huffmanletters（i））'
'
霍夫曼码：
num2str（huffmantabel{i}）]）
%==============================形成霍夫曼码================================
------------------------------霍夫曼码-------------------------------'
huffmancode=[];
%huffmancode用来存储huffman码
c1=find（huffmanletters==inputletters（i））;
huffmancode=[huffmancode,huffmantabel{c1
（1）}];
ceil（length（huffmancode）/10）
disp（num2str（huffmancode（（i-1）*20+1:
min（i*20,length（huffmancode）））））
%==============================霍夫曼解码================================
huffmancodep=huffmancode;
%将十进制霍夫曼码组元胞数组元素变成十进制数组方便解码
%开始解码
------------------------------霍夫曼解码-------------------------------'
disp（char（decodeletters））
%判断解码结果与输入是否相同
%==============================计算压缩比================================
------------------------------压缩比-------------------------------'
bitsone=ceil（log2（length（huffmanletters）））;
%一个字符需要用几位二进制表示
bitsrequired=length（inputletters）*bitsone;
%理论上需要的总二进制位数
bitsactual=length（huffmancode）;
%huffman编码用到的二进制位数
compratio=bitsrequired/bitsactual;
%压缩比
fprintf（'
压缩比：
compratio）
升级会员 