US Patent 5,001,478

Number:	5,001,478
Title:	Method of Encoding Compressed Data
Filed:	28-Dec-1989
Granted:	19-Mar-1991
Inventor:	Michael E. Nagy
Assignee:	IBM

Comment by FAQ:1. A method of encoding a compressed data stream made up of a sequence of literal references, lexicon references and history references, which comprises the steps of: assigning to each literal reference a literal identifier; assigning to each history reference a history identifier; assigning to each lexicon reference a lexicon identifier; and emitting a data stream with said identifiers assigned to said references. Gordon Irlam says: The invention can probably be best understood by considering the decompressor. It consists of a history buffer, and a lexicon buffer, both of which are initially empty. The history buffer contains the last n symbols emitted. Whenever a history buffer reference is to be output the string so referenced is subsequently moved to the lexicon buffer for future reference. Thus the history buffer keeps track of strings that may be repeated on a very short term basis, while the lexicon buffer stores items for a longer time. Furthermore a history reference involves specifying both the offset and length within the history buffer, whereas a lexicon reference simply specifies a number denoting the string. Both buffers have a finite size.