Semi-dynamic, low latency compression
Methods and apparatus are described by which data is compressed using semi-dynamic Huffman code generation. Embodiments generate symbol statistics over a portion of data. The symbol statistics are expanded to include all possible literals that could appear within the data. Any literal or reference added to the statistics may be given a frequency of one. The statistics are used to generate a semi-dynamic Huffman code. The entire data is then compressed using the semi-dynamic Huffman code.
1. An apparatus comprising:
a hardware matcher circuit to:
encode a preamble of data into a plurality of tokens, the data to include remainder data, each token to include a symbol and a length of the symbol; and
generate symbol frequency statistics to indicate a number of times the symbol appears within the preamble of data;
a Huffman table generator circuit to generate a Huffman code from the plurality of tokens and the symbol frequency statistics; and
an encoder circuit to compress the remainder data using the Huffman code.
2. The apparatus of claim 1 , the hardware matcher circuit to add a second plurality of tokens with a symbol frequency of one, the plurality of tokens and the second plurality of tokens to include all possible literals within the data.
3. The apparatus of claim 1 , the Huffman table generator circuit to add a second plurality of tokens with a symbol frequency of one, the plurality of tokens and the second plurality of tokens to include all possible literals within the data.
4. The apparatus of claim 3 , the encoder circuit to compress the preamble of data.
5. The apparatus of claim 3 , further comprising:
a buffer to store the plurality of tokens; and
a transcoder to transcode the plurality of tokens using the Huffman codes, the encoder circuit to compress only the remainder data.
6. The apparatus of claim 1 , a file to include a plurality of chunks of data, and wherein the data is one chunk of data.
7. The apparatus of claim 6 , wherein each chunk of data is compressed.
8. The apparatus of claim 7 , wherein at least two chunks of data are one megabyte in size.
9. The apparatus of claim 1 , wherein the preamble of data is no more than 5% of a size of the data.
10. The apparatus of claim 9 , wherein the preamble of data is 32 kilobytes.
11. The apparatus of claim 9 , wherein the preamble of data is 64 kilobytes.
12. The apparatus of claim 9 , wherein the preamble of data is 96 kilobytes.
13. A machine-implemented method comprising:
encoding a preamble of data into a plurality of tokens, the data to include remainder data, each token to include a symbol and a length of the symbol;
generating symbol frequency statistics to indicate a number of times the symbol appears within the preamble of data;
generating a Huffman code from the plurality of tokens and the symbol frequency statistics; and
compressing the remainder data using the Huffman code.
14. The method of claim 13 , further comprising generating the Huffman codes from a second plurality of tokens with a symbol frequency of one, the plurality of tokens and the second plurality of tokens to include all possible literals within the data.
15. The method of claim 14 , further comprising compressing the preamble of data.
16. The method of claim 14 , further comprising:
storing, in a buffer, the plurality of tokens;
transcoding the plurality of tokens using the Huffman codes; and
compressing only the remainder data.
17. The method of claim 13 , a file to include a plurality of chunks of data, and wherein the data is one chunk of data.
18. The method of claim 17 , wherein each chunk of data is compressed.
19. The method of claim 18 , wherein at least two chunks of data are one megabyte in size.
20. The method of claim 17 , wherein the preamble of data is no more than 5% of a size of the data.
21. At least one non-transitory computer-readable medium, including instructions, which when executed by a machine, cause the machine to perform operations:
encoding a preamble of data into a plurality of tokens, the data to include remainder data, each token to include a symbol and a length of the symbol;
generating symbol frequency statistics to indicate a number of times the symbol appears within the preamble of data;
generating a Huffman code from the plurality of tokens and the symbol frequency statistics; and
compressing the remainder data using the Huffman code.
22. The at least one computer-readable medium of claim 21 , the operations further comprising generating the Huffman codes from a second plurality of tokens with a symbol frequency of one, the plurality of tokens and the second plurality of tokens to include all possible literals within the data.
23. The at least one computer-readable medium of claim 22 , the operations further comprise compressing the preamble of data.
24. The at least one computer-readable medium of claim 22 , the operations further comprising:
storing, in a buffer, the plurality of tokens;
transcoding the plurality of tokens using the Huffman codes; and
compressing only the remainder data.
25. The at least one computer-readable medium of claim 21 , wherein a file comprises a plurality of chunks of data, and wherein the data is one chunk of data.