US 6,320,523 B1 · Method and apparatus for reducing the time required for compressing data

Abstract

The present invention provides a novel method and system for obtaining maximum system speed performance for compressing coded data characters in a serial data stream by replacing strings of data with code values stored in a dictionary when strings are first observed as unique strings in the data stream. A novel pointer address is generated to represent new strings to be searched in the dictionary. The novel pointer address comprises a string code portion representative of the last matched string found in the dictionary and appended thereto an extension character code portion representative of the next character taken from the input data stream. The dictionary is constructed large enough to provide a unique memory location for every possible pointer address. The unique pointer address, representative of a string of data in the input data stream, is employed as an address pointer to access the memory. If no data is in memory at the address pointer the string has not been previously observed and a new unique compression code is stored at the pointer address in memory for the string so that the next identical pointer address will read the code for the string from the dictionary. Accordingly, every memory address accessed in the dictionary with the unique address pointer immediately causes a HIT or a MISS in the dictionary. A HIT produces the last matched string code for generating a new address pointer indicative of a longer string when the extension character code is appended onto the last matched string code to provide the next new pointer address.

Claims20

Dependent claims

A method for compressing serial streams of data which includes substituting string code values for known string previously observed in the data stream, characterized by the steps of:

preparing a dictionary having 2n storage addresses to receive said string code values in the memory of some of the 2n storage addresses,
storing unique code values for new strings in said dictionary when first observed in said data stream,
creating a unique 2n bit dictionary pointer address to be used to determine if the same string being searched already has a string code stored in said dictionary, said pointer address comprising a string code portion corresponding to bits of a code for a known string and an extension character portion corresponding to bits of a code for the next character in said data stream,
reading the contents of said dictionary at said one unique 2n bit pointer address, and
determining from the contents read at the single 2n bit pointer address whether or not a code value for the memory string being searched is already present in said dictionary.

2 more elements

A method for data compression utilizing a memory dictionary for storing codes for strings of data characters encountered in an input data stream and representing known strings with string codes, characterized by:

storing unique string codes in said memory dictionary representative of known strings of data,
generating a 2n bit pointer address indicative of strings of data characters in said input data stream,
forming said pointer address comprising bits of the code for the last character in the previous string and appended thereto the bits of the next character from the input data stream forming a two character code string address,
reading a string code from the memory said dictionary at said 2n bit pointer address, and
generating a new 2n bit pointer address comprising the bits of the string code read from said dictionary and appended thereto the bit code for the next character taken from the input data stream.

2 more elements

A data compression system for compressing serial streams of data by substituting codes for known strings of characters in an input data stream, comprising:

pointer address means for searching for codes representative of strings of data in said data stream,
said pointer address comprising a known string code portion and a next character code portion wherein the next character is taken from the input data stream and appended as a character code to the string code portion to form a unique pointer address,
a string code dictionary having a plurality of addressable memory locations at least one for each possible unique pointer address,
said string code dictionary containing a unique string code value for plural character strings observed in said data stream, and
means for reading said unique string code values from said string code dictionary at said unique pointer addresses, and
means for determining from the contents read from said string code dictionary whether or not a string code exist in said dictionary that is representative of the string of characters in said input data stream and indicated by said pointer address.

3 more elements

Dependencies are inferred from the claim text.

Method and apparatus for reducing the time required for compressing data

Life of this patent

Method and apparatus for reducing the time required for compressing data

Life of this patent

Abstract

Claims20