Algorithm for the implementation of Ziv-Lempel data compression using content addressable memory
First Claim
1. A computer system for processing Ziv-Lempel compressed data, comprisinga 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, andmeans for determining if a data field of an item of compressed data specifies another item of compressed data.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
9 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.
-
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.
-
Specification