Compressed caching in a virtual memory system

摘要

Data compression systems, methods, and computer program products are disclosed. For each successive input word of an input stream, it is determined whether the input word matches an entry in a lookback table. The lookback table is updated in response to the input word. Input words may be of a number of data types, including zero runs and full or partial matches with an entry in the lookback table. A codeword is generated by entropy encoding a data type corresponding to the input word. The lookback table may be indexed by the position of the input word in the input stream.

主权项

1. A method for compressing an input stream of a plurality of input words, the method comprising:
for each successive input word of the input stream, determining whether the input word matches an entry in a lookback table, the lookback table storing a plurality of entries; updating the lookback table in response to the input word; generating a codeword by entropy encoding a data type corresponding to the input word, each input word being one of a plurality of data types, the plurality of data types including at least a first data type indicating full matching between the input word and an entry in the lookback table and a second data type indicating partial matching between the input word and an entry in the lookback table; and generating an output stream, the output stream including codewords ordered correspondingly to the input words of the input stream, wherein the entropy encoding comprises at least one of: an incremental encoding scheme that uses suffixes or prefixes with its codewords to build its dictionary; a text-based, loss-less coding scheme; WKDM encoding; WinRAR encoding; 7-Zip encoding; an image compression encoding scheme used in a portable document format (PDF) image compression technique; a lossy image compression encoding scheme; a Joint Photographic Experts Group (JPEG) image compression technique; a loss-less image compression technique; and a Portable Network Graphics (PNG) image compression technique.