Huffman codes require an enormous number of computations. For N source symbols, N-2 source reductions (sorting operations) and N-2 code assignments must be made. Sometimes we sacrifice coding efficiency for reducing the number of computations.

Truncated Huffman coding is a variation of standard Huffman coding.

In truncated Huffman coding the first K (out of overall J source symbols) most probable source symbols joined with hypothetical symbol which probability is equal to sum of probabilities of J-K less probable source symbols are coded with standard Huffman code.

The J-K less probable source symbols are assigned the Huffman code of that hypothetical symbol concatenated with natural binary code of length log 2 (J-K).

For example, if J=10 and K=4, then J-K=6 and we add binary code of length 3 as

The constant K < J may be chosen arbitrarily and if K=J truncated Huffman coding is equivalent to standard Huffman coding. The truncated Huffman coding makes J-K-1 Huffman code assignments and J-K-1 source reductions, thus taking less time, by cost of greater average code length and less efficiency.

Truncated Huffman Algorithm:

A truncated Huffman code is generated by:

• Arranging the source symbols so that their probabilities are monotonically decreasing.
• Dividing the total number of symbols (J) into two groups, the first group consists of the first K most probable source symbols and the second group consists of the remaining J-K symbols.
• Adding a hypothetical symbol to the first group. Its probability is equal to sum of probabilities of J-K less probable source symbols.

Arranging the new set of source symbols (K+1) so that their probabilities are monotonically decreasing.

Encoding the new set of symbols with the standard Huffman code.

The J-K less probable source symbols are assigned the Huffman code of that hypothetical symbol concatenated with natural binary code of length log2 (J-K).