US Patent 5,229,768

Number:	5,229,768
Title:	Adaptive data compression system
Filed:
Granted:	20-Jul-1993
Inventor:	Kasman E. Thomas
Assignee:	Traveling Software, Inc.

Comment by FAQ:A system for data compression and decompression is disclosed. A series of fixed length overlapping segments, called hash strings, are formed from an input data sequence. A retrieved character is the next character in the input data sequence after a particular hash string. A hash function relates a particular hash string to a unique address in a look-up table (LUT). An associated character for the particular hash string is stored in the LUT at the address. When a particular hash string is considered, the content of the LUT address associated with the hash string is checked to determine whether the associated character matches the retrieved character following the hash string. If there is a match, a Boolean TRUE is output; if there is no match, a Boolean FALSE along with the retrieved character is output. Furthermore, if there is no match, then the LUT is updated by replacing the associated character in the LUT with the retrieved character. [...]

[This algorithm is used in the Internet Draft "PPP Predictor Compression Protocol".]