Data compression apparatus and method

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.

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.

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.