Documentation

huffmandict

Generate Huffman code dictionary for source with known probability model

Syntax

[dict,avglen] = huffmandict(symbols,p)
[dict,avglen] = huffmandict(symbols,p,N)
[dict,avglen] = huffmandict(symbols,p,N,variance)

Description

For All Syntaxes

The huffmandict function generates a Huffman code dictionary corresponding to a source with a known probability model. The required inputs are

• symbols, which lists the distinct signal values that the source produces. It can have the form of a numeric vector, numeric cell array, or alphanumeric cell array. If it is a cell array, it must be either a row or a column.

• p, a probability vector whose kth element is the probability with which the source produces the kth element of symbols. The length of p must equal the length of symbols.

The outputs of huffmandict are

• dict, a two-column cell array in which the first column lists the distinct signal values from symbols and the second column lists the corresponding Huffman codewords. In the second column, each Huffman codeword is represented as a numeric row vector.

• avglen, the average length among all codewords in the dictionary, weighted according to the probabilities in the vector p.

For Specific Syntaxes

[dict,avglen] = huffmandict(symbols,p) generates a binary Huffman code dictionary using the maximum variance algorithm.

[dict,avglen] = huffmandict(symbols,p,N) generates an N-ary Huffman code dictionary using the maximum variance algorithm. N is an integer between 2 and 10 that must not exceed the number of source symbols whose probabilities appear in the vector p.

[dict,avglen] = huffmandict(symbols,p,N,variance) generates an N-ary Huffman code dictionary with the minimum variance if variance is 'min' and the maximum variance if variance is 'max'. N is an integer between 2 and 10 that must not exceed the length of the vector p.

Examples

collapse all

Generate a binary Huffman code dictionary. Assign the second output to return the average code length.

Specify symbol alphabet and probability vectors.

symbols = (1:5); % Alphabet vector
prob = [.3 .3 .2 .1 .1]; % Symbol probability vector

Generate binary Huffman code. View the average code length and the cell array containing the codeword dictionary.

[dict, avglen] = huffmandict(symbols,prob);
avglen
avglen = 2.2000
dict
dict=5×2 cell
{}    {1x2 double}
{}    {1x2 double}
{}    {1x2 double}
{}    {1x3 double}
{}    {1x3 double}

View the fifth codeword from the dictionary.

samplecode = dict{5,2} % Codeword for fifth signal value
samplecode = 1×3

1     1     0

Use the code dictionary generator for Huffman coder function to generate binary and ternary Huffman codes.

Specify symbol alphabet and probability vectors

symbols = (1:5); % Alphabet vector
prob = [.3 .3 .2 .1 .1]; % Symbol probability vector

Generate binary Huffman code.

[dict, avglen] = huffmandict(symbols, prob);
dict(:, 2) = cellfun(@num2str, dict(:, 2), 'UniformOutput', false)
dict=5×2 cell
{}    {'0  1'   }
{}    {'0  0'   }
{}    {'1  0'   }
{}    {'1  1  1'}
{}    {'1  1  0'}

Generate ternary Huffman code

[dict,avglen] = huffmandict(symbols,prob, 3);
dict(:, 2) = cellfun(@num2str, dict(:, 2), 'UniformOutput', false)
dict=5×2 cell
{}    {'2'   }
{}    {'1'   }
{}    {'0  0'}
{}    {'0  2'}
{}    {'0  1'}

References

 Sayood, Khalid, Introduction to Data Compression, San Francisco, Morgan Kaufmann, 2000.