ISO/IEC 10918-1 : 1993(E)
K.2
A procedure for generating the lists which specify a Huffman code table
A Huffman table is generated from a collection of statistics in two steps. The first step is the generation of the list of
lengths and values which are in accord with the rules for generating the Huffman code tables. The second step is the
generation of the Huffman code table from the list of lengths and values.
The first step, the topic of this section, is needed only for custom Huffman table generation and is done only in the
encoder. In this step the statistics are used to create a table associating each value to be coded with the size (in bits) of the
corresponding Huffman code. This table is sorted by code size.
A procedure for creating a Huffman table for a set of up to 256 symbols is shown in Figure K.1. Three vectors are defined
for this procedure:
FREQ(V)
Frequency of occurrence of symbol V
CODESIZE(V)
Code size of symbol V
OTHERS(V)
Index to next symbol in chain of all symbols in current branch of code tree
where V goes from 0 to 256.
Before starting the procedure, the values of FREQ are collected for V
=
0 to 255 and the FREQ value for V
=
256 is set to
1 to reserve one code point. FREQ values for unused symbols are defined to be zero. In addition, the entries in
CODESIZE are all set to 0, and the indices in OTHERS are set to 1, the value which terminates a chain of indices.
Reserving one code point guarantees that no code word can ever be all "1" bits.
The search for the entry with the least value of FREQ(V) selects the largest value of V with the least value of FREQ(V)
greater than zero.
The procedure "Find V1 for least value of FREQ(V1) > 0" always selects the value with the largest value of V1 when
more than one V1 with the same frequency occurs. The reserved code point is then guaranteed to be in the longest code
word category.
144
CCITT Rec. T.81 (1992 E)