System and method for compressing data
First Claim
1. A data structure stored on a computer readable medium, comprising:
- a field representing a decoding structure to decode canonical Huffman encoded data, the decoding structure including;
a field representing an accelerator table to perform a 2N-deep direct-index lookup of the encoded data to provide a high-frequency symbol for high-frequency data and to provide bracketing indices for low-frequency data; and
a field representing a binary search table to provide a symbol index using a binary search bounded by the bracketing indices; and
a field representing a symbol table to provide a symbol associated with the symbol index.
1 Assignment
0 Petitions
Accused Products
Abstract
Systems, devices and methods are provided to compress data, and in particular to code and decode data. One aspect of the present subject matter is a data structure. The data structure includes a field representing a decoding structure to decode canonical Huffman encoded data, and a field representing a symbol table. The decoding structure includes a field representing an accelerator table to provide a 2N-deep direct-index lookup to provide high-frequency symbols for high-frequency data and to provide bracketing indices for low-frequency data. The decoding structure also includes a field for a binary search table to provide a low-frequency symbol index using a binary search bounded by the bracketing indices provided by the accelerator table. The symbol table is adapted to provide a symbol associated with the low-frequency index.
35 Citations
33 Claims
-
1. A data structure stored on a computer readable medium, comprising:
-
a field representing a decoding structure to decode canonical Huffman encoded data, the decoding structure including;
a field representing an accelerator table to perform a 2N-deep direct-index lookup of the encoded data to provide a high-frequency symbol for high-frequency data and to provide bracketing indices for low-frequency data; and
a field representing a binary search table to provide a symbol index using a binary search bounded by the bracketing indices; and
a field representing a symbol table to provide a symbol associated with the symbol index. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. An electronic navigational aid device, comprising:
-
a processor; and
a memory connected to the processor, wherein the processor and memory are adapted to cooperate to;
perform a 2N-deep direct-index lookup using N bits from canonical Huffman encoded data, extract high-frequency symbols based on the direct-index lookup, provide bracketing indices for low-frequency data based on the direct-index lookup, perform a binary search using the bracketing indices to provide a low-frequency symbol index, and extract the low-frequency symbols associated with the low-frequency symbol index. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
a field containing canonical Huffman encoded data, the encoded data including high-frequency data and low-frequency data;
a field representing a decoding structure to decode the encoded data, the decoding structure including;
a field representing an accelerator table to perform the 2N-deep direct-index lookup to provide the high-frequency symbols for the high-frequency data and to provide the bracketing indices for the low-frequency data;
a field representing a binary search table to provide the low-frequency symbol index using the binary search bounded by the bracketing indices; and
a field representing a symbol table to provide the low-frequency symbols associated with the low-frequency symbol index.
-
-
15. The electronic navigational aid device of claim 14, wherein the accelerator table and the binary table each have a size that is capable of being determined at a time when the canonical Huffman encoded data is coded.
-
16. The electronic navigational aid device of claim 14, wherein increasing the size of the accelerator table improves decoding speed by increasing a value of N in the 2N-deep direct-index lookup such that the accelerator table is adapted to provide more high-frequency symbols.
-
17. The electronic navigational aid device of claim 14, wherein decreasing the size of the accelerator table decreases an overall size of the decoding structure and decreases the decoding speed by decreasing a value of N in the 2N-deep direct index lookup such that the accelerator table is adapted to provide less high-frequency symbols.
-
18. The electronic navigational aid device of claim 14, wherein the accelerator table includes a symbol index column to provide high-frequency indices for the high-frequency data that has a code length less than or equal to N bits.
-
19. The electronic navigational aid device of claim 14, wherein the accelerator table includes a binary search table start index column and a binary search table end index column to provide the bracketing indices for the low frequency data that has a code length longer than N bits.
-
20. The electronic navigational aid device of claim 14, wherein encoded data that have an equal bit length are categorized in a symbol group, and wherein the binary search table includes a base canonical Huffman code for each symbol group and a base symbol index column to provide a base symbol index for each base canonical Huffman code.
-
21. A navigation system, comprising:
-
a server; and
a navigation device adapted to communicate with and retrieve navigation data from the server via a communication channel, wherein the system is adapted to;
perform a 2N-deep direct-index lookup using N bits from canonical Huffman encoded navigation data, extract high-frequency symbol based on the direct-index lookup, provide bracketing indices for low-frequency data based on the direct-index lookup, perform a binary search using the bracketing indices to provide a low-frequency symbol index, and extract the low-frequency symbol associated with the low-frequency symbol index. - View Dependent Claims (22, 23, 24, 25, 26, 27)
-
-
28. A method, comprising:
-
performing a direct-index lookup using N bits from canonical Huffman encoded data;
determining whether a high-frequency symbol is found based on the direct-index lookup;
upon determining that a high-frequency symbol is found based on the direct-index lookup, extracting the high-frequency symbol;
upon determining that a high-frequency symbol is not found based on the direct-index lookup, providing bracketing indices for an auxiliary table based on the direct index lookup;
performing a binary search using the auxiliary table and the bracketing indices to provide a low-frequency symbol index; and
extracting a low-frequency symbol associated with the low-frequency symbol index. - View Dependent Claims (29, 30, 31, 32, 33)
retrieving N bits from the canonical Huffman encoded data; and
using the N bits to directly index 2N-deep into an accelerator table to provide high-frequency symbol indices.
-
-
32. The method of claim 28, wherein performing a binary search using the auxiliary table and the bracketing indices to provide a low-frequency symbol index comprises:
-
retrieving the bracketing indices;
retrieving additional bits from the canonical Huffman encoded data to provide an L-bit compare value;
performing a binary search bounded by the bracketing indices;
identifying a base Huffman code and a base symbol index for the L-bit compare value;
deriving a comparison index from the L-bit compare value and the base Huffman code;
identifying a symbol index from the comparison index and the symbol base index; and
extracting a symbol associated with the symbol index.
-
-
33. The method of claim 28, further comprising shifting a data string used in a previous decoding iteration to use unused bits in the previous decoding iteration as most significant bits for a successive decoding iteration.
Specification