huffman编码的matlab实现.doc

(完整)huffman编码的matlab实现
Huffman编码的matlab实现

一、信源编码介绍
为了减少信源输出符号序列中的剩余度、提高符号的平均信息量，对所施行的变换。具体说，就是针对信源输出符号序列的统计特性来寻找某种方法,把信源输出符号序列变换为最短的码字序列,使后者的各码元所载荷的平均信息量最大，同时又能保证无失真地恢复原来的符号序列。
既然信源编码的基本目的是提高码字序列中码元的平均信息量,那么，一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理,都可以在这种意义下归入信源编码的范畴，例如过滤、预测、域变换和数据压缩等。当然，这些都是广义的信源编码。
一般来说，减少信源输出符号序列中的剩余度、提高符号平均信息量的基本途径有两个：①使序列中的各个符号尽可能地互相独立;②使序列中各个符号的出现概率尽可能地相等.前者称为解除相关性，后者称为概率均匀化。
信源编码的一般问题可以表述如下：
信源编码
若某信源的输出为长度等于M的符号序列集合 式中符号A为信源符号表，它包含着K个不同的符号，A={ɑk｜k=1,…,K｝，这个信源至多可以输出KM个不同的符号序列。记‖U‖=KM。所谓对这个信源的输出
信源编码
进行编码,就是用一个新的符号表B的符号序列集合V来表示信源输出的符号序列集合U.若V的各个序列的长度等于 N，即 式中新的符号表B共含L个符号,B=｛bl｜l=1，…，L｝.它总共可以编出LN个不同的码字.类似地,记‖V‖=LN。为了使信源的每个输出符号序列都能分配到一个独特的码字与之对应，至少应满足关系 ‖V‖=LN≥‖U‖=KM或者 N/M≥logK/logL
下面的几个编码定理，提供了解决这个矛盾的方法。它们既能改善信息载荷效率，又能保证码字唯一可译。
离散无记忆信源的定长编码定理
对于任意给定的ε>0，只要满足条件 N/M≥(H（U)+ε)/logL
那么，当M足够大时,上述编码几乎没有失真；反之，若这个条件不满足,就不可能实现无失真的编码。式中H(U)是信源输出序列的符号熵.
信源编码
通常，信源的符号熵H(U）<logK，因此，上述条件还可以表示为 【H(U)+ε】/logL≤N/M≤logK/logL特别，若有K=L，那么,只要H(U)〈logK，就可能有N〈M,从而提高信息载荷的效率.由上面这个条件可以看出，H（U）离logK越远，通过编码所能获得的效率改善就越显著。实质上，定长编码方法提高信息载荷能力的关键是利用了渐近等分性,通过选择足够大的M，把本来各个符号概率不等［因而H（U)<logK］的信源输出符号序列变换为概率均匀的典型序列，而码字的唯一可译性则由码字的定长性来解决。
离散无记忆信源的变长编码定理
变长编码是指V的各个码字的长度不相等.只要V中各个码字的长度 Ni（i=1，…，‖V‖)满足克拉夫特不等式 这 ‖V‖个码字就能唯一地正确划分和译码。离散无记忆信源的变长编码定理指出：若离散无记忆信源的输出符号序列为， 式中 A=｛ɑk|k=1，…，K｝,符号熵为H(U),对U进行唯一可译的变长编码，编码字母表B的符号数为L,即B=｛bl|l=1,…,L｝，那么必定存在一种编码方法,使编出的码字Vi=(vi1,…,viNi），(i=1,…,‖V‖），具有平均长度嚻: MH(U)/logL≤嚻〈MH(U）/logL+1
若L=K，则当H（U)<logK=logL时,必有嚻<M；H（U）离logK越远，则嚻越小于M。
具体实现唯一可译变长编码的方法很多，但比较经典的方法还是仙农编码法、费诺编码法和霍夫曼编码法。其他方法都是这些经典方法的变形和发展。所有这些经典编码方法,都是通过以短码来表示常出现的符号这个原则来实现概率的均匀化，从而得到高的信息载荷效率;同时,通过遵守克拉夫特不等式关系来实现码字的唯一可译。
以上几个编码定理，在有记忆信源或连续信源的情形也有相应的类似结果.在实际工程应用中，往往并不追求无差错的信源编码和译码，而是事先规定一个译码差错率的容许值，只要实际的译码差错率不超过这个容许值即认为满意（见信息率—失真理论和多用户信源编码)。
二、 Huffman编码
霍夫曼编码方法的具体过程是：首先把信源的各个输出符号序列按概率递降的顺序排列起来，求其中概率最小的两个序列的概率之和，并把这个概率之和看作是一个符号序列的概率,再与其他序列依概率递降顺序排列(参与求概率之和的这两个序列不再出现在新的排列之中)，然后，对参与概率求和的两个符号序列分别赋予二进制数字0和1。继续这样的操作,直到剩下一个以1为概率的符号序列.最后，按照与编码过程相反的顺序读出各个符号序列所对应的二进制数字组,就可分别得到各该符号序列的码字。
三、 Huffman编码的Matlab源程序
1、 Huffman源程序
p=input（’please input a number:') ％提示输入界面
n=length(p）；
for i=1:n
if p（i)<0
fprintf（’\n The probabilities in huffman can not less than 0！\n');
p=input（’please input a number：’） %如果输入的概率数组中有小于0的值，则重新输入概率数组
end
end
if abs（sum（p)-1)〉0
fprintf（’\n The sum of the probabilities in huffman can more than 1!\n’)；
p=input（'please input a number：') ％如果输入的概率数组总和大于1，则重新输入概率数组
end
q=p;
a=zeros（n-1，n)； ％生成一个n-1行n列的数组
for i=1：n—1
［q,l］=sort(q） %对概率数组q进行从小至大的排序,并且用l数组返回一个数组，该数组表示概率数组q排序前的顺序编号
a（i，：）=［l（1：n-i+1）,zeros（1,i—1)］ ％由数组l构建一个矩阵,该矩阵表明概率合并时的顺序，用于后面的编码
q=[q(1)+q(2),q(3：n)，1］; ％将排序后的概率数组q的前两项，即概率最小的两个数加和，得到新的一组概率序列
end
for i=1：n-1
c(i，1：n*n）=blanks(n*n); ％生成一个n—1行n列，并且每个元素的的长度为n的空白数组，c矩阵用于进行huffman编码,并且在编码中与a矩阵有一定的对应关系
end
c（n—1，n）=’0’; ％由于a矩阵的第n—1行的前两个元素为进行huffman编码加和运算时所得的最
c（n-1,2*n)='1'; 后两个概率，因此其值为0或1，在编码时设第n—1行的第一个空白字符为0,第二个空白字符1.
for i=2：n—1
c（n-i，1:n-1）=c（n—i+1,n＊(find(a（n—i+1,：)==1)）-（n-2）：n*(find（a(n-i+1,：）==1）)) %矩阵c的第n-i的第一个元素的n—1的字符赋值为对应于a矩阵中第n—i+1行中值为1的位置在c矩阵中的编码值

c(n-i,n）='0’ ％根据之前的规则，在分支的第一个元素最后补0
c（n—i，n+1：2＊n—1）=c（n—i,1:n-1） %矩阵c的第n-i的第二个元素的n—1的字符与第n—i行的第一个元素的前n-1个符号相同，因为其根节点相同
c（n—i,2*n)=’1’ ％根据之前的规则，在分支的第一个元素最后补1
for j=1:i—1
c（n—i，(j+1)＊n+1：(j+2）*n)=c(n—i+1,n＊(find（a（n—i+1,：)==j+1）-1）+1:n*find(a(n-i+1，：)==j+1)） ％矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值
end
end ％完成huffman码字的分配
for i=1:n
h（i，1:n)=c（1，n*(find(a(1，：)==i)-1）+1：find（a(1,:)==i)*n） %用h表示最后的huffman编码，矩阵h的第i行的元素对应于矩阵c的第一行的第i个元素
ll（i）=length（find(abs（h（i,:））～=32）) ％计算每一个huffman编码的长度
end
l=sum（p.＊ll）； ％计算平均码长
fprintf(’\n huffman code：\n’)；
h
hh=sum（p。＊（-log2(p）)）; %计算信源熵
fprintf（’\n the huffman effciency：\n'）；
t=hh/l ％计算编码效率
2、程序运行结果
四、结论
Huffman编码的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的，就是说出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的.