Patent ID: 6653950
Filing Date: 2003-11-25
Classification: H03M

Abstract:
Data compression apparatus for compressing an input stream of data characters into an output stream of compressed codes, comprisinga plurality of storage means for storing strings of data characters encountered in said input stream, said stored strings having respective string codes associated therewith, said storage means being arranged in respective levels so that the strings stored in the storage means at a level comprise one character more than the strings stored in the storage means at the level prior thereto, means for fetching a plurality of data characters from said input stream and applying the fetched characters to said levels, respectively, means for searching said fetched characters by comparing said fetched characters to said stored strings to determine the longest match therewith, said longest match being determined by one of said fetched characters resulting in a mismatch at one of said levels, said means for searching including means for cascading the string code of a string matched at a level to the next level and means for searching the strings stored in the storage means at said next level for a string corresponding to said cascaded string code extended by the fetched character applied to said next level, means for outputting the string code associated with said longest match so as to provide said output stream of compressed codes, and means for inserting an extended string into said storage means, said extended string comprising said longest match extended by the fetched character resulting in said mismatch, said extended string being stored in said storage means at the mismatching level.