Data compression method using textual substitution

摘要

A method of compressing input characters, and decompressing compressed data to produce the original input characters is provided whereby an input substitution table and an output substitution table are formed by storing an identical set of arbitrary character tokens of a fixed length in each of the tables. Each table entry has a first and second token data field associated with it. The token data fields are representative of either a character token or substitution code token. Input characters are loaded into an input register and pairs of tokens in the input register are replaced with a substitution code token from the input substitution table. The tokens residing in the input resister are transmitted as output tokens to the decompression mechanism. The entries in the input substitution table are then updated by locating a substitution entry in the table which is not referenced by any other substitution table entry and by replacing this entry with the two most recently transmitted output tokens. Meanwhile, the transmitted output tokens are loaded into a token field of an output register. The output substitution table is updated based on the received output tokens in a manner similar to the method of updating the input substitution table. Substitution code tokens received by the output register are expanded to produce a plurality of character tokens. Character tokens are output as output characters which are identical to the original input characters.