Data compression apparatus and method

An apparatus for converting an input data character stream into a variable length encoded data stream in a data compression system, said data compression system comprising a history array means, said history array means having a plurality of entries, said entries of said history array means for storing said input data stream, a history array pointer, said history array pointer indicating a latest entry in said history array means, a hash table means having a plurality of entries, each entry of said hash table means for storing a pointer indicating one of said entries of said history array means, and an offset array means, said offset array means having a plurality of entries, each entry of said offset array means providing a link, if any, from one of said entries in said history array means to one or more other entries of said history array means, said apparatus comprising:

• means for performing a search in said history array means for a longest matching data string which matches said input data stream, said means for performing said search including:
• means for performing a hashing function on said input data stream, said hashing function providing a pointer indicating one of said entries of said hash table means,
• means for obtaining said pointer stored at said hash table entry pointed to by said hashing function,
• means for calculating a difference between said history array pointer and said pointer obtained from said hash table means,
• means for storing said difference into said offset array means entry pointed to by said history array pointer, and
• means for storing said history array pointer into said hash table entry pointed to by said hashing function,
• means for encoding said matching data string found in said history array means by assigning a tag indicating that said matching data string was found and a string substitution code including a variable length indicator of the length of said matching data string and a pointer indicating the location within said history array means of said matching data string,
• means for encoding a first character of said input data stream by assigning a "raw" data tag indicating that no matching data string was found is said history array means and said first character of said input data stream,
• whereby said input data stream is converted into a variable length encoded data stream.

A method for converting an input data character stream into a variable length encoded data stream, said method comprising the steps of:

• storing previously processed input data characters into a storage means for reference,
• performing a search in said data storage means for a longest data string of said previously processed input data characters which matches said input data stream,
• operative when said matching data string is found within said storage means, encoding said matching data string by assigning a tag indicating that said matching data string was found, a variable length indicator of the length of said matching data string, and a pointer indicating the location within said storage means of said matching data string, and said step of encoding said matching data 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 string of two characters of said input data stream is compressed to less than said two characters of said input data stream,
• operative when said matching input data string is not found within said storage means, encoding a first character of said input data stream by assigning a "raw" data tag indicating that no matching data string was found in said storage means and said first character of said input data stream,
• whereby said input data stream is converted into a variable length encoded data stream.

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, a storage means pointer, said storage means pointer indicating a latest entry in said storage means, 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 is a raw data tag or a tag indicating an encoded matching data string,
• operative when said tag is said raw data tag, parsing a raw data byte from said separate portion, outputting said raw data byte, placing said raw data byte in said storage means, and
• operative when said tag is said tag indicating an encoded matching data string, parsing a variable length indicator of the length of said matching data string and an offset indicating the location within said storage means of said matching data string, said separate portion being less than two characters of said output data character stream when said separate portion represents a matching data string of two characters, outputting said matching data string at said location within said storage means for said length, and placing said matching data string in said storage means.

An apparatus for converting an input data character stream into a variable length encoded data stream, said apparatus comprising:

• storage means for storing previously processed input data characters for reference,
• means for performing a search in said storage means for a longest data stream of said previously processed input data characters which matches said input data stream,
• means for encoding said matching data stream by assigning a tag indicating that said matching data string was found, a variable length indicator of the length of said matching data string, and a pointer indicating the location within said storage means of said matching data string, and 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 string of two characters of said input data stream is compressed to less than said two characters of said input data stream, and
• means for encoding a first character of said input data stream by assigning a "raw" data tag indicating that no matching data string was found in said storage means and said first character of said input data stream,
• whereby said input data stream is converted into a variable length encoded data stream.

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,
• a storage means pointer, said storage means pointer indicating a latest entry in said storage means,
• 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 is said a raw data tag or a tag indicating an encoded matching data string,
• means for parsing a raw data byte from said separate portion, means for outputting said raw data byte, means for placing said raw data byte in said storage means, and
• means for parsing a variable length indicator of the length of said matching data string and an offset indicating the location within said storage means of said matching data string, said separate portion being less than two characters of said output data character stream when said separate portion represents a matching data string of two characters, means for outputting said matching data string at said location within said storage means for said length, and means for placing said matching data string in said storage means.