huffmandict

Generate Huffman code dictionary for source with known probability model

Syntax

[dict,avglen] = huffmandict(symbols,prob)

[dict,avglen] = huffmandict(symbols,prob,N)

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

Description

[dict,avglen] = huffmandict(symbols,prob) generates a binary Huffman code dictionary, dict, for the source symbols, symbols, by using the maximum variance algorithm. The function also returns average codeword length of the dictionary (avglen), weighted according to the probabilities in the input prob.

[dict,avglen] = huffmandict(symbols,prob,N) generates an N-ary Huffman code dictionary using maximum variance algorithm.

[dict,avglen] = huffmandict(symbols,prob,N,variance) generates an N-ary Huffman code dictionary with the specified variance algorithm.

Examples

Generate Huffman Code and View Results

Generate a binary Huffman code dictionary, additionally returning the average code length.

Specify a symbol alphabet vector, symbols, and a symbol probability vector, prob.

symbols = (1:5);
prob = [.3 .3 .2 .1 .1];

Generate a binary Huffman code, displaying the average code length and the cell array containing the codeword dictionary.

[dict,avglen] = huffmandict(symbols,prob)

dict=5×2 cell array
    {[1]}    {[  0 1]}
    {[2]}    {[  0 0]}
    {[3]}    {[  1 0]}
    {[4]}    {[1 1 1]}
    {[5]}    {[1 1 0]}

avglen = 
2.2000

Display the fifth codeword from the dictionary.

samplecode = dict{5,2}

samplecode = 1×3

     1     1     0

Generate Ternary Huffman Codes

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

Specify a symbol alphabet vector, symbols, and a symbol probability vector, prob.

symbols = (1:5);
prob = [.3 .3 .2 .1 .1];

Generate a binary Huffman code, and then display the cell array containing the codeword dictionary.

[dict,avglen] = huffmandict(symbols,prob);
dict(:,2) = cellfun(@num2str,dict(:,2),UniformOutput=false)

dict=5×2 cell array
    {[1]}    {'0  1'   }
    {[2]}    {'0  0'   }
    {[3]}    {'1  0'   }
    {[4]}    {'1  1  1'}
    {[5]}    {'1  1  0'}

Generate a ternary Huffman code by using the minimum variance algorithm, and then display the cell array containing the codeword dictionary.

[dict,avglen] = huffmandict(symbols,prob,3,'min');
dict(:,2) = cellfun(@num2str,dict(:,2),UniformOutput=false)

dict=5×2 cell array
    {[1]}    {'2'   }
    {[2]}    {'1'   }
    {[3]}    {'0  0'}
    {[4]}    {'0  2'}
    {[5]}    {'0  1'}

Input Arguments

symbols — Source symbols

vector | cell array | alphanumeric cell array

Source symbols, specified as a vector, cell array, or an alphanumeric cell array. symbols lists the distinct signal values that the source produces. If symbols is a cell array, it must be a 1-by-S or S-by-1 cell array, where S is the number of symbols.

Data Types: double | cell

prob — Probability of occurrence

vector in the range [0, 1]

Probability of occurrence for each symbol, specified as a vector in the range [0, 1]. The elements of this vector must sum to 1. The length this vector must equal the length of input symbols.

Data Types: double

N — N-ary Huffman code dictionary

2 (default) | scalar in the range [2, 10]

N-ary Huffman code dictionary, specified as a scalar in the range [2, 10]. This value must be less than or equal to the length of input symbols.

Data Types: double

variance — Variance algorithm for Huffman code

'max' (default) | 'min'

Variance algorithm for Huffman code, specified as 'max' or 'min'.

• 'max' — This function generates N-ary Huffman code dictionary by using the maximum variance algorithm.

• 'min' — This function generates N-ary Huffman code dictionary by using the minimum variance algorithm.

Output Arguments

dict — Huffman code dictionary

two-column cell array

Huffman code dictionary, returned as a two-column cell array. The first column lists the distinct signal values from input symbols. The second column corresponds to Huffman codewords, where each Huffman codeword is represented as a row vector. If you specify the input argument N, the function returns dict as an N-ary Huffman code dictionary.

Data Types: double | cell

avglen — Average codeword length

positive scalar

Average codeword length of the dictionary, returned as a positive scalar that is weighted according to the probabilities in the input prob.

Data Types: double

References

[1] Sayood, Khalid. Introduction to Data Compression. 2nd ed. San Francisco: Morgan Kaufmann Publishers, 2000.

Version History

Introduced before R2006a