Data compression apparatus and method
First Claim
1. A method for converting an input data stream into an encoded data character stream, said data stream including data characters, said method comprising the steps of:
- storing data characters into a data storage means for reference,performing a search in said data storage means for a data character string of said stored data characters which match said input data stream, andencoding a length and an offset position within said data storage means of one of said matching strings found by said search in said data storage means, wherein said offset position is encoded with a tag bit indicating either a short or a long offset, and with a predetermined number of bits indicating the location within said data storage means where said matching string is located.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
14 Claims
-
1. A method for converting an input data stream into an encoded data character stream, said data stream including data characters, said method comprising the steps of:
-
storing data characters into a data storage means for reference, performing a search in said data storage means for a data character string of said stored data characters which match said input data stream, and encoding a length and an offset position within said data storage means of one of said matching strings found by said search in said data storage means, wherein said offset position is encoded with a tag bit indicating either a short or a long offset, and with a predetermined number of bits indicating the location within said data storage means where said matching string is located. - View Dependent Claims (2, 3)
-
-
4. An apparatus for converting an input data stream into an encoded data character stream, said data stream including data characters, said apparatus comprising:
-
means for storing data characters for reference, means for performing a search in said storing means for a data character string of said stored data characters which match said input data stream, and means for encoding a length and an offset position within said storing means of one of said matching strings found by said search in said storing means, wherein said offset position is encoded with a tag bit indicating either a short or a long offset, and with a predetermined number of bits indicating the location within said storing means where said matching string is located. - View Dependent Claims (5)
-
-
6. The apparatus of claim 33, wherein said means for encoding said offset position further comprises:
-
means for indicating the location within said storing means where said matching string is located with seven bits, and means for indicating the location within said storing means where said matching string is located with eleven bits.
-
-
7. A method for converting an input data stream into a variable length encoded data character stream in a data compression system, said data stream including data characters, said data compression system comprising a storage means for storing input data characters of said input data character stream, said method comprising the steps of:
-
performing a search in said storage means for a data character string which matches said input data stream; operative when said matching data character string is found within said storage means, 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 pointer indicating the location within said storage means of said matching data character string, and said step of encoding said matching data character string including the step of representing said pointer and said variable length indicator by an encoding scheme according to a predetermined strategy, said predetermined strategy ensuring that a matching data character string of two data characters of said input data character stream is compressed to less than said two data characters of said input data character stream; operative when said matching input data character string is not found within said storage means, encoding a first character of said input data character stream by assigning a "raw" data tag indicating that no matching data character was found in said storage means and appending said first character of said input data character stream. - View Dependent Claims (8, 9, 10)
-
-
11. An apparatus for converting an input data stream into a variable length encoded data character stream, said data stream including data characters, said apparatus comprising:
-
a storage means for storing input data characters of said input data character stream; means for performing a search in said storage means for a data character string which matches said input data stream; means for 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 pointer indicating the location within said storage means of said matching data character string, said means for encoding said matching data character string including means for representing said pointer and said variable length indicator by an encoding scheme according to a predetermined strategy, said predetermined strategy ensuring that a matching data character string of two data characters of said input data character stream is compressed to less than said two data characters of said input data character stream; means for encoding a first character of said input data character stream by assigning a "raw" data tag indicating that no matching data character was found in said storage means and appending said first character of said input data character stream. - View Dependent Claims (12, 13, 14)
-
Specification