Data compression apparatus and method

• US 5,463,390 A
• Filed: 07/21/1994
• Issued: 10/31/1995
• Est. Priority Date: 01/13/1989
• Status: Expired due to Fees

• Current Assignee: Hifn, Inc. (Maxlinear Incorporated)
• Original Assignee: STAC Electronics Incorporated
• Inventors: Whiting, Douglas L., Ivey, Glen E., George, Glen A.
• Primary Examiner(s): Hoff, Marc S.
• Application Number:
  US08/279,714
• Time in Patent Office: 467 Days
• Field of Search: 341/51, 341/67, 341/95, 341/106
• US Class Current: 341/51
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• 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

An apparatus and method are disclosed for converting an input data character stream into a variable length encoded data stream in a data compression system. The data compression system includes a history array. The history array has a plurality of entries and each entry of the history array is for storing a portion of the input data stream. The method for converting the input data character stream includes the following steps. Performing a search in a history array for the longest data string which matches the input data string. If the matching data string is found within the history buffer, the next step includes encoding the longest matching data string found by appending to the encoded data stream a tag indicating the longest matching data string was found and a string substitution code. If the matching data string is not found within the history array, the next step includes encoding the first character of the input data string by appending to the encoded data stream a raw data tag indicating that no matching data string was found and the first character of the input data string.

Claims

1. A method for converting an input data character stream into a variable length encoded data stream, each of said input data characters of said input data character stream comprising an equal number of bits, said method comprising:

a) storing said input data characters into a storage means for reference,

b) performing a search in said storage means for a longest data character string of said input data characters which matches said input data character stream,

c) encoding said matching data character string by assigning a tag indicating that said matching data character string was found, a variable length indicator of the length of said matching data character string, and a variable length pointer indicating the location within said storage means of said matching data character string, said variable length pointer represented in a form that depends upon the location within said storage means of said matching data character string;

said tag, said variable pointer and said variable length indicator together comprising a plurality of bits;

said tag, said variable pointer, and said variable length indicator encoded according to a predetermined strategy;

said predetermined strategy enabling matching strings of two data characters to be encoded so that said plurality of bits of said tag, said variable pointer, and said variable length indicator does not exceed the number of bits of two of said input data characters of said input data stream,

d) encoding a character of said input data stream by assigning a tag indicating that no matching data string was found in said storage means and said input data character;

said tag and said encoded input data character together comprising a number of bits;

said number of bits of said tag and said encoded input data character exceeding the number of bits of one of said input data characters of said input data stream.

2. The method of claim 1, wherein said step of performing said search in said storage means for a longest data character string further includes the step of performing a predetermined number of additional searches in said data storage means for data character strings of said storage data characters which match said input data stream.

3. The method of claim 1 further including the steps of:

discarding input data characters of said input data stream which have been encoded performing one or more steps of said method for further encoding said input data stream.

4. The method of claim 1 wherein said step of performing said search in said storage means for a longest data character string further includes the step of performing a hashing function.

5. The method of claim 4 wherein said conversion of said input data character stream into said variable length encoded data stream occurs in data compression system and said data compression system includes said storage means, said storage means having a plurality of entries, said entries of said storage means for storing said input data stream, a storage means pointer, said storage means pointer indicating the latest entry in said storage means, and a hash table means having a plurality of entries, each entry of said hash table means for storing a pointer for indicating one of said entries of said storage means, further including the steps of:

said hashing function providing a pointer to one of said entries of said hash table means,

obtaining said pointer stored at said hash table entry pointed to by said result of said hashing function, and

storing said storing means pointer into said hash table entry pointed to by said hashing function.

6. The method of claim 5 further including the step of incrementing said storage means pointer to the next entry in said storage means and performing one or more elements of said method for hashing said next entry of said storage means.

7. The method of claim 1 further including the step of:

appending an end of compressed data marker which is detected during decompression of said variable length encoded data stream.

8. The method of claim 1 further including the step of decoding said variable length encoded data stream, said step including the steps of:

parsing said variable length encoded data stream into separate portions, each said separate portion starting with one of said tags,

evaluating said tag of each said separate portion for determining whether said tag indicates that said matching data character string was found in said storage means or that no matching data character string was found in said storage means.

9. The method of claim 8 further including the step:

interpreting said variable length indicator of the length of said matching data character string and said variable length pointer indicating the location within said storage means of said matching data character string for generating said matching data character string, thereby reconstructing a portion of the original input data character stream.

10. The method of claim 8 further including the step:

obtaining said encoded input data character of said encoded input data stream, thereby reconstructing a portion of the original input data character stream.

11. A method for converting a variable length encoded input data stream into an output data character stream in a data decompression system, said data decompression system comprising a storage means, said storage means having a plurality of entries, said entries of said storage means for storing said output data character stream, said method comprising the steps of:

parsing said variable length encoded input data stream into separate portions, each said separate portion starting with a tag,

evaluating said tag of each said separate portion for determining whether said tag indicates that said matching data character string was found in said storage means or that no matching data character string was found in said storage means,

obtaining an encoded input data character of said encoded input data stream, outputting said input data character, placing said input data character in said storage means, and

obtaining a variable length indicator of the length of said matching data character string and a variable length pointer indicating the location within said storage means of said matching data character string, outputting said matching data character string at said location within said storage means for said length, and placing said matching data character string in said storage means.

12. An apparatus for converting an input data character stream into a variable length encoded data stream, each of said input data characters of said input data character stream comprising an equal number of bits, said apparatus comprising:

a) storage means for storing said input data characters for reference,

b) means for performing a search in said storage means for a longest data character string of said input data characters which matches said input data character stream,

c) means for encoding a matching data character string by assigning a tag indicating that said matching data character string was found, a variable length indicator of the length of said matching data character string, and a variable length pointer indicating the location within said storage means of said matching data character string, said variable length pointer represented in a form that depends upon the location within said storage means of said matching data character string;

said tag, said variable pointer and said variable length indicator together comprising a plurality of bits;

said tag, said variable pointer, and said variable length indicator encoded according to a predetermined strategy;

said predetermined strategy enabling matching strings of two data characters to be encoded so that said plurality of bits of said tag, said variable pointer, and said variable length indicator does not exceed the number of bits of two of said input data characters of said input data stream,

d) means for encoding a character of said input data stream by assigning a tag indicating that no matching data string was found in said storage means and said input data character;

said tag and said encoded input data character together comprising a number of bits;

said number of bits of said tag and said encoded input data character exceeding the number of bits of one of said input data characters of said input data stream.

13. The apparatus of claim 12, further comprising:

means for performing a predetermined number of additional searches in said data storage means for data character strings of said stored data characters which match said input data stream.

14. The apparatus of claim 12, further comprising:

means for discarding input data characters of said input data stream which have been encoded.

15. The apparatus of claim 12, wherein said means for performing said search in said storage means for a longest data character string further includes means for performing a hashing function.

16. The apparatus of claim 15, wherein said storage means has a plurality of entries, said entries of said storage means for storing said input data stream, said apparatus further comprising:

a storage means pointer, said storage means pointer indicating the latest entry in said storage means,

a hash table means having a plurality of entries, each entry of said hash table means for storing a pointer for indicating one of said entries of said storage means,

said means for performing a hashing function providing a pointer to one of said entries of said hash table means,

means for obtaining said pointer stored at said hash table entry pointed to by said result of said hashing function, and

means for storing said storage means pointer into said hash table entry pointed to by said hashing function.

17. The apparatus of claim 16, further comprising:

means for incrementing said storage means pointer to the next entry in said storage means.

18. The apparatus of claim 12, further comprising:

means for appending an end of compressed data marker which is detected during decompression of said variable length encoded data stream.

19. The apparatus of claim 12, further comprising means for decoding said variable length encoded data stream, said decoding means comprising:

means for parsing said variable length encoded data stream into separate portions, each said separate portion starting with one of said tags,

means for evaluating said tag of each said separate portion for determining whether said tag indicates that said matching data character string was found in said storage means or that no matching data character string was found in said storage means.

20. The apparatus of claim 19, further comprising:

means for interpreting said variable length indicator of the length of said matching data character string and said variable length pointer indicating the location within said storage means of said matching data character string for generating said matching data character string, thereby reconstructing a portion of the original input data character stream.

21. The apparatus of claim 19, further comprising:

means for obtaining said encoded input data character of said encoded input data stream, thereby reconstructing a portion of the original input data character stream.

22. An apparatus for converting a variable length encoded input data stream into an output data character stream in a data decompression system, said data decompression system comprising a storage means, said storage means having a plurality of entries, said entries of said storage means for storing said output data character stream, said method comprising the steps of:

means for parsing said variable length encoded input data stream into separate portions, each said separate portion starting with a tag,

means for evaluating said tag of each said separate portion for determining whether said tag indicates that said matching data character string was found in said storage means or that no matching data character string was found in said storage means,

means for obtaining an encoded input data character of said encoded input data stream, outputting said input data character, placing said input data character in said storage means, and

means for obtaining a variable length indicator of the length of said matching data character string and a variable length pointer indicating the location within said storage means of said matching data character string, outputting said matching data character string at said location within said storage means for said length, and placing said matching data character string in said storage means.