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.