Back to results
US 5,970,177 AGranted
Data compression using selective encoding
AssigneeAmerica Online, Inc.
InventorDouglas P. Chinnock
Life of this patent
Estimating the term…
Abstract
A data compression method that uses selective encoding is disclosed. A block of data is compressed using a combination of the LZ77 and Huffman coding techniques. Each compressed block consists of a pair of Huffman code trees that describe the representation of the compressed data part and a compressed data part. Compressed data may consist of literal data that has not been detected as duplicated and length/backward pairs indicating the location of a duplicated string. Compressed data is arranged in a deflate format.
Claims8
A data compression system comprising:
- an input store for receiving and storing a plurality of bytes of uncompressed data from an input source;
- a data processing means for processing successive bytes of data from said input source;
- a sequence of successive bytes to be processed by said data processing means;
- an identification means included in said data processing means for identifying a sequence of successive bytes already processed identical to said sequence of successive bytes to be processed;
- a plurality of index tables one of which is selected by a first byte in said sequence of successive bytes to be processed, said index tables comprising pointers to already processed byte sequences;
- an entry in said index table selected by said first byte such that said entry is selected by a second byte in said sequence of successive bytes to be processed;
- a pointer to a head of a chain of already processed byte sequences with same said first byte and said second byte, said pointer being a part of said entry in one of said plurality of index tables;
- a selection means for finding a longest sequence of successive bytes already processed that matches said sequence of successive bytes to be processed from said byte sequences in said chain of already processed byte sequences;
- a first encoding means for transferring to a processing unit each literal byte not found by said selection means to match one of said already processed byte sequences;
- and
- a second encoding means for transferring to said processing unit a position and a length of said longest sequence of successive bytes already processed.
8 more elements
A method for compressing data compression comprising the steps of:
- receiving and storing in an input store a plurality of bytes of uncompressed data from an input source;
- processing successive bytes of data from said input source;
- locating from said input source a sequence of successive bytes to be processed;
- identifying a sequence of successive bytes already processed identical to said sequence of successive bytes to be processed;
- selecting by a first byte in said sequence of successive bytes to be processed one of a plurality of index tables, said index tables comprising pointers to already processed byte sequences;
- selecting by a second byte in said sequence of successive bytes to be processed an entry in said index table selected by said first byte;
- setting a pointer to a head of a chain of already processed byte sequences with same said first byte and said second byte, said pointer being a part of said entry in one of said plurality of index tables;
- finding a longest sequence of successive bytes already processed that matches said sequence of successive bytes to be processed from said byte sequences in said chain of already processed byte sequences;
- encoding each literal byte not found by said selection means to match one of said already processed byte sequences;
- transferring said encoded literal byte to a processing unit;
- encoding a position and a length of said longest sequence of successive bytes already processed;
- and;
- transferring said encoded position and length to said processing unit.
10 more elements
Dependencies are inferred from the claim text.