Method of constructing an approximated dynamic Huffman table for use in data compression
US7834781B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 6, 2009 |
| Grant date | Nov 16, 2010 |
| Priority date | — |
| Expiry date | May 8, 2029 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH03M7/40
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
Abstract
A novel and useful method of constructing a fast approximation of a dynamic Huffman table from a data sample comprising a subset of data to be compressed. The frequency of incidence of each symbol in the sample is calculated, and the symbols are then allocated to predefined bins based on their frequency of incidence. The bins are then transformed into binary sub-trees, where the leaf nodes of the binary sub-trees comprise the symbols of the bin associated with the binary sub-trees. The binary sub-trees are then combined via nesting, thereby creating a coarse grained binary tree, where all leaves are mapped to a specified number of depths. The coarse grained binary tree is then traversed, thereby yielding a canonical code for each symbol, thereby defining the entries for a dynamic Huffman table.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.