Compression using small dictionaries with applications to network packets

• US 5,389,922 A
• Filed: 04/13/1993
• Issued: 02/14/1995
• Est. Priority Date: 04/13/1993
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Seroussi, Gadiel, Lempel, Abraham
• Primary Examiner(s): Logan, Sharon D.
• Application Number:
  US08/046,548
• Time in Patent Office: 672 Days
• Field of Search: 341/51, 341/106, 341/52, 341/55, 341/87, 341/90, 341/94, 341/95
• US Class Current: 341/51
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

Abstract

The invention is a dictionary initialization scheme adaptive to changes in the type and structure of input data. The compression ratio is increased by minimizing the number of data entries used to represent single characters in the input data. By using fewer codes than what is normally used to represent characters in an array of input data, the dictionary can have fewer entries than the alphabet size. A further aspect of the invention implements a type of run-length encoding in the LZ methodology which exploits the redundant structure existing in the compressed stream in the presence of a long run. Some of the codewords in the compressed stream are deleted but can be recovered at the decompression site. The foregoing LZE method is used alone, or used in combination with other methods to form a compression scheme that is especially useful for transmitting network packets.

Claims

1. A method for encoding input data in a dictionary based compression/decompression system comprising:

storing unique multiple character strings from the input data as dictionary entries in the compression/decompression system;

encoding multi-character strings from the input data into codewords according to the address of dictionary entries matching the character strings;

identifying single-character strings from the input data that have not previously been stored in the compression/decompression dictionary;

encoding each single-character string into a special code and a partial code, each special and partial code representing a selectable portion of the associated single-character string; and

outputting a compressed data stream from the compression/decompression system having both the codewords corresponding to the encoded single-character strings and the codewords corresponding to the encoded multiple character strings, each special code and associated partial code uniquely identifying a single-character string and representing a subset of the total number of unique single-character strings that can exist in the input data.

2. An encoding method according to claim 1 including encoding the special code for each single-character string in the compressed data stream according to a selectable parameter k that determines how many bits of the single character are contained in the special code.

3. An encoding method according to claim 2 including reconstructing single character strings from the compressed data stream, the reconstruction process comprising:

identifying a special code in the compressed data stream;

decoding the special code back into an original portion of the associated single character string; and

combining the special code with its associated partial code.

4. An encoding method according to claim 1 wherein the special code is encoded to exist within a predefined range of code values generated by the compression/decompression system.

5. An encoding method according to claim 1 wherein encoding single-character strings comprise allocating a subset of bits from the single character string to the special code, and allocating the remaining bits from the single character to the partial code, the number of bits in the special code being determined by the number of codewords allotted in the compression/decompression system to represent single character strings.

6. An encoding method according to claim 5 wherein the number of bits assigned to the special codes of the single character strings are changed according to the type and structure of the input data.

7. An encoding method according to claim 1 including detecting a run of consecutive codewords in the compressed data stream, each codeword in the run representing a string of input data made up from the same character.

8. An encoding method according to claim 7 including compressing the run of codewords from the compressed data stream.

9. An encoding method according to claim 7 including disabling the compression/decompression system from outputting part of the codeword run in the compressed data stream.

10. An encoding method according to claim 9 wherein the value of the first codeword sent following the disabled codewords allows for reconstruction of the sequence of disabled codewords.

11. An encoding method according to claim 7 including simultaneously compressing the input data with at least one additional compression scheme and selecting the compressed data stream from the scheme that provides the best compression ratio.

12. An encoding method according to claim 11 including selecting the uncompressed input data characters when the input data size smaller than each compressed data stream.

13. An encoding method according to claim 1 wherein the total number of unique single character strings is larger than the total number of dictionary entries in the compression/decompression system.

14. An encoding method according to claim 1 wherein the number of unique single character strings is 2¹⁶.

15. A method for encoding input data in a dictionary based compression/decompression system comprising:

encoding character strings from the input data and storing unique character strings as data entries in the compression/decompression dictionary;

outputting a compressed data stream from the compression/decompression system, the compressed data stream made up of codewords representing the encoded character strings;

detecting a sequence of codewords in the compressed data stream that represent a run of input data characters, the run representing input data characters having the same value and processed by the compression/decompression system in sequential order; and

compressing the compressed data stream by disabling the compression/decompression system from outputting part of the codeword run in the compressed data stream;

the value of the first codeword sent following the disabled codewords allowing for reconstruction of the sequence of disabled codewords.

16. An encoding method according to claim 15 wherein the run is detected by comparing the encoded value output from the compression/decompression system with the memory location of the last data entry stored in the compression/decompression dictionary.

17. An encoding method according to claim 16 including disabling the compression/decompression system from outputting encoded character strings until the last encoded value output from the compression/decompression system no longer equals the address value of the last character string stored in the dictionary.

18. An encoding method according to claim 15 including decompressing the first codeword sent following the disabled codewords into codewords that are further decompressed into decompressed data by the compression/decompression system.

19. A circuit for encoding input data in a dictionary based compression/decompression system comprising:

a compression/decompression engine for encoding single and multiple character strings from the input data into codewords and outputting the codewords as a compressed data stream;

means for separating single-character strings from the input data into first and second code fields;

means for encoding the first code field to identify single-character strings in the compressed data stream, the first code field encoded to be within a predefined range of compression/decompression engine code values; and

means for generating single-character strings from the compressed data stream by decoding the first code field and combining it with the second code field, the first and second code fields reducing the bit-length of encoded character strings by representing a subset of all single-character strings that can possibly occur in the input data.

20. A circuit according to claim 19 wherein the encoding means sums a selectable number of bits from the first code field with a predefined value.

21. A circuit according to claim 19 wherein the decoder subtracts a predefined value from the first code field and combines a selectable number of bits from the result with the second field.

22. A circuit according to claim 19 including an encoder run enhancement engine coupled to the compression/decompression engine for disabling the compression/decompression engine from outputting some of the codewords in the compressed data stream.

23. A circuit according to claim 22 including a decoder run enhancement engine coupled to the compression/decompression engine for reconstructing the sequence of disabled codewords from the value of the first codeword sent following the disabled codewords.