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 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.

[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

Generate Huffman Code and View Results

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

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 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

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

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 for Huffman code

'min' | 'max'

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

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, 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.