哈夫曼编码的MATLAB实现
- 格式：pdf
- 大小：77.63 KB
- 文档页数：2
哈夫曼编码的MATLAB实现
本代码灵感来⾃于百度上某篇使⽤sort()函数实现哈夫曼编码的⽂章，原⽂过于复杂。于是本⼈按照逻辑重写过程得到下述代码，可谓思路清晰，⽅法简洁。由于试验的量也不是很⼤，所以性能或许不好？嗯……管他的呢
唯⼀难读的地⽅在于MAP函数的补全部分，但其实和哈夫曼编码最后⾃顶向下得到编码的过程逻辑⼀致。
sort()函数是MATLAB中⽐较⽅便的⼀个排序函数。
[A,B]=sort(C)，其中C为乱序概率序列，可得：
1.A为C的升序序列
2.B为A对应数字在C中的原始位置
（1）由 A 我们可以得到C序列中 最⼩值 和 次⼩值 ，⽤于哈夫曼编码中最⼩值和次⼩值相加。
（2）由 B 可以知道两个值在原始序列中的位置，⽤于记录本次加法对应的“ 0 ”和“ 1 ”。
那么我们可以把它记录下来作为哈夫曼编码中加法合并的路径，记作MAP矩阵。
合并后的序列在原序列的基础上⽣成，两项的和统⼀赋值给较⼤值，较⼩值则赋⼀个⽤不到的极⼤值即可，此处⽤5。
[0.2 0.19 0.17 0.18 0.15 0.01 0.1]
--->[0.2 0.19 0.17 0.18 0.15 5 0.11]
反复操作后，即依次合并最⼩两项，得到合成的全路线如下：
补全所有的值后得到完整的MAP，倒着输出就可以
下⾯贴上完整的代码。
clc;clear;
p=[0.2 0.19 0.17 0.18 0.15 0.01 0.1];
n=length(p);
List=p;
Op_List=p;
Map=[];%Map⽤于进⾏huffman 编码,下⾯⽣成(n-1)*(n*n)的矩阵
for i=1:n-1
Map=[Map;blanks(n)];
end
for i=1:n-1
[Op_List,e]=sort(Op_List);% e 记录了原来的顺序
%e(1)e(2)就是合并的两个数,⼩的赋1⼤的赋0
Map(i,e(1))='1';
Map(i,e(2))='0';
%第⼀第⼆加到第⼆个，第⼀个作废
Op_List(2)=Op_List(1)+Op_List(2);
Op_List(1)=n;
%位置还原
Back_List=zeros(1,n);
for j=1:n
Back_List(e(j))=Op_List(j);
end
Op_List= Back_List;
end
x=n;y=n-1;%补全Map
for i=y:-1:1
for j=1:x
if Map(i,j)~=' '
for k=i-1:-1:1
if Map(k,j)~=' '
for b=1:x
if b~=j && Map(k,b)~=' '
Map(k+1:y,b)=Map(k+1:y,j);
end
end
end
end
end
end
end
Map%输出
for j=1:n
fprintf(' 概率：%.2f',p(j));
fprintf(' 哈夫曼编码： ');
for i=y:-1:1
if Map(i,j)~=' '
fprintf('%c',Map(i,j));
end
end
fprintf('\n');
end
