System and method for compressing data in a PDA
First Claim
1. A data structure stored on a PDA, 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 in a PDA. 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.
38 Citations
33 Claims
-
1. A data structure stored on a PDA, 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. A personal digital assistant (PDA), comprising:
-
a calendar function;
an address book function;
a processor; and
a memory connected to the processor, wherein the processor and memory 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)
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.
-
-
14. The PDA of claim 13, 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.
-
15. The PDA of claim 13, 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.
-
16. The PDA of claim 13, 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.
-
17. The PDA of claim 13, 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.
-
18. The PDA of claim 13, 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.
-
19. The PDA of claim 13, 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.
-
20. A PDA navigation system, comprising:
-
a server; and
a PDA operable 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 (21, 22, 23, 24, 25, 26)
-
-
27. A method for a PDA, comprising:
-
in a PDA memory, 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 (28, 29, 30, 31, 32)
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.
-
-
31. The method of claim 27, 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.
-
-
32. The method of claim 27, 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.
-
33. A personal digital assistant (PDA), comprising:
-
a calendar function;
an address book function;
a processor operable to communicate with a memory;
means for performing a 2N-deep direct-index lookup using N bits from canonical Huffman encoded data;
means for extracting high-frequency symbols based on the direct-index lookup;
means for providing bracketing indices for low-frequency data based on the direct-index lookup;
means for performing a binary search using the bracketing indices to provide a low-frequency symbol index; and
means for extracting the low-frequency symbols associated with the low-frequency symbol index.
-
Specification