Matlab实现自适应Huffman哈夫曼编码

function huffstream = adaptivehuffman(stream,type) % %========================================================================== % Matt Clarkson - University of Bath % % Copyleft 2008 %========================================================================== % % huffstream = adaptivehuffman(stream,type) % % Adaptively encodes or decodes an integer stream. If type is not defined % the program inspects the input stream and failing to find a suitable % adaptively encoded huffman stream the program defaults to compression. % % The stream has a two bit header containing the bit depth of the symbols. % This is easily removed if a constant bit depth is always going to be % used. % % To help visualise the huffman tree a function "treedetails" can be called % at any point to display the values of each node. % % Examples: % % huffstream = adaptivehuffman(stream) returns a adaptively huffman encoded % stream or a decompressed string depending on the input. For compression % the input must be a one dimensional horizontal unsigned integer % array. 8 and 16 bit depths are accepted. For decompression the % input must be a previously encoded string % % huffstream = adaptivehuffman(stream,'enc') returns compressed stream. % Also the compression percentage is printed. % % huffstream = adaptivehuffman(stream,'dec') returns the result of % decompressing a previously compressed huffman stream. % %========================================================================== %========================================================================== %Insect input stream %========================================================================== if nargin < 2; %Inspects input stream if isinteger(stream)... %If integer... && (size((unique(stream)),2) == 2)... %and has two symbols... && isa(stream,'uint8')... %and a usigned 8 bit integer stream... && ~(size(size(stream),2)~=2)... %and is 2D... && (size(stream,1) == 1 && size(stream,2) > 0)... %and is 1D horizontal... && sum(unique(stream)) == 1 %and is binary stream type = 'dec'; else type = 'enc'; end end if ~strcmp(type,'dec') %If not decoding, encode %========================================================================== %Adaptive Huffman Encoding %========================================================================== clear type %-------------------------------------------------------------------------- %Check stream structure %-------------------------------------------------------------------------- if ~isinteger(stream);error('Input must be unsigned integer stream');end for i = 3:6;if isa(stream, num2str(2^i,'int%i'));error('Input must be unsigned integer stream');end;end if size(size(stream),2)~=2 || ~(size(stream,1) == 1 && size(stream,2) > 0) error('Input must be a one dimensional horizontal stream'); end %-------------------------------------------------------------------------- %Find bit depth of stream and check for accepted bit depths %-------------------------------------------------------------------------- for i = 3:6 if isa(stream, num2str(2^i,'uint%i'));bitdepth = 2^i;end; end if ~exist('bitdepth','var');error('Input stream must be a unsigned integer');end; if bitdepth == 64 || bitdepth == 32;error('Bit depth must be 8 or 16');end; %-------------------------------------------------------------------------- %Set up the Not Yet Transmitted (NYT) Node and Tree Structure %-------------------------------------------------------------------------- huffstream = uint8([]); %Initialise outputstream NYT = unique(stream); %Find unique symbols and create NYT list NYTlocation = double(max(NYT))+2; %Set the NYT location n = length(stream); %Find length of stream nodenumber = (2*n); %Find the amount of nodes tree(1).number = nodenumber; %Total number of nodes tree(1).parent = 0; %Node parent tree(1).left = 0; %Node left child tree(1).right = 0; %Node right child tree(1).symbol = NYTlocation; %Node symbol tree(1).weight = 0; %Node Weight location = zeros(1,NYTlocation); %Location of the symbols in the tree location(NYTlocation) = 1; %Location of the NYT node %-------------------------------------------------------------------------- %Add a one bit header to the huffman stream where 0 and 1 represent %8 and 16 bit depths respectively. If the function is going to be used %with only one bit depth the following line can be commented out. Make %sure, the bit depth in the decoding section is changed accordingly %-------------------------------------------------------------------------- huffstream = [huffstream uint8(bitget((log2(bitdepth)-3),1))]; %-------------------------------------------------------------------------- %Huffman Tree loop %-------------------------------------------------------------------------- wb = waitbar(0,'Please Wait...','Name','Encoding'); %Creates progress bar for index = 1:n %For whole stream symbol = stream(index); %Read in symbol if sum(NYT == symbol) %Symbol seen before? nodecode(NYTlocation-1) %Add NYT code to the output stream treeloop(symbol); %Start the huffman tree loop for symbol huffstream(length(huffstream)+1:length(huffstream)+bitdepth) = uint8(bitget(symbol,bitdepth:-1:1)); %Output symbol else nodecode(symbol); %Add NYT code to the output stream treeloop(symbol); %Start the huffman tree loop for symbol end waitbar(index/n,wb); %Update progress bar end close(wb) %Close progress bar if nargin==2;fprintf(['Compressed: ' num2str((length(huffstream)/(length(stream)*bitdepth))*100,'%6.2f') '%%\n']);end; else %========================================================================== %Adaptive Huffman Decoding %========================================================================== clear type %-------------------------------------------------------------------------- %Finds bitdepth. If the function is going to be used with only one bit %depth alter the commenting of the following three assignments. Make sure %that, if a constant bit rate is going to be used, the header assignment in %the encoding part of the function is commented out. %-------------------------------------------------------------------------- bitdepth = 2^((bits2dec(stream(1)))+3);stream(1)=[]; %bitdepth = 8; %bitdepth = 16; %-------------------------------------------------------------------------- %Set up the Not Yet Transmitted (NYT) Node and Tree Structure %-------------------------------------------------------------------------- huffstream = eval(num2str(bitdepth,'uint%i([])')); %Initialise outputstream NYT = 0:(2^bitdepth)-1; %Find unique symbols and create NYT list NYTlocation = max(NYT)+2; %Set the NYT location n = length(stream); %Find length of stream nodenumber = max(2*NYT)+1; %Find the amount of nodes tree(1).number = nodenumber; %Total number of nodes tree(1).parent = 0; %Node parent tree(1).left = 0; %Node left child tree(1).right = 0; %Node right child tree(1).symbol = NYTlocation; %Node symbol tree(1).weight = 0; %Node Weight location = zeros(1,NYTlocation); %Location of the symbols in the tree location(NYTlocation) = 1; %Location of the NYT node %-------------------------------------------------------------------------- %Perform Decoding %-------------------------------------------------------------------------- wb = waitbar(0,'Please Wait...','Name',