Method of building an adaptive huffman codeword tree
US6040790A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | May 29, 1998 |
| Grant date | Mar 21, 2000 |
| Priority date | — |
| Expiry date | May 29, 2018 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH03M7/6047
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.