Fast approximate dynamic Huffman coding with periodic regeneration and precomputing

1. An approximate dynamic Huffman coding method for use in a computing system, the method comprising in any order:

using precomputation-based Huffman coding for encoding or decoding of a plurality of tokens

collecting statistics about the frequency with which each token is used

periodically regenerating the Huffman coding tree and precomputed information; and

using information precomputed from the Huffman coding tree.

2. The method of claim 1 , further comprising:

precomputing the code and number of bits for each node in the Huffman coding tree; and

encoding a plurality of tokens, the encoding for each token comprising:

looking up a node corresponding to the token

outputting a code for the token using the precomputed code and number of bits stored in the node; and

for at least some tokens output, checking whether the coding tree should be regenerated, and if so, encoding a special code, regenerating the Huffman coding tree and precomputed information, determining when to next regenerate the coding tree, and encoding the token.

3. The method of claim 2 , further comprising:

checking whether the length of the code to be output exceeds the size of the code field, and if so, using a parent field to send the code for one or more parents of the node before sending the code for the node itself.

4. The method of claim 1 , further comprising:

precomputing a ‘fastdecode’ table

precomputing a used number of bits value for each node

decoding a plurality of tokens, the decoding for each token comprising:

reading a plurality of bits from the input without removing them from the input

using a plurality of the bits to index the ‘fastdecode’ table to obtain the node corresponding to those bits

checking if the node is a non-leaf node, and if so, using following bits in the input to find a leaf node in the input

determining the number of bits of the input that were actually used in decoding the token, and

consuming those bits from the input; and

checking whether the decoded token is the special token indicating Huffman coding tree regeneration, and if so, regenerating the Huffman coding tree, recomputing the precomputed information, and repeating the decoding step.

5. A computing system comprising a means for using approximate dynamic Huffman coding with periodic regeneration and recomputing, the means comprising:

a precomputation-based Huffman coding means for encoding or decoding tokens

a means for collecting statistics about the frequency with which each token is used

a means for periodically regenerating the Huffman coding tree and precomputed information; and

a means for using information precomputed from the Huffman coding tree.

6. The computing system of claim 5 , further comprising:

a means for precomputing the code and number of bits for each node in the Huffman coding tree; and

a means for encoding a plurality of tokens, the means comprising:

a means for looking up a node corresponding to the token

a means for outputting a code for the token using the precomputed code and number of bits stored in the node; and

a means for checking, for at least some tokens output, whether the coding tree should be regenerated, and if so, encoding a special code, regenerating the Huffman coding tree and precomputed information, determining when to next regenerate the coding tree, and encoding the token.

7. The computing system of claim 5 , further comprising:

a means for precomputing a ‘fastdecode’ table

a means for precomputing a used number of bits value for each node

a means for decoding a plurality of tokens, the means comprising:

a means for reading a plurality of bits from the input without removing them from the input

a means for using a plurality of the bits to index the ‘fastdecode’ table to obtain the node corresponding to those bits

a means for checking if the node is a non-leaf node, and if so, using following bits in the input to find a leaf node in the input

a means for determining the number of bits of the input that were actually used in decoding the token, and

a means for consuming those bits from the input; and

a means for checking whether the decoded token is the special token indicating Huffman coding tree regeneration, and if so, regenerating the Huffman coding tree, recomputing the precomputed information, and reactivating the decoding means.

8. A computer usable software distribution medium having computer usable program code means embodied therein for causing a computer system to perform approximate dynamic Huffman coding with periodic regeneration and recomputing, the computer usable program code means in said computer usable software distribution medium comprising:

computer usable program code means for using precomputation-based Huffman coding for encoding or decoding a plurality of tokens

computer usable program code means for collecting statistics about the frequency with which each token is used

computer usable program code means for periodically regenerating the Huffman coding tree and precomputed information; and

computer usable program code means for using information precomputed from the Huffman coding tree.