通信仿真课实验报告
霍夫曼编码
老师：秦川
2010级通信工程1班
季平
1019620109
第一部分 Ⅰ.代码及JP层层解析:
closeall;clc;clear all;
%先输入5个符号出现的概率矩阵%
p=[8/30 10/30 3/30 4/30 5/30];
%判断p的矩阵中是否有概率不满足大于0的情况，不然出现错误提示%
if length(find(p
error('negative component(s)!');
end
%因为总概率应该为1，所以不满足时则出现错误提示% if sum(p)>1
error('Not a prob.vector,add to 1');
end
%满足概率均大于0及概率总和为1时，则输出p矩阵5个符号的概率的预备工作已经完成%
disp('Symbol probability of the source:');
%n为p矩阵的长度，又为其符号个数，为今后计算最少需要多少bits来表示n个符号%
n=length(p);
%运用for语句，依次输出5个符号的概率的长度%
fori=1:n
disp(['Prob(',char(64+i),')',':',num2str(p(i))]);
end
pause;
%计算5个符号的信息熵,并显示出来%
H=-sum(p.*log2(p));
disp(['ENtropy of the source:',num2str(H),'bits']);
%L0即为表示n个符号最少需要多少bits的值，ceil为向上取整，并予以显示%
L0=ceil(log2(n));
disp(['Average code length before Huffman encoding:',num2str(L0),'bits']);
pause;
%为了不使得原来的p矩阵产生变化，这里我们用了一个新的矩阵叫q来代替p矩阵%
q=p;
%生成一个n-1行*n列的全零矩阵m%
m=zeros(n-1,n);
%进行霍夫曼编码的运算%
fori=1:n-1
%将ｑ矩阵用sort函数从小到大进行排列生成新的q矩阵，其中L为从原来变换到新矩阵的新下标排序%
[q,L]=sort(q);
%m为n-1行n列的矩阵，其实相当于做了n-1个操作，使得每一步操作都有了存放，L矩阵由于经过每次编码后存在为了使他平衡的1不改变其原有的n-1*n的矩阵，所以将其与零矩阵合并%
m(i,:)=[L(1:n-i+1),zeros(1,i-1)];
%因为q已经进行过从小到大排序，而霍夫曼的算法可知，使得两个最小的概率相加行程一个新的矩阵，为了不使得计算产生左右不平衡，每当完成一次相加操作后，在矩阵后补一个1（因为其他概率都不会大于1的），这样做的好处是在将用sort函数时，矩阵中1的由于从小到大排列就将一直在矩阵的最右边，使得新矩阵能够满足原有矩阵长度%
q=[q(1)+q(2),q(3:n),1];
end
%blanks函数的作用是打出n*n个空格，c为(n-1)*(n*n)的空格方阵，意在每行存放5个最多为5bits的二进制数，其实就等于是个4*5个最多5bits的矩阵，因为m矩阵是一个下标矩阵，要将c矩阵来配合m矩阵用来反过去寻找霍夫曼编码%
fori=1:n-1
c(i,:)=blanks(n*n);
end
%现在开始反过来寻找原有的赫夫曼编码，需要对应着m矩阵来看，我们这样我们先看m矩阵 3 4 5 1 2
2 1 3 4 0
2 3 1 0 0
2 1 0 0 0，因为c中编码定义为将概率小的为0，
概率大的为1，第一步就是先将c中最后一行的第一个元素定位 0，第二个元素定为 1，我前面已经说过了，5个空格用来表达一个元素%
c(n-1,n)='0';
c(n-1,2*n)='1';
%开始用m矩阵来与c矩阵发生关系来反过去一层层反推霍夫曼编码%
for i=2:n-1
%寻找方式为依次从最后向前寻找，具体方法为，由于m矩阵为从小到大排列好矩阵的没排列前的下标矩阵，那么每行位于1位置的数必为上一行中第一列和第二列的数的和，于是由霍夫曼编码的特性，我们可以知道，那倒寻上去的时候，上一行第一列的数因为下面一行位于1位置的数后面+0（因为这个数相对于第一列第二列的数中较小的一个），而上一行第二列的数应为下面一行位于1位置的数后面+1（因为这个数相对于第一列第二列数中较大的一个），第一第二列即
为（10个空格）的数排好之后，剩下的(4-i)*5个bits的4-i个5bits的数就为下面一行不为1位置的数依次排列，这样一次寻找，如图所示
%
%从图上可以看到当寻找到排序为1的位置时将其定义的0或1以及其前面的空格全部复制到上一行的第一位置，当然要留出一个空格给，倒追上去的概率小的0%
c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)==1))-(n-2):n*(find(m(n-i+1,:)==1)));
%霍夫曼编码的定义是概率小的地方赋值为0，填在下一行复制上来的值的后面%
c(n-i,n)='0';
%同理从图上可以看到当寻找到排序为1的位置时将其定义的0或1以及其前面的空格全部复制到上一行的第二位置，当然要留出一个空格给，倒追上去的概率相对大的1% c(n-i,n+1:2*n-1)=c(n-i,1:n-1);
%霍夫曼编码的定义是概率的地方赋值为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(m(n-i+1,:)==j+1)-1)+1:n*find(m(n-i+1,:)==j+1));
end
end
%h函数为存放5个字符霍夫曼编码%
fori=1:n
%寻找方式为，运用m矩阵第一行存放的是从小到大后的原有下标位置，例如当i=1时，寻找的是字符A的霍夫曼编码，A的位置原来为1，而find来寻找1的位置，又c为每行总共有25个空格以5*5存放，5个霍夫曼编码，每个霍夫曼编码寄存在5个空格中，其中包括空格，如此依次寻找5个字符的霍夫曼编码%
h(i,1:n)=c(1,n*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*n);
%由于h矩阵中有空格字符，所以当要计算bit长度时，就除去空格位置将不为空格bit长度用L函数依次存放%
L1(i)=length(find(abs(h(i,:))~=32));
end
%一一显示最后霍夫曼编码的结果%
disp('Encoded results:');
fori=1:n
disp([char(64+i),':',h(i,:)]);
end
pause;
%因为L1为存放各个字符的bit数，再计算霍夫曼编码后的总bit数，并显示最后的结果%
L=sum(p.*L1);
disp(['Average code length after Huffman encoding:',num2str(L)]); pause;
%计算霍夫曼编码的压缩率L0/L，并显示结果%
disp(['Compressionratio=',num2str(L0),'/',num2str(L),'=',num2str(L0/L)]);
Ⅱ.运行结果如下：
Symbol probability of the source:
Prob(A):0.26667
Prob(B):0.33333
Prob(C):0.1
Prob(D):0.13333
Prob(E):0.16667
----------------------------------------------------------------------------------------------------------------- ENtropy of the source:2.1874bits
Average code length before Huffman encoding:3bits
----------------------------------------------------------------------------------------------------------------- Encoded results:
A: 10
B: 11
C: 010
D: 011
E: 00
----------------------------------------------------------------------------------------------------------------- Average code length after Huffman encoding:2.2333 Compression ratio=3/2.2333=1.3433
Ⅲ.分析优缺点及改进方案
上课老师写的这个程序虽然运行出来是正确无误的，但是个人觉得，程序不应该有他的局限性，第一部分在建立P的信源概率时，编码已经将其固定，只有特殊性，不具普遍性，第二部分倒寻找霍夫曼编码的过程也将予以改变。
第二部分
1. JP版霍夫曼编码
Ⅰ.代码之JP版:
closeall;clc;clearall;
String=input('Input String one by one:','s');
n=length(String);
S=reshape(str2mat(String),1,n);
s=zeros(1,94);
fori=1:n switch S(i) case ('!') s(1)=s(1)+1; case ('"') s(2)=s(2)+1; case ('#') s(3)=s(3)+1; case ('$') s(4)=s(4)+1; case ('%') s(5)=s(5)+1; case ('&') s(6)=s(6)+1; case (',') s(7)=s(7)+1; case ('(') s(8)=s(8)+1; case (')') s(9)=s(9)+1; case ('*') s(10)=s(10)+1; case ('+') s(11)=s(11)+1; case (',') s(12)=s(12)+1; case ('-') s(13)=s(13)+1; case ('.') s(14)=s(14)+1; case ('/') s(15)=s(15)+1; case ('0') s(16)=s(16)+1; case ('1') s(17)=s(17)+1;; case ('2') s(18)=s(18)+1; case ('3') s(19)=s(19)+1; case ('4') s(20)=s(20)+1; case ('5')
case ('6')
s(22)=s(22)+1;
case ('7')
s(23)=s(23)+1;
case ('8')
s(24)=s(24)+1;
case ('9')
s(25)=s(25)+1;
case (':')
s(26)=s(26)+1;
case (';')
s(27)=s(27)+1;
case ('
s(28)=s(28)+1;
case ('=')
s(29)=s(29)+1;
case ('>')
s(30)=s(30)+1;
case ('?')
s(31)=s(31)+1;
case('@')
s(32)=s(32)+1;
case ('A')
s(33)=s(33)+1;
case ('B')
s(34)=s(34)+1;
case ('C')
s(35)=s(35)+1;
case ('D')
s(36)=s(36)+1;
case('E')
s(37)=s(37)+1;
case ('F')
s(38)=s(38)+1;
case ('G')
s(39)=s(39)+1;
case ('H')
s(40)=s(40)+1;
case ('I')
s(41)=s(41)+1;
case ('J')
s(42)=s(42)+1;
case ('K')
case ('L')
s(44)=s(44)+1;
case ('M')
s(45)=s(45)+1;
case ('N')
s(46)=s(46)+1;
case ('O')
s(47)=s(47)+1;
case ('P')
s(48)=s(48)+1;
case ('Q')
s(49)=s(49)+1;
case ('R')
s(50)=s(50)+1;
case ('S')
s(51)=s(51)+1;
case ('T')
s(52)=s(52)+1;
case ('U')
s(53)=s(53)+1;
case ('V')
s(54)=s(54)+1;
case ('W')
s(55)=s(55)+1;
case ('X')
s(56)=s(56)+1;
case ('Y')
s(57)=s(57)+1;
case ('Z')
s(58)=s(58)+1;
case ('[')
s(59)=s(59)+1;
case ('/')
s(60)=s(60)+1;
case (']')
s(61)=s(61)+1;
case ('^')
s(62)=s(62)+1;
case ('_')
s(63)=s(63)+1;
case ('`')
s(64)=s(64)+1;
case ('a')
case ('b')
s(66)=s(66)+1;
case ('c')
s(67)=s(67)+1;
case ('d')
s(68)=s(68)+1;
case ('e')
s(69)=s(69)+1;
case ('f')
s(70)=s(70)+1;
case ('g')
s(71)=s(71)+1;
case ('h')
s(72)=s(72)+1;
case ('i')
s(73)=s(73)+1;
case ('j')
s(74)=s(74)+1;
case ('k')
s(75)=s(75)+1;
case ('l')
s(76)=s(76)+1;
case ('m')
s(77)=s(707)+1;
case ('n')
s(78)=s(78)+1;
case ('o')
s(79)=s(79)+1;
case ('p')
s(80)=s(80)+1;
case ('q')
s(81)=s(81)+1;
case ('r')
s(82)=s(82)+1;
case ('s')
s(83)=s(83)+1;
case ('t')
s(84)=s(84)+1;
case ('u')
s(85)=s(85)+1;
case ('v')
s(86)=s(86)+1;
case ('w')
case ('x')
s(88)=s(88)+1;
case ('y')
s(89)=s(89)+1;
case ('z')
s(90)=s(90)+1;
case ('{')
s(91)=s(91)+1;
case ('|')
s(92)=s(92)+1;
case ('}')
s(93)=s(93)+1;
case ('~')
s(94)=s(94)+1;
end
end
countrank=find(s~=0);
N=length(countrank);
s0=s;
s0(:,find(s
Totalsymbol=sum(s0);
P=s/Totalsymbol;
p=s0/Totalsymbol;
if length(find(p
error('Error:Input number in p
end
disp(['Pay attention!U input ',num2str(N),' Symbols']);
fori=countrank
disp(['The number of ',char(i+32),' is',num2str(s(i)),' The Symbol probability of ',char(i+32),' :',num2str(P(i))]);
end
pause;
H=sum(-p.*log2(p));
disp(['ENtropy of the source:',num2str(H),'bits']);
L0=ceil(log2(N));
disp(['Average code length before Huffman
encoding:',num2str(L0),'bits']);
pause;
q=p;
rank=zeros(N-1,N);
fori=1:N-1
[q,L]=sort(q);
rank(i,:)=[L(1:N+1-i),zeros(1,i-1)];
q=[q(1)+q(2),q(3:N),1];
end
fori=1:N-1
hufftree(i,:)=blanks(N*N);
end
hufftree(N-1,N)='0';
hufftree(N-1,2*N)='1';
fori=2:N-1
hufftree(N-i,1:N-1)=hufftree(N-i+1,N*(find(rank(N-i+1,:)==1))-(N-2):N*(find(rank(N-i+1,:)==1)));
hufftree(N-i,N)='0';
hufftree(N-i,N+1:2*N-1)=hufftree(N-i,1:N-1);
hufftree(N-i,2*N)='1';
for j=1:i-1
hufftree(N-i,(j+1)*N+1:(j+2)*N)=hufftree(N-i+1,N*(find(rank(N-i+1,:)==j+1)-1)+1:N*find(rank(N-i+1,:)==j+1));
end
end
fori=1:N
huffman(i,1:N)=hufftree(1,N*(find(rank(1,:)==i)-1)+1:find(rank(1,:)==i)*N);
L1(i)=length(find(abs(huffman(i,:))~=32));
end
disp('Encoded results:');
fori=countrank
disp(['The symbol probability ',char(i+32),' of huffman one by one']); end
for k=1:N
disp([huffman(k,:)]);
end
pause;
L=sum(p.*L1);
disp(['Average code length after Huffman encoding:',num2str(L)]);
pause;
disp(['Compression
ratio=',num2str(L0),'/',num2str(L),'=',num2str(L0/L)]);
Ⅱ.运行结果如下：
Input String one by one:aaqqqqqqqwwwwweeeee@#$$$$
----------------------------------------------------------------------------------------------------------------- Pay attention!U input 7 Symbols
The number of # is1 The Symbol probability of # :0.04
The number of $ is4 The Symbol probability of $ :0.16
The number of @ is1 The Symbol probability of @ :0.04
The number of a is2 The Symbol probability of a :0.08
The number of e is5 The Symbol probability of e :0.2
The number of q is7 The Symbol probability of q :0.28
The number of w is5 The Symbol probability of w :0.2
----------------------------------------------------------------------------------------------------------------- ENtropy of the source:2.529bits
Average code length before Huffman encoding:3bits
----------------------------------------------------------------------------------------------------------------- Encoded results:
The symbol probability # of huffman one by one
The symbol probability $ of huffman one by one
The symbol probability @ of huffman one by one
The symbol probability a of huffman one by one
The symbol probability e of huffman one by one
The symbol probability q of huffman one by one
The symbol probability w of huffman one by one
11000
111
11001
1101
00
10
01
----------------------------------------------------------------------------------------------------------------- Average code length after Huffman encoding:2.56
Compression ratio=3/2.56=1.1719
-----------------------------------------------------------------------------------------------------------------
第三部分
经过这次自己编写霍夫曼编码，我对于整个压缩过程有了一个初步了解，在整个学习过程中，要将一个直观的问题变为一个程序为之所用一直是一个不简单的地方，让我认识到计算机与数学两者是一个不可分割的，相辅相成。虽然我认为在matlab中for语句的效率不高，并且我也想跳过for语句循环结构，但是最终还是选择了for语句。
对于matlab仿真，我一直都非常感兴趣，如何将实际问题归为一个编程问题虽然不简单，但是非常有趣，如何把一个复杂低效率的程序改为一个高效率简单化的程序才是我们学习的最终目的。
通信仿真课实验报告
霍夫曼编码
老师：秦川
2010级通信工程1班
季平
1019620109
第一部分 Ⅰ.代码及JP层层解析:
closeall;clc;clear all;
%先输入5个符号出现的概率矩阵%
p=[8/30 10/30 3/30 4/30 5/30];
%判断p的矩阵中是否有概率不满足大于0的情况，不然出现错误提示%
if length(find(p
error('negative component(s)!');
end
%因为总概率应该为1，所以不满足时则出现错误提示% if sum(p)>1
error('Not a prob.vector,add to 1');
end
%满足概率均大于0及概率总和为1时，则输出p矩阵5个符号的概率的预备工作已经完成%
disp('Symbol probability of the source:');
%n为p矩阵的长度，又为其符号个数，为今后计算最少需要多少bits来表示n个符号%
n=length(p);
%运用for语句，依次输出5个符号的概率的长度%
fori=1:n
disp(['Prob(',char(64+i),')',':',num2str(p(i))]);
end
pause;
%计算5个符号的信息熵,并显示出来%
H=-sum(p.*log2(p));
disp(['ENtropy of the source:',num2str(H),'bits']);
%L0即为表示n个符号最少需要多少bits的值，ceil为向上取整，并予以显示%
L0=ceil(log2(n));
disp(['Average code length before Huffman encoding:',num2str(L0),'bits']);
pause;
%为了不使得原来的p矩阵产生变化，这里我们用了一个新的矩阵叫q来代替p矩阵%
q=p;
%生成一个n-1行*n列的全零矩阵m%
m=zeros(n-1,n);
%进行霍夫曼编码的运算%
fori=1:n-1
%将ｑ矩阵用sort函数从小到大进行排列生成新的q矩阵，其中L为从原来变换到新矩阵的新下标排序%
[q,L]=sort(q);
%m为n-1行n列的矩阵，其实相当于做了n-1个操作，使得每一步操作都有了存放，L矩阵由于经过每次编码后存在为了使他平衡的1不改变其原有的n-1*n的矩阵，所以将其与零矩阵合并%
m(i,:)=[L(1:n-i+1),zeros(1,i-1)];
%因为q已经进行过从小到大排序，而霍夫曼的算法可知，使得两个最小的概率相加行程一个新的矩阵，为了不使得计算产生左右不平衡，每当完成一次相加操作后，在矩阵后补一个1（因为其他概率都不会大于1的），这样做的好处是在将用sort函数时，矩阵中1的由于从小到大排列就将一直在矩阵的最右边，使得新矩阵能够满足原有矩阵长度%
q=[q(1)+q(2),q(3:n),1];
end
%blanks函数的作用是打出n*n个空格，c为(n-1)*(n*n)的空格方阵，意在每行存放5个最多为5bits的二进制数，其实就等于是个4*5个最多5bits的矩阵，因为m矩阵是一个下标矩阵，要将c矩阵来配合m矩阵用来反过去寻找霍夫曼编码%
fori=1:n-1
c(i,:)=blanks(n*n);
end
%现在开始反过来寻找原有的赫夫曼编码，需要对应着m矩阵来看，我们这样我们先看m矩阵 3 4 5 1 2
2 1 3 4 0
2 3 1 0 0
2 1 0 0 0，因为c中编码定义为将概率小的为0，
概率大的为1，第一步就是先将c中最后一行的第一个元素定位 0，第二个元素定为 1，我前面已经说过了，5个空格用来表达一个元素%
c(n-1,n)='0';
c(n-1,2*n)='1';
%开始用m矩阵来与c矩阵发生关系来反过去一层层反推霍夫曼编码%
for i=2:n-1
%寻找方式为依次从最后向前寻找，具体方法为，由于m矩阵为从小到大排列好矩阵的没排列前的下标矩阵，那么每行位于1位置的数必为上一行中第一列和第二列的数的和，于是由霍夫曼编码的特性，我们可以知道，那倒寻上去的时候，上一行第一列的数因为下面一行位于1位置的数后面+0（因为这个数相对于第一列第二列的数中较小的一个），而上一行第二列的数应为下面一行位于1位置的数后面+1（因为这个数相对于第一列第二列数中较大的一个），第一第二列即
为（10个空格）的数排好之后，剩下的(4-i)*5个bits的4-i个5bits的数就为下面一行不为1位置的数依次排列，这样一次寻找，如图所示
%
%从图上可以看到当寻找到排序为1的位置时将其定义的0或1以及其前面的空格全部复制到上一行的第一位置，当然要留出一个空格给，倒追上去的概率小的0%
c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)==1))-(n-2):n*(find(m(n-i+1,:)==1)));
%霍夫曼编码的定义是概率小的地方赋值为0，填在下一行复制上来的值的后面%
c(n-i,n)='0';
%同理从图上可以看到当寻找到排序为1的位置时将其定义的0或1以及其前面的空格全部复制到上一行的第二位置，当然要留出一个空格给，倒追上去的概率相对大的1% c(n-i,n+1:2*n-1)=c(n-i,1:n-1);
%霍夫曼编码的定义是概率的地方赋值为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(m(n-i+1,:)==j+1)-1)+1:n*find(m(n-i+1,:)==j+1));
end
end
%h函数为存放5个字符霍夫曼编码%
fori=1:n
%寻找方式为，运用m矩阵第一行存放的是从小到大后的原有下标位置，例如当i=1时，寻找的是字符A的霍夫曼编码，A的位置原来为1，而find来寻找1的位置，又c为每行总共有25个空格以5*5存放，5个霍夫曼编码，每个霍夫曼编码寄存在5个空格中，其中包括空格，如此依次寻找5个字符的霍夫曼编码%
h(i,1:n)=c(1,n*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*n);
%由于h矩阵中有空格字符，所以当要计算bit长度时，就除去空格位置将不为空格bit长度用L函数依次存放%
L1(i)=length(find(abs(h(i,:))~=32));
end
%一一显示最后霍夫曼编码的结果%
disp('Encoded results:');
fori=1:n
disp([char(64+i),':',h(i,:)]);
end
pause;
%因为L1为存放各个字符的bit数，再计算霍夫曼编码后的总bit数，并显示最后的结果%
L=sum(p.*L1);
disp(['Average code length after Huffman encoding:',num2str(L)]); pause;
%计算霍夫曼编码的压缩率L0/L，并显示结果%
disp(['Compressionratio=',num2str(L0),'/',num2str(L),'=',num2str(L0/L)]);
Ⅱ.运行结果如下：
Symbol probability of the source:
Prob(A):0.26667
Prob(B):0.33333
Prob(C):0.1
Prob(D):0.13333
Prob(E):0.16667
----------------------------------------------------------------------------------------------------------------- ENtropy of the source:2.1874bits
Average code length before Huffman encoding:3bits
----------------------------------------------------------------------------------------------------------------- Encoded results:
A: 10
B: 11
C: 010
D: 011
E: 00
----------------------------------------------------------------------------------------------------------------- Average code length after Huffman encoding:2.2333 Compression ratio=3/2.2333=1.3433
Ⅲ.分析优缺点及改进方案
上课老师写的这个程序虽然运行出来是正确无误的，但是个人觉得，程序不应该有他的局限性，第一部分在建立P的信源概率时，编码已经将其固定，只有特殊性，不具普遍性，第二部分倒寻找霍夫曼编码的过程也将予以改变。
第二部分
1. JP版霍夫曼编码
Ⅰ.代码之JP版:
closeall;clc;clearall;
String=input('Input String one by one:','s');
n=length(String);
S=reshape(str2mat(String),1,n);
s=zeros(1,94);
fori=1:n switch S(i) case ('!') s(1)=s(1)+1; case ('"') s(2)=s(2)+1; case ('#') s(3)=s(3)+1; case ('$') s(4)=s(4)+1; case ('%') s(5)=s(5)+1; case ('&') s(6)=s(6)+1; case (',') s(7)=s(7)+1; case ('(') s(8)=s(8)+1; case (')') s(9)=s(9)+1; case ('*') s(10)=s(10)+1; case ('+') s(11)=s(11)+1; case (',') s(12)=s(12)+1; case ('-') s(13)=s(13)+1; case ('.') s(14)=s(14)+1; case ('/') s(15)=s(15)+1; case ('0') s(16)=s(16)+1; case ('1') s(17)=s(17)+1;; case ('2') s(18)=s(18)+1; case ('3') s(19)=s(19)+1; case ('4') s(20)=s(20)+1; case ('5')
case ('6')
s(22)=s(22)+1;
case ('7')
s(23)=s(23)+1;
case ('8')
s(24)=s(24)+1;
case ('9')
s(25)=s(25)+1;
case (':')
s(26)=s(26)+1;
case (';')
s(27)=s(27)+1;
case ('
s(28)=s(28)+1;
case ('=')
s(29)=s(29)+1;
case ('>')
s(30)=s(30)+1;
case ('?')
s(31)=s(31)+1;
case('@')
s(32)=s(32)+1;
case ('A')
s(33)=s(33)+1;
case ('B')
s(34)=s(34)+1;
case ('C')
s(35)=s(35)+1;
case ('D')
s(36)=s(36)+1;
case('E')
s(37)=s(37)+1;
case ('F')
s(38)=s(38)+1;
case ('G')
s(39)=s(39)+1;
case ('H')
s(40)=s(40)+1;
case ('I')
s(41)=s(41)+1;
case ('J')
s(42)=s(42)+1;
case ('K')
case ('L')
s(44)=s(44)+1;
case ('M')
s(45)=s(45)+1;
case ('N')
s(46)=s(46)+1;
case ('O')
s(47)=s(47)+1;
case ('P')
s(48)=s(48)+1;
case ('Q')
s(49)=s(49)+1;
case ('R')
s(50)=s(50)+1;
case ('S')
s(51)=s(51)+1;
case ('T')
s(52)=s(52)+1;
case ('U')
s(53)=s(53)+1;
case ('V')
s(54)=s(54)+1;
case ('W')
s(55)=s(55)+1;
case ('X')
s(56)=s(56)+1;
case ('Y')
s(57)=s(57)+1;
case ('Z')
s(58)=s(58)+1;
case ('[')
s(59)=s(59)+1;
case ('/')
s(60)=s(60)+1;
case (']')
s(61)=s(61)+1;
case ('^')
s(62)=s(62)+1;
case ('_')
s(63)=s(63)+1;
case ('`')
s(64)=s(64)+1;
case ('a')
case ('b')
s(66)=s(66)+1;
case ('c')
s(67)=s(67)+1;
case ('d')
s(68)=s(68)+1;
case ('e')
s(69)=s(69)+1;
case ('f')
s(70)=s(70)+1;
case ('g')
s(71)=s(71)+1;
case ('h')
s(72)=s(72)+1;
case ('i')
s(73)=s(73)+1;
case ('j')
s(74)=s(74)+1;
case ('k')
s(75)=s(75)+1;
case ('l')
s(76)=s(76)+1;
case ('m')
s(77)=s(707)+1;
case ('n')
s(78)=s(78)+1;
case ('o')
s(79)=s(79)+1;
case ('p')
s(80)=s(80)+1;
case ('q')
s(81)=s(81)+1;
case ('r')
s(82)=s(82)+1;
case ('s')
s(83)=s(83)+1;
case ('t')
s(84)=s(84)+1;
case ('u')
s(85)=s(85)+1;
case ('v')
s(86)=s(86)+1;
case ('w')
case ('x')
s(88)=s(88)+1;
case ('y')
s(89)=s(89)+1;
case ('z')
s(90)=s(90)+1;
case ('{')
s(91)=s(91)+1;
case ('|')
s(92)=s(92)+1;
case ('}')
s(93)=s(93)+1;
case ('~')
s(94)=s(94)+1;
end
end
countrank=find(s~=0);
N=length(countrank);
s0=s;
s0(:,find(s
Totalsymbol=sum(s0);
P=s/Totalsymbol;
p=s0/Totalsymbol;
if length(find(p
error('Error:Input number in p
end
disp(['Pay attention!U input ',num2str(N),' Symbols']);
fori=countrank
disp(['The number of ',char(i+32),' is',num2str(s(i)),' The Symbol probability of ',char(i+32),' :',num2str(P(i))]);
end
pause;
H=sum(-p.*log2(p));
disp(['ENtropy of the source:',num2str(H),'bits']);
L0=ceil(log2(N));
disp(['Average code length before Huffman
encoding:',num2str(L0),'bits']);
pause;
q=p;
rank=zeros(N-1,N);
fori=1:N-1
[q,L]=sort(q);
rank(i,:)=[L(1:N+1-i),zeros(1,i-1)];
q=[q(1)+q(2),q(3:N),1];
end
fori=1:N-1
hufftree(i,:)=blanks(N*N);
end
hufftree(N-1,N)='0';
hufftree(N-1,2*N)='1';
fori=2:N-1
hufftree(N-i,1:N-1)=hufftree(N-i+1,N*(find(rank(N-i+1,:)==1))-(N-2):N*(find(rank(N-i+1,:)==1)));
hufftree(N-i,N)='0';
hufftree(N-i,N+1:2*N-1)=hufftree(N-i,1:N-1);
hufftree(N-i,2*N)='1';
for j=1:i-1
hufftree(N-i,(j+1)*N+1:(j+2)*N)=hufftree(N-i+1,N*(find(rank(N-i+1,:)==j+1)-1)+1:N*find(rank(N-i+1,:)==j+1));
end
end
fori=1:N
huffman(i,1:N)=hufftree(1,N*(find(rank(1,:)==i)-1)+1:find(rank(1,:)==i)*N);
L1(i)=length(find(abs(huffman(i,:))~=32));
end
disp('Encoded results:');
fori=countrank
disp(['The symbol probability ',char(i+32),' of huffman one by one']); end
for k=1:N
disp([huffman(k,:)]);
end
pause;
L=sum(p.*L1);
disp(['Average code length after Huffman encoding:',num2str(L)]);
pause;
disp(['Compression
ratio=',num2str(L0),'/',num2str(L),'=',num2str(L0/L)]);
Ⅱ.运行结果如下：
Input String one by one:aaqqqqqqqwwwwweeeee@#$$$$
----------------------------------------------------------------------------------------------------------------- Pay attention!U input 7 Symbols
The number of # is1 The Symbol probability of # :0.04
The number of $ is4 The Symbol probability of $ :0.16
The number of @ is1 The Symbol probability of @ :0.04
The number of a is2 The Symbol probability of a :0.08
The number of e is5 The Symbol probability of e :0.2
The number of q is7 The Symbol probability of q :0.28
The number of w is5 The Symbol probability of w :0.2
----------------------------------------------------------------------------------------------------------------- ENtropy of the source:2.529bits
Average code length before Huffman encoding:3bits
----------------------------------------------------------------------------------------------------------------- Encoded results:
The symbol probability # of huffman one by one
The symbol probability $ of huffman one by one
The symbol probability @ of huffman one by one
The symbol probability a of huffman one by one
The symbol probability e of huffman one by one
The symbol probability q of huffman one by one
The symbol probability w of huffman one by one
11000
111
11001
1101
00
10
01
----------------------------------------------------------------------------------------------------------------- Average code length after Huffman encoding:2.56
Compression ratio=3/2.56=1.1719
-----------------------------------------------------------------------------------------------------------------
第三部分
经过这次自己编写霍夫曼编码，我对于整个压缩过程有了一个初步了解，在整个学习过程中，要将一个直观的问题变为一个程序为之所用一直是一个不简单的地方，让我认识到计算机与数学两者是一个不可分割的，相辅相成。虽然我认为在matlab中for语句的效率不高，并且我也想跳过for语句循环结构，但是最终还是选择了for语句。
对于matlab仿真，我一直都非常感兴趣，如何将实际问题归为一个编程问题虽然不简单，但是非常有趣，如何把一个复杂低效率的程序改为一个高效率简单化的程序才是我们学习的最终目的。