huffman.m

霍夫曼coding程序

function CODE = huffman(p)
% HUFFMAN Builds a variable-length Huffman code for a symbol source.
%   CODE = HUFFMAN(P) returns a Huffman code as binary strings in
%   cell array CODE for input symbol probability vector P. Each word
%   in CODE corresponds to a symbol whose probability is at the
%   corresponding index of P.
%
%   Based on huffman5 by Sean Danaher, University of Northumbria,
%   Newcastle UK. Available at the MATLAB Central File Exchange:
%   Category General DSP in Signal Processing and Communications.

% Check the input arguments for reasonableness.
error(nargchk(1 , 1 , nargin));
if (ndims(p) ~= 2) | (min(size(p)) > 1) | ~isreal(p) | ~isnumeric(p) 
    error('P must be a real numeric vector,');
end

% Global variable surviving all recursions of function 'makecode'
global CODE
CODE = cell(length(p) , 1);     % Init the global cell array

if length(p) > 1                % When more than one symbol...
    p = (p / sum(p));           % Normalize the input probabolities
    s = reduce(p);              % Do Huffman source symbol reductions
    makecode(s , []);           % Recursively generate the code
else
    CODE = {'1'};               % Else, trivial one symbol case!
end;

%--------------------------------------------------------------------%
function s = reduce(p);
% Create a Huffman source reduction tree in a MATLAB cell structure
% by performing source symbol reductions until there are only two
% reduced symbols remaining

s = cell(length(p) , 1);

% Generate a starting tree with symbol nodes 1,2,3, ... to
% reference the symbol probabilities
for i = 1 : length(p)
    s{i} = i;
end

while numel(s) > 2
    [p , i] = sort(p);           % Sort the sybmol probabilities
    p(2) = p(1) + p(2);          % Merge the 2 lowest probabilities
    p(1) = [];                   % and prune the lowest one
    
    s = s(i);                    % Reorder tree for new probabilities
    s{2} = {s{1} , s{2}};        % and merge & prune its nodes
    s(1) = [];                   % to match the probabilities
end

%--------------------------------------------------------------------%
function makecode(sc , codeword)
% Scan the nodes of a Huffman source reduction tree recursively to
% generate the indicated variable length code words.

% Global variable surviving all recursive calls
global CODE
if isa(sc , 'cell')                     % For cell array nodes,
    makecode(sc{1} , [codeword 0]);     % add a 0 if the 1st element
    makecode(sc{2} , [codeword 1]);     % or a 1 if the 2nd
else                                    % For leaf (numeric) nodes,
    CODE{sc} = char('0' + codeword);    % create a char code string
end