huffmandic.m

MATLAB编写的huffman编解码程序

function [dict,avglen] = huffmanDic(sig,prob)
%
%    Generates a binary Huffman code dictionary using the maximum variance 
%    algorithm for the distinct symbols given by the sig vector.  
%    The second input, prob, represents the probability of occurrence for 
%    each of these symbols. sig and prob must be of same length.
%--------------------------------------------------------------------------

% Make sure that the input symbols are in a cell array format
if ~iscell(sig)
	[m,n] = size(sig);
	sig = mat2cell(sig, ones(1,m), ones(1,n)) ;
end

% Create tree nodes with the signals and the corresponding probabilities
huff_tree = struct('signal',[],'probability',[],'child',[],'code',[],'origOrder',-1);
for i=1:length(sig)
    huff_tree(i).signal = sig{i}; 
    huff_tree(i).probability = prob(i); 
	huff_tree(i).origOrder = i;
end

% Sort the signal and probability vectors based on ascending order of probability
[s,i] = sort(prob);
huff_tree = huff_tree(i);

% Create a Huffman tree
huff_tree = createTree(huff_tree); 

% Create the codebook
[huff_tree,dict,avglen] = createDict(huff_tree,{},0); 

% Sort the dictionary
[dictsort,dictsortorder] = sort([dict{:,4}]);
finaldict = {};
for i=1:length(dictsortorder)
    finaldict{i,1} = dict{dictsortorder(i), 1};
    finaldict{i,2} = dict{dictsortorder(i), 2};
end
dict = finaldict;


%--------------------------------------------------------------------------
% Function: createTree
% Input: An array of structures to be arranged into a Huffman tree
% Utility: This is a recursive algorithm to create the Huffman Code tree.
function huff_tree = createTree(huff_tree)

% The termination condition for the recursive loop
if( length(huff_tree) <= 1)
    return;
end

% Change the nodes
temp = struct('signal',[],'probability',0,'child',[],'code',[]);
for i=1:2
    if( length(huff_tree) == 0)
        break; 
    end
    temp.probability = temp.probability + huff_tree(1).probability; 
    temp.child{i} = huff_tree(1);
	temp.origOrder = -1;
    huff_tree(1) = [];
end
huff_tree = insertNode(huff_tree, temp);

% Create a Huffman tree from the reduced number of free nodes
huff_tree = createTree(huff_tree);
return;


%--------------------------------------------------------------------------
% Function: insertNode
% This function will insert a node in the sorted list such that the
% resulting list will be sorted (ascending). If there exists node with the
% same probability as the new node, the new node  is placed after these
% same value nodes.
function huff_tree = insertNode(huff_tree, newNode)

sortedOn = [huff_tree.probability];
i = 1;
while i <= length(huff_tree) && newNode.probability > huff_tree(i).probability 
    i = i+1;
end
huff_tree = [huff_tree(1:i-1) newNode huff_tree(i:end)];


%--------------------------------------------------------------------------
% Function: createDict
% This function does a pre-order traversal of the tree to create the codes
% for each leaf node. This is a recursive function.
function [huff_tree,dict,total_wted_len] = createDict(huff_tree,dict,total_wted_len)

% Add signal on a leaf node and its corresponding code to the dictionary
if( length(huff_tree.child) == 0 )
    dict{end+1,1} = huff_tree.signal;
    dict{end, 2} = huff_tree.code;
    dict{end, 3} = length(huff_tree.code);  %sorting based on original order
	dict{end, 4} = huff_tree.origOrder;     %sorting based on the lenght of code
    total_wted_len = total_wted_len + length(huff_tree.code)*huff_tree.probability;
    return;
end
num_childrens = length(huff_tree.child);
for i = 1:num_childrens
    huff_tree.child{i}.code = [huff_tree(end).code,(num_childrens-i)];
    [huff_tree.child{i},dict,total_wted_len] = createDict(huff_tree.child{i},dict,total_wted_len);
end