Algorithm for the implementation of Ziv-Lempel data compression using content addressable memory

• US 5,469,161 A
• Filed: 08/13/1992
• Issued: 11/21/1995
• Est. Priority Date: 08/13/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bezek, John D.
• Primary Examiner(s): Hoff, Marc S.
• Application Number:
  US07/930,136
• Time in Patent Office: 1,195 Days
• Field of Search: 341/51, 341/106, 341/50
• US Class Current: 341/51
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

A data processing system is provided with a system to implement a form of data compression--the Ziv-Lempel or Ziv-Lempel-Welsh (ZLW) algorithm--in those systems which incorporate a content addressable memory (CAM), also known as an associative memory. Such implementation results in significant processing performance improvement in the data compression and decompression phases. The ZLW algorithm is widely used in industry and government to realize the reduction in amount of storage space needed for various forms of computer system data files. The processing to result in a LZW compressed file, or the inverse decompress operation, consumes significant computer resources. Such resource and time is justified realizing the savings in amount of computer main and secondary stores needed to retain various data files. The algorithms presented here-in are a significant variation on the basic ZLW theme. Utilizing a CAM memory for high speed data table searching, the novel algorithms result in a standard ZLW format compressed file.

Claims

1. A computer system for processing Ziv-Lempel compressed data, comprising

a functional unit having, in combination, a computer operating system, a main memory and a content addressable memory, and a secondary memory for retrieval and storage of data, and a means to address secondary memory for retrieval and storage of data,

an application program and a ZLWCAM data compression paradigm, said ZLWCAM data compression paradigm including means for processing data from said application program and compressing it to utilize less data storage in said secondary memory,

said content addressable memory being utilized during execution of said ZLWCAM data compression paradigm to accelerate the process of compression of application program data, and

means for determining if a data field of an item of compressed data specifies another item of compressed data.

2. A computer system according to claim 1 wherein said content addressable memory has a pattern register, a mask register and a CAM memory array with status latches and a response resolver for said CAM memory array.

3. A computer system according to claim 2 wherein said ZLWCAM paridigm while operating within said computer system performs compression and decompression steps, and wherein said compression steps include reading and writing data to and from said CAM memory array, the writing of data to said CAM memory array including a precursor step of a pattern match for selecting CAM memory components for reading and writing.

4. A computer system according to claim 3 wherein said ZLWCAM paradigm includes the means for:

initializing a string table for CAM locations to empty, and then filling initialized locations with code values for initial literal characters in a character set,

setting in memory a current base value and building string to null,

maintaining an execution loop which executes until all input data is exhausted,

performing a match operation using an input character and current Base Value against Append Character and Base Code Value CAM fields respectively,

and then if string in string table shows a match of previous step is successful, setting the Current Base Value to Base Code Value from matching CAM word, but if the Base Code Value is NULL then using a character encoding value for the character just input, and

output current Base Code Value for the latest matching string and

performing a match in the CAM using the Current Base Value against a New Code Value field to locate a unique CAM entry which is a representation of the string whose code value was just output, and increment a Use Count field of that CAM entry, then

write a new string table entry to CAM using Current Base Value as the Base Code Value, current input character as an append character and the next larger unused Base Code Value as a Code Value, and

set a Building String to contain only the current input character, and set the Current Base Value to the character encoding value for the character just input to start construction of a new string pattern.

5. A computer system according to claim 1 wherein the ZLWCAM paradigm includes means for efficient pruning of dynamic string/substring tables.

6. A computer system according to claim 1 wherein the ZLVCAM paradigm includes means for efficient pruning of dynamic string/substring tables which employs a method of imbedding a use count within items in a string table using CAM searching to quickly trim off low use fields.

7. A computer system according to claim 2 wherein the computer system includes within operations of said ZLWCAM paradigm means for implementing the Ziv-Lempel, Ziv-Lempel-Welch, (ZLW) data compression algorithm using said content addressable memory.

8. A method to uncompress ZLW compressed strings using CAM, comprising the steps of:

initializing a string table for CAM locations to empty, and then filling initialized locations with code values for the initial literal characters in the character set,

setting in memory a current base value and a building string to null,

Maintaining an execution loop which executes until all input data is exhausted,

performing a match operation using an input character and current Base Value against Append Character and Base Code Value CAM fields respectively,

and then if string in string table shows a match of previous step is successful, setting a Current Base Value to Base Code Value from matching CAM word, but if a Base Code Value is NULL then using a character encoding value for a character just input, and

output the current Base Code Value for a latest matching string and

performing a match in a CAM using the Current Base Value against a New Code Value field to locate a unique CAM entry which is the representation of the string whose code value was just output, and increment a Use Count field of that CAM entry, then

write a new string table entry to CAM using Current Base Value as a Base Code Value, current input character as an append character and a next larger unused Base Code Value as the New Code Value, and

set the Building String to contain only a current input character, and set the Current Base Value to the character encoding value for a character just input to start construction of a new string pattern.

9. A method for efficient pruning of dynamic string/substring tables, comprising the steps of:

pattern matching using a CAM, and marking words which have a Use Count<

=Prune Threshold,

picking one of the marked CAM words from said pattern matching step and unmark it, but if no words remain marked then exit,

if a Base Code Value of the word selected in step 2 is NULL then going to said picking step,

extracting a New Code Value from the word of said picking step, Perform a CAM Match using the New Code Value against the Base Code Value field,

if no matches occur in the CAM

removing the CAM word entry selected in said picking step,

extracting the Base Code Value from the word of said picking step, Mark that CAM entry which has its New Code Value equal to this Base Code Value,

returning to said picking step.