Patent US5450562: Cache-based data compression/decompression 

Inventors: Rosenberg; Charles, Mt. View, CA
           Berge; Thomas G., Boise, ID
Applicant: Hewlett-Packard Company, Palo Alto, CA

Application Date: Oct. 19, 1992
Publication Date: Sep. 12, 1995

Abstract:   

A system for compressing bilevel data includes a first cache memory
having a plurality of assigned levels of usage, a first usage level
assigned to a most recently used data segments and a second level
assigned to a plurality of less recently used data segments. A
processor determines if a received data segment is found in the cache
memory and, if not, it assigns the received data segment to the cache
memory's first level in place of a previous data segment stored
therein. The previous data segment is assigned to a position in the
second level in place of a less recently used data segment. The less
recently used data segment that is displaced is chosen by a
pseudo-random method. A not-found indication is then transmitted to a
receiving station along with the identity of the received data
segment. The receiving station contains identical cache structures and
updates its caches in response to received code words and data
segments. A further version of the invention emplaces data segments
into cache memories in accordance with the context in which the data
segments are found, the cache memories being assigned in accordance
with context derived addresses.