Main Content

huffmandict

Generate Huffman code dictionary for source with known probability model

collapse all in page

Syntax

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

Description

example

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

example

[dict,avglen] = huffmandict(symbols,prob,N) generates an N-ary Huffman code dictionary using maximum variance algorithm. N must not exceed the number of source symbols.

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

Examples

collapse all

Open Live Script

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

Specify a symbol alphabet vector and a symbol probability vector.

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

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} % Codeword for fifth signal value
samplecode = 1×3

     1     1     0
Open Live Script

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

Specify a symbol alphabet vector and a symbol probability vector.

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

Generate a binary Huffman code, displaying 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 with minimum variance.

[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

collapse all

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

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-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 for Huffman code, specified as one of these values.

  • 'min' — This function generates N-ary Huffman code dictionary with the minimum variance. If you do not specify the variance input argument, the function uses this case.

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

Data Types: char

Output Arguments

collapse all

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

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

Data Types: double

References

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

Version History

Introduced before R2006a

See Also

Functions

Topics