Huffman编码树通过MATLAB实现

%%% 下面用MATLAB实现哈夫曼编码的例程（以子函数形式给出）: clear all; fprintf('Reading data ....') data=imread('E:\temp\originalimage(holl).bmp') data=uint8(data);% 读入数据，并将数据限制为unit8型 fprintf('Done!\n') fprintf('Comqressing data...') [zipped,info]=norm2huff(data); %进行压缩编码 fprintf('Done!\n') fprintf('Decomqressing data...') unzipped=huff2norm(zipped,info);% 进行解压缩 fprintf('Done!\n') isOK=isequal(data(:),unzipped(:)) %显示压缩效果 whos data zipped unzipped %%%%%%%%%% norm2huff %%%%%%%%%% % NORM2HUFF 哈夫曼编码器 % 对于输入向量，NORM2HUFF(X) 返回向量的哈夫曼编码后的码串 % 矩阵用X(:)形式输入 % 输入限制为 unit8格式，输出为unit8的序列 % [….,info] 返回解码需要的解码信息 % INFO.pad =最后添加的比特数 % INFO.huffcodes=Huffman码字 % INFO.ratio=压缩率 % INFO.length=原始数据长度 % INFO.maxcodelen=最大码长 % function [zipped, info] = norm2huff(vector) if ~isa(vector,'unit8'), error ('input argument must be a unit8 vector'); end %保证输入为unit8的数据 vector = vector(:)'; %将输入向量转换为行向量 f=frequency(vector); %计算个元素出现的概率 simbols=find(f~=0); %寻找数出现的所有元素 f=f(simbols); [f,sortindex]=sort(f); %将元素按照出现概率排列 simbols=simbols(sortindex); len=length(simbols); simbols_index=num2cell(1:len); codeword_tmp=cell(len,1); while length(f)>1, index1=simbols_index{1}; index2=simbols_index{2}; codeword_tmp(index1)=addnode(codeword_tmp(index1),unit8(0)); codeword_tmp(index2)=addnode(codeword_tmp(index1),unit8(1)); f=[sum(f(1:2)) f(3:end)]; simbol_index=[{[index1 index2]} simbols_index(3:end)]; %将数据重新排列，是两个节点的频率尽量与前一个节点的频率相当 [f,sortindex]=sort(f); simbols_index=simbols(sortindex); end %对应相应的元素和码字 codeword=cell(256,1); code(simbols)=codeword_tmp; %计算总的字符串长度 len=0; for index=1:length(vector), len=len+length(codeword{double(vector(index))+1}); end %产生0 1序列 string=repmat(unit8(0),1,len); pointer=1; for index=1:length(vector), code = codeword{double(vector(index))+1}; len=length(code); string(pointer+(0:len-1))=code; poiter=pointer+len; end %如果需要的话加零 len=length(string); pad=8-mod(len,8); if pad>0, string =[string unit8(zeros(1,pad))]; end %保存实际有用的码字 codewod=codeword(simbols); codelen=zeros(size(codeword)); weights=2.^(0:23); maxcodelen=0; for index=1:length(codeword), len=length(codeword{index}); if len>maxcodelen, maxcodelen=len; end if len>0, code=sum(weights(codeword{index}==1)); code=bitset(code,len+1); codeword(index)=code; codelen(index)=len; end end codeword=[codeword{:}]; %计算压缩后的向量 cols=length(string)/8; string=reshape(string,8,cols); weights=2.^(0:7); zipped=uni8(weights*double(string)); %存储数据到一个稀疏矩阵 huffcodes=sparse(1,1); for index=1:numel(codeword), huffcodes(codeword(index),1)=simbols(index); end %产生信息结构体 info.pad=pad; info.huffcodes=huffcodes; info.rato=cols./length(vector); info.length=length(vector); info.maxcodelen=maxcodelen; %%%%%%%%%% addnode %%%%%%%%%%%% function codeword_new=addnode(codeword_old,item) codewod_new=cell(size(codeword_old)), codeword_new{index}=[item codeword_old{index}]; %%%%%%%% huff2norm %%%%%%%%%%%% function vector =huff2norm(zipped,info) % HUFF2NORM 哈夫曼解码器 if ~isa(zipped,'unit8'), error('input argument must be a unit vector') end %产生01 序列 len=length(zipped ); string=repmat(unit8(0),1,len.*8); bitindex=1:8; for index =1:len, string(bitindex+8.*(index-1)) , unit8(bitget(zipped(index),bitindex)); end %调整字符串 string=logical(string(:)'); len=length(string); string((len-info.pad.l+1):end)=[ ]; len=length(string); %解码 weights=2>(0:51); vector=repmat(unit8(0),1,info.length); vectorindex=1; codeindex=1; code=0; for index=1:len, code=bitset(code,codeindex,string(index)); codeindex=codeindex+1; byte=decode(bitset(code,codeindex),info); if byte>0, vector(vectorindex)=byte-1; codeindex=1; code=0; vectorindex=vectorindex+1; end end %%%%%%%%%%%%% decode %%%%%%%%%% function byte=decode(code,info) byte=info.huffcode(code); % %%%%%%%%%% frequence %%%%%%%%%% function f=frequency(vector) % FREQUENCY 计算元素出现概率 if ~isa(vector,'unit8'), error('input argument must be a unit8 vector ') end f=repmat(0,1,256); %扫描向量 len=length(vector); for index=1:255, f(index+1)=sum(vector==unit8(index)); end %归一化 f=f./len; % 运行上述程序，得到结果为： % Name Size Bytes Class % data 256*256 65535 unit8 arrray % unzipped 1*65535 65535 unit8 arrray % zipped 1*57712 57712 unit8 arrray % Grand total is 188784 elements using 188784 bytes % 其中压缩的信息结构体info 为： % pad:7 % huffcodes:[108471*1 double] % ratio:0.8806 % length:65535 % maxcodelen:16