LZW data compression and decompression apparatus and method using grouped data characters to reduce dictionary accesses

A data compression method for compressing an input stream of data characters into an output stream of compressed codes comprising

• storing strings of data characters encountered in said input stream, said stored strings having respective codes associated therewith, a string being stored as at least one grouping of a predetermined number of data characters concatenated with at most one less than said predetermined number of data characters, said grouping of said predetermined number of data characters defining a grouped character,
• in a compression cycle, forming said input stream into a plurality of consecutive grouped characters, each grouped character comprised of said predetermined number of data characters, thereby providing a formed input stream,
• determining the longest match between said formed input stream and said stored strings by comparing said formed input stream to said stored strings by sequentially matching said plurality of consecutive grouped characters of said formed input stream with said at least one grouped character of said stored strings until a mismatching grouped character of said formed input stream occurs, and then sequentially matching the data characters of said mismatching grouped character with said concatenated data characters of said stored strings until said longest match is determined,
• outputting the code associated with said longest match so as to provide said output stream of compressed codes,
• storing an extended string comprising said longest match extended hy the data character of said mismatching grouped character following said longest match, and
• assigning a code corresponding to said stored extended string,
• said step of forming said input stream including forming a new grouped character to begin the next compression cycle, said new grouped character comprising the data characters of said mismatching grouped character following said longest match concatenated by a number of next following data characters from said input stream so that said new grouped character comprises said predetermined number of data characters.

A data decompression method for decompressing an input stream of compressed codes to recover an output stream of data characters corresponding thereto comprising

• storing strings of data characters, said stored strings having respective codes associated therewith, a string being stored as a grouping of a predetermined number of data characters concatenated with at least one data character, said grouping of said predetermined number of data characters defining a grouped character, each said grouped character having associated therewith a code less than a predetermined code, each code associated with a stored string being greater than any code associated with a grouped character,
• in a decompression cycle, comparing a received compressed code to said predetermined code and if said received compressed code is less than said predetermined code,
• outputting the data characters of the grouped character corresponding to said received compressed code so as to provide said output stream of data characters,
• storing an extended string comprising the string corresponding to the compressed code received in the previous decompression cycle extended by the first data character of said grouped character corresponding to said received compressed code,
• said compressed code received in said previous decompression cycle defining a previous code, and
• assigning a code to said stored extended string, said code assigned to said stored extended string being greater than any code associated with said grouped characters.

A data decompression method for decompressing an input stream of compressed codes to recover an output stream of data characters corresponding thereto comprising

• storing strings of data characters in first and second storage means, said stored strings having respective codes associated therewith,
• a string being stored in said first storage means as a plurality of consecutive groupings of data characters, each said grouping comprising a predetermined number of data characters, said grouping of said predetermined number of data characters defining a grouped character, each said grouped character having associated therewith a code less than a predetermined code, each code associated with a stored string being greater than any code associated with a grouped character,
• a string being stored in said second storage means as a root code extended by at most one less than said predetermined number of data characters,
• at least one of said strings stored in said second storage means being stored as an extension of a string stored in said first storage means wherein said root code comprises the code associated with said string stored in said first storage means,
• at least one of said strings stored in said second storage means being stored as one grouped character extended by at most one less than said predetermined number of data characters wherein said root code comprises said one grouped character,
• maintaining a table of the codes associated with strings stored in a particular one of said first and second storage means,
• in a decompression cycle,
• receiving a compressed code,
• outputting the data characters of a string of data characters corresponding to said received compressed code so as to provide said output stream of data characters,
• setting a temporary flag in accordance with said string corresponding to said received compressed code, said temporary flag indicating one of said first and second storage means into which to store an extended string in the next decompression cycle,
• storing an extended string in one of said first and second storage means in accordance with an update flag indicating into which of said first and second storage means to store said extended string, said extended string based on the string corresponding to the compressed code received in the previous decompression cycle,
• said compressed code received in said previous decompression cycle defining a previous code,
• assigning a code to said stored extended string, said code assigned to said stored extended string being greater than any code associated with said grouped characters,
• said maintaining step including listing said code assigned to said stored extended string in said table if said extended string is stored in said particular one of said first and second storage means, and
• transferring said temporary flag to said update flag.

Data compression apparatus for compressing an input stream of data characters into an output stream of compressed codes comprising

• means for storing strings of data characters encountered in said input stream, said stored strings having respective codes associated therewith, a string being stored as a grouping of a predetermined number of data characters concatenated with at least one data character, said grouping of said predetermined number of data characters defining a grouped character,
• means operative in a compression cycle for forming said input stream into a grouped character comprised of said predetermined number of data characters followed by at least one data character, thereby providing a formed input stream,
• means for determining the longest match between said formed input stream and said stored strings by comparing said formed input stream to said stored strings by matching said grouped character of said formed input stream with said grouped character of said stored strings and sequentially matching said at least one data character of said formed input stream with said at least one data character of said stored strings until one of the data characters of said formed input stream causes a mismatch to occur,
• means for outputting the code associated with said longest match so as to provide said output stream of compressed codes,
• means for storing an extended string comprising said longest match extended by said data character that caused said mismatch, and
• means for assigning a code corresponding to said stored extended string,
• said means for forming said input stream including means for forming a new grouped character to begin the next compression cycle, said new grouped character comprising said data character that caused said mismatch concatenated hy one less than said predetermined number of the next following data characters from said input stream.

Data compression apparatus for compressing an input stream of data characters into an output stream of compressed codes comprising

• means for storing strings of data characters encountered in said input stream, said stored strings having respective codes associated therewith, a string being stored as at least one grouping of a predetermined number of data characters concatenated with at most one less than said predetermined number of data characters, said grouping of said predetermined number of data characters defining a grouped character,
• means operative in a compression cycle for forming said input stream into a plurality of consecutive grouped characters, each grouped character comprised of said predetermined number of data characters, thereby Providing a formed input stream,
• means for determining the longest match between said formed input stream and said stored strings by comparing said formed input stream to said stored strings by sequentially matching said plurality of consecutive grouped characters of said formed input stream with said at least one grouped character of said stored strings until a mismatching grouped character of said formed input stream occurs, and then sequentially matching the data characters of said mismatching grouped character with said concatenated data characters of said stored strings until said longest match is determined,
• means for outputting the code associated with said longest match so as to provide said output stream of compressed codes,
• means for storing an extended string comprising said longest match extended by the data character of said mismatching grouped character following said longest match, and
• means for assigning a code corresponding to said stored extended string,
• said means for forming said input stream including means for forming a new grouped character to begin the next compression cycle, said new grouped character comprising the data characters of said mismatching grouped character following said longest match concatenated by a number of next following data characters from said input stream so that said new grouped character comprises said predetermined number of data characters.

Data decompression apparatus for decompressing an input stream of compressed codes to recover an output stream of data characters corresponding thereto comprising

• means for storing strings of data characters, said stored strings having respective codes associated therewith, a string being stored as a grouping of a predetermined number of data characters concatenated with at least one data character, said grouping of said predetermined number of data characters defining a grouped character, each said grouped character having associated therewith a code less than a predetermined code, each code associated with a stored string being greater than any code associated with a grouped character,
• said apparatus operative in a decompression cycle to comparing a received compressed code to said predetermined code and if said received compressed code is less than said predetermined code, to
• output the data characters of the grouped character corresponding to said received compressed code so as to provide said output stream of data characters,
• store an extended string comprising the string corresponding to the compressed code received in the previous decompression cycle extended by the first data character of said grouped character corresponding to said received compressed code,
• said compressed code received in said previous decompression cycle defining a previous code, and
• assign a code to said stored extended string, said code assigned to said stored extended string being greater than any code associated with said grouped characters.

Data decompression apparatus for decompressing an input stream of compressed codes to recover an output stream of data characters corresponding thereto comprising

• means for storing strings of data characters in first and second storage means, said stored strings having respective codes associated therewith,
• a string being stored in said first storage means as a plurality of consecutive groupings of data characters, each said grouping comprising a predetermined number of data characters, said grouping of said predetermined number of data characters defining a grouped character, each said grouped character having associated therewith a code less than a predetermined code, each code associated with a stored string being greater than any code associated with a grouped character,
• a string being stored in said second storage means as a root code extended by at most one less than said predetermined number of data characters,
• at least one of said strings stored in said second storage means being stored as an extension of a string stored in said first storage means wherein said root code comprises the code associated with said string stored in said first storage means,
• at least one of said strings stored in said second storage means being stored as one grouped character extended by at most one less than said predetermined number of data characters wherein said root code comprises said one grouped character, and
• a table listing the codes associated with strings stored in a particular one of said first and second storage means,
• said apparatus operative in a decompression cycle to
• receive a compressed code,
• output the data characters of a string of data characters corresponding to said received compressed code so as to provide said output stream of data characters,
• set a temporary flag in accordance with said string corresponding to said received compressed code, said temporary flag indicating one of said first and second storage means into which to store an extended string in the next decompression cycle,
• store an extended string in one of said first and second storage means in accordance with an update flag indicating into which of said first and second storage means to store said extended string, said extended string based on the string corresponding to the compressed code received in the previous decompression cycle,
• said compressed code received in said previous decompression cycle refining a previous code,
• assign a code to said stored extended string, said code assigned to said stored extended string being greater than any code associated with said grouped characters,
• list said code assigned to said stored extended string in said table if said extended string is stored in said particular one of said first and second storage means, and
• transfer said temporary flag to said update flag.