Browse Prior Art Database

Trimming Of Huffman Coding Tables

IP.com Disclosure Number: IPCOM000067953D
Original Publication Date: 1979-Oct-01
Included in the Prior Art Database: 2005-Feb-20

Publishing Venue

IBM

Related People

Authors:
Marks, BL [+details]

Abstract

Huffman coding tables may be trimmed in order to trade-off table space against compression efficiency by dividing the characters to be encoded into two sets A and B which are coded differently. The first set A of most frequently occurring characters is augmented by a "copy" character which has as its frequency the sum of the frequencies in the second set B of remaining characters. The augmented set A characters are all Huffman encoded. The set B characters are all encoded as the Huffman "copy" character prefixed to the particular uncoded character. Before deciding whether a character should be assigned to the A or B set, it is necessary to know the effect on its encoded length. This is dependent on the length of "copy", which in turn is dependent on the decision.