Flexible huffman tree approximation for low latency encoding
Techniques are described for encoding symbols using a new algorithm that provides a flexible Huffman tree approximation and that can be used for low latency encoding. For example, the new algorithm can perform encoding using one or more of the following phases: Shannon-based binning, code space optimization, tree completion, and code assignment.
1. A computing device comprising:
a processor; and
memory;
the computing device configured to perform operations for encoding a plurality of symbols, the operations comprising:
as part of a first phase, performing Shannon-based binning to determine initial code lengths for the symbols and place the symbols into corresponding code-length bins (CLBs) based on the determined initial code lengths;
as part of a second phase, performing code space optimization to shorten at least some of the symbols to shorter code-length bins; and
as part of a third phase, assigning prefix codes to the symbols based at least in part on the code-length bins.
2. The computing device of claim 1 , wherein performing Shannon-based binning comprises:
assigning each symbol to one of the code-length bins that corresponds to its Shannon code length; and
dividing the code-length bins into quantization intervals.
3. The computing device of claim 1 , wherein performing Shannon-based binning comprises:
dividing each of the code-length bins into a plurality of quantization intervals;
wherein each symbol is assigned to one of the quantization intervals within one of the code-length bins.
4. The computing device of claim 3 , wherein performing Shannon-based binning comprises:
maintaining a count of symbols that have been placed into each of the quantization intervals in each of the code-length bins.
5. The computing device of claim 1 , wherein performing code space optimization comprises:
for each of one or more code-length bins:
moving one or more most frequently occurring symbols in the code-length bin to a next shorter code-length bin which has a shorter code length.
6. The computing device of claim 1 , wherein each code-length bin is divided into a plurality of quantization intervals, and wherein performing code space optimization comprises:
for each of one or more code-length bins:
moving one or more symbols in the code-length bin that are associated with a most frequent quantization interval to a next shorter code-length bin which has a shorter code length.
7. The computing device of claim 1 , wherein performing code space optimization comprises:
determining whether remaining code space is greater than zero;
when remaining code space is greater than zero, performing code space optimization comprising moving at least one symbol to a next shorter code-length bin;
when remaining code space is equal to zero, proceeding to a next phase without moving any symbols.
8. The computing device of claim 1 the operations further comprising:
as part of a new phase after the second phase and before the third phase, performing tree completion by processing a binary tree representing the symbols to transform the binary tree into a full binary tree.
9. The computing device of claim 8 , wherein processing the binary tree comprises:
promoting nodes lower in the binary tree to fill in missing nodes higher in the binary tree.
10. The computing device of claim 1 , the operations further comprising:
receiving the plurality of symbols representing data to be compressed, wherein the plurality of symbols were generated from a deflate algorithm.
11. The computing device of claim 1 , wherein the prefix codes are assigned according to canonical Huffman coding.
12. The computing device of claim 1 , wherein the operations are performed by a field-programmable gate array (FPGA) or application-specific integrated circuits (ASIC) of the computing device.
13. A method, implemented by a computing device, for encoding a plurality of symbols, the method comprising:
performing Shannon-based binning to determine initial code lengths for the symbols and place the symbols into corresponding code-length bins (CLBs) based on the determined initial code lengths;
performing code space optimization to shorten at least some of the symbols to shorter code-length bins; and
assigning prefix codes to the symbols based at least in part on the code-length bins.
14. The method of claim 13 , wherein performing Shannon-based binning comprises:
assigning each symbol to one of the code-length bins that corresponds to its Shannon code length; and
dividing the code-length bins into quantization intervals.
15. The method of claim 13 , wherein performing Shannon-based binning comprises:
dividing each of the code-length bins into a plurality of quantization intervals;
wherein each symbol is assigned to one of the quantization intervals within one of the code-length bins.
16. The method of claim 13 , wherein performing Shannon-based binning comprises:
maintaining a count of symbols that have been placed into each of the quantization intervals in each of the code-length bins.
17. The method of claim 13 , wherein performing code space optimization comprises:
for each of one or more code-length bins:
moving one or more most frequently occurring symbols in the code-length bin to a next shorter code-length bin which has a shorter code length.
18. The method of claim 13 , wherein each code-length bin is divided into a plurality of quantization intervals, and wherein performing code space optimization comprises:
for each of one or more code-length bins:
moving one or more symbols in the code-length bin that are associated with a most frequent quantization interval to a next shorter code-length bin which has a shorter code length.
19. A method, implemented by a computing device, for encoding a plurality of symbols, the method comprising:
receiving symbol information generated from input data, wherein the symbol information comprises the symbols and their associated frequencies;
as part of a first phase, performing Shannon-based binning to determine initial code lengths for the symbols and place the symbols into corresponding code-length bins (CLBs) based on the determined initial code lengths;
as part of a second phase, performing code space optimization to shorten at least some of the symbols to shorter code-length bins;
as part of a third phase, performing tree completion by processing a binary tree representing the symbols to transform the binary tree into a full binary tree;
as part of a fourth phase, assigning prefix codes to the symbols based at least in part on the code-length bins; and
encode the input data using the assigned prefix codes to generate compressed output data.
20. The method of claim 19 , wherein performing Shannon-based binning comprises:
assigning each symbol to one of the code-length bins that corresponds to its Shannon code length; and
dividing the code-length bins into quantization intervals.