Method of building an adaptive huffman codeword tree
AssigneeXerox Corporation
InventorSimon M. Law
Life of this patent
Estimating the term…
Abstract
Many compression algorithms require the compressor to generate trees (tables) for encoding purposes. To generate the optimum tree for a set of Huffman symbols either takes too much time or requires too much hardware. This invention proposes to separate the symbols into groups according to the symbol's occurring frequency. With these groups of symbols available, subsequent code length assignment of these groups can be done without a complete sorting of all the symbols and their parents. During code length assignment, some relocation of individual symbols from one group to another can also be performed to optimize the Huffman table. In most of the cases this technique can achieve a compression ratio within 5% of the optimum Huffman table, while requiring less hardware or software overhead.
Claims4
A method of building an adaptive Huffman codeword tree for input symbols comprising the steps of:
- a) creating a number of bands to continuously cover all frequencies of use from least to most used symbols,
- b) assigning a number of codeword bits to each band, lower numbers being assigned to higher frequencies,
- c) assembling all symbols into a list in order of frequency of use, and assigning each symbol to a group so that the frequency of each symbol falls within the band of the group,
- d) if there is enough space in a current group for all symbols assigned to the group, assign to each symbol a current codeword, and increment the codeword for each symbol,
- f) if there is enough space in the current group for all of the remaining symbols, assign to each remaining symbol a current codeword and increment the codeword, and
- g) if the current symbol is the last symbol of a group, increment the codeword, add a zero to the end of the codeword to start a new group, and go back to step d).
Dependencies are inferred from the claim text.