Efficient dictionary for lossless compression

• US 10,128,868 B1
• Filed: 12/29/2017
• Issued: 11/13/2018
• Est. Priority Date: 12/29/2017
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Gopal, Vinodh, Guilford, James D., Chen, Yen-Kuang
• Primary Examiner(s): Jeanglaude, Jean B
• Application Number:
  US15/858,964
• Time in Patent Office: 319 Days
• Field of Search: 341 50, 341 51, 341106
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/6011 Encoder aspects

Abstract

Various systems and methods for lossless data compression are described herein. A process for lossless data compression includes hashing an input byte stream to produce a hash key; identifying a set of dictionary entries in a hash table using the hash key, the hash key associated with a word from a compact dictionary; identifying a set of candidate words from the compact dictionary based on the identified set of dictionary entries, the compact dictionary being a subset of a standard dictionary; determining a best match of the set of candidate words with the input byte stream; and encoding the best match of the set of candidate words as a compressed output of the input byte stream, the encoding including an operation to determine an index into the standard dictionary of the best match and using the index in the encoding operation.

Claims

1. A system for lossless data compression, the system comprising:

one or more hash engines to perform a respective hash on an input byte stream, the respective hashes producing respective hash keys for each hash engine of the one or more hash engines, the hash keys mapped to dictionary entries in one or more memory devices to store a corresponding one or more hash tables, each hash table associated with a respective hash engine;

the one or more memory devices to store a corresponding one or more compact dictionaries, each compact dictionary associated with a respective hash engine, each compact dictionary including a plurality of words, each word having a specific distance into the compact dictionary, and the one or more compact dictionaries being a subset of a standard dictionary;

one or more comparator circuits, each comparator circuit associated with a respective hash engine and compact dictionary, and to compare a word from the respective compact dictionary with the input byte stream hashed by the respective hash engine to create a match score, the one or more comparator circuits to identify a selected word; and

an encoder circuit to encode the selected word from the respective compact dictionary, wherein to encode the selected word includes an operation to determine an index into the standard dictionary of the selected word and use the index in the encoding.

2. The system of claim 1, wherein the one or more hash engines comprises multiple hash engines to operate in parallel, each of the one or more hash engines to perform their respective hashes on a portion of the input byte stream.

3. The system of claim 2, wherein each respective hash engine performs their respective hashes on an incrementally larger portion of the input byte stream.

4. The system of claim 2, wherein the one or more hash engines comprises twenty-one hash engines, and the hash engines are to operate on byte lengths in the range of four to twenty-four from the input byte stream.

5. The system of claim 1, wherein the one or more memory devices comprises multiple distinct devices to store the one or more hash tables.

6. The system of claim 1, wherein dictionary entries includes a single entry.

7. The system of claim 1, wherein dictionary entries includes multiple entries.

8. The system of claim 1, wherein the one or more memory devices comprises multiple distinct devices to store the one or more compact dictionaries.

9. The system of claim 1, wherein the one or more compact dictionaries comprises a single dictionary.

10. The system of claim 1, wherein the one or more compact dictionaries comprises multiple compact dictionaries, each compact dictionary including words of a specific length, the specific length corresponding to a hash engine from the one or more hash engines that is to operate on a string of the specific length.

11. The system of claim 1, wherein the one or more comparator circuits comprises multiple comparator circuits, each comparator circuit corresponding to a hash engine from the one or more hash engines.

12. The system of claim 1, wherein the encoder circuit is to select a candidate word from a plurality of candidate words from the one or more comparator circuits.

13. The system of claim 1, wherein the encoder circuit is to select a candidate word from a plurality of candidate words, the plurality of candidate words provided by a plurality of comparator circuits from the one or more comparator circuits.

14. The system of claim 13, wherein the encoder circuit is to select the candidate word from the plurality of candidate words by evaluating the plurality of candidate words from longest to shortest, terminating the evaluation when a match is found.

15. The system of claim 1, wherein the encoder circuit is to select a candidate word from a plurality of candidate words from the one or more comparator circuits by selecting a word having the highest match score of the plurality of candidate words.

16. The system of claim 1, wherein the standard dictionary is a Brotli dictionary.

17. A method for lossless data compression, the method comprising:

hashing an input byte stream to produce a hash key;

identifying dictionary entries in a hash table using the hash key, the hash key associated with a word from a compact dictionary;

identifying candidate words from the compact dictionary based on the identified set of dictionary entries, the compact dictionary being a subset of a standard dictionary;

determining a best match of candidate words with the input byte stream; and

encoding the best match of candidate words as a compressed output of the input byte stream, the encoding including an operation to determine an index into the standard dictionary of the best match and using the index in the encoding operation.

18. The method of claim 17, wherein hashing the input byte stream is performed by a plurality of hash engines operating in parallel, each of the plurality of hash engines to perform their respective hashes on a portion of the input byte stream.

19. The method of claim 18, wherein each respective hash engine performs their respective hashes on an incrementally larger portion of the input byte stream.

20. The method of claim 18, wherein the plurality of hash engines comprises twenty-one hash engines, and the hash engines are to operate on byte lengths in the range of four to twenty-four from the input byte stream.

21. The method of claim 18, wherein the compact dictionary comprises multiple subset compact dictionaries, each subset compact dictionary including words of a specific length, the specific length corresponding to a hash engine from the plurality of hash engines that is to operate on a string of the specific length.

22. The method of claim 17, wherein determining the best match comprises:

evaluating the plurality of candidate words from longest to shortest; and

terminating the evaluation when the best match is found.

23. The method of claim 17, wherein the standard dictionary is a Broth dictionary.

24. At least one machine-readable medium including instructions for lossless data compression, the instructions when executed by a machine, cause the machine to perform the operations comprising:

hashing an input byte stream to produce a hash key;

identifying dictionary entries in a hash table using the hash key, the hash key associated with a word from a compact dictionary;

identifying candidate words from the compact dictionary based on the identified set of dictionary entries, the compact dictionary being a subset of a standard dictionary;

determining a best match of candidate words with the input byte stream; and

encoding the best match of candidate words as a compressed output of the input byte stream, the encoding including an operation to determine an index into the standard dictionary of the best match and using the index in the encoding operation.

25. The machine-readable medium of claim 24, wherein hashing the input byte stream is performed by a plurality of hash engines operating in parallel, each of the plurality of hash engines to perform their respective hashes on a portion of the input byte stream.