Memory circuit for lossless data compression/decompression dictionary storage

• US 5,485,526 A
• Filed: 01/14/1994
• Issued: 01/16/1996
• Est. Priority Date: 06/02/1992
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: HP Inc.
• Inventors: Tobin, Jeffrey P.
• Primary Examiner(s): Chin, Stephen
• Assistant Examiner(s): MAY, TIMOTHY
• Application Number:
  US08/183,100
• Time in Patent Office: 732 Days
• Field of Search: 382/56, 341/51, 341/67, 341/106
• US Class Current: 382/232
• 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

Data is compressed/decompressed according to the address location of data entries contained within a dictionary built in a content addressable memory 88. During data compression, character combinations which have not previously occurred within the input data stream are encoded as new data entries within the dictionary. When the character string OMEGA-K fails to match any existing dictionary entry, the address of the data entry (OMEGA) is output as a codeword representing the matched portion of the character string and OMEGA-K are stored in a new address location for later use. In compression, update circuitry 84 allows a memory search and a data write to be performed during the same clock cycle. Compressed data strings are decompressed by using the compressed data characters as addresses for link list traversal of the decompression dictionary. The data entry addressed by the data character is output if it does not require further decompression. If the data entry read from memory contains another codeword, the codeword is fed back to the address decoder as the next dictionary address.

Claims

1. A circuit for use in compressing data character strings according to a dictionary based data compression algorithm, the circuit comprising:

a memory for storing compressed character strings, the memory including;

(a) a data input for receiving OMEGA-K inputs, each OMEGA-K input containing in part a codeword (OMEGA) and in part a data character string (K);

(b) a plurality of storage locations for storing the OMEGA-K inputs as data entries, each storage location having a corresponding memory address;

(c) means for simultaneously comparing an OMEGA-K input received by the data input with every previously stored data entry to determine if the OMEGA-K input matches any of the stored data entries; and

(d) a plurality of match indication outputs each corresponding to one of the plurality of storage locations, each match indication output indicating a match between an OMEGA-K input and the corresponding data entry;

a match address encoder coupled to the match indication outputs of the memory to derive a new codeword (OMEGA'"'"') equal to the address of the storage location of the stored data entry that matches the OMEGA-K input; and

input generator means, operatively coupled to receive the new codeword (OMEGA'"'"') from the match address encoder, for generating a next OMEGA'"'"'-K'"'"' input containing in part the new codeword (OMEGA'"'"') equal to the address of the storage location of the stored data entry that matches the previous OMEGA-K input and in part a next data character string (K'"'"') and for supplying the next OMEGA'"'"'-K'"'"' input to the data input of the memory.

2. A circuit according to claim 1 including means for writing an OMEGA-K input to a storage location having a selected address;

and

address generation means for incrementally selecting addresses of unused storage locations to store the OMEGA-K inputs.

3. A circuit according to claim 1 including means for reading a data entry stored in a storage location at an address defined by one of the codewords (OMEGA);

and

data feedback means for using the data entry read from the storage location in the memory as a next, linked-list memory address of previously stored OMEGA-K input to decompress a compressed character string.

4. A circuit according to claim 1 including an automatic memory update circuit coupled to the address match encoder for initiating a write of the OMEGA-K input into memory when the OMEGA-K input does not match any of the stored data entries in the memory.

5. A circuit according to claim 4 wherein the memory comprises a content addressable memory capable of performing search and write operations at the same time thereby allowing the automatic memory update circuit to selectively initiate the write of the OMEGA-K input to a memory address in a clock cycle simultaneous with searching the memory for a data entry that matches the OMEGA-K input.

6. A method for encoding a series of data character strings according to a dictionary based data compression algorithm, the method comprising the following steps:

providing a memory having unique data strings stored as data entries therein;

inputting a series of data character strings into the memory;

simultaneously comparing individual character strings of said series to every stored data entry in the memory to determine if the individual character string matches or fails to match any of the data entries;

in the case of a match, determining an address of the storage location of the data entry that matches the character string deriving a codeword equal to the address of the storage location, and combining the codeword with a next character string in said series; and

in the case of no match, storing the character string in the memory at an unused storage location.

7. A system for storing a linked list data structure according to a dictionary based data compression algorithm, the system comprising:

means for inputting an OMEGA-K string consisting of a codeword (OMEGA) followed by a string of characters (K);

a content addressable memory for storing a plurality of OMEGA-K strings as data entries at corresponding address locations;

means for simultaneously comparing an OMEGA-K string with every previously stored data to determine if the OMEGA-K string matches or fails to match any of the stored data entries;

means responsive to a match for substituting the address of the stored data entry that matches the OMEGA-K string as a new codeword (OMEGA'"'"') and means for inputting a new string of characters (K'"'"') to form a new OMEGA'"'"'-K'"'"' string; and

means responsive to a non-match for updating the memory to store the OMEGA-K string that fails to match any stored data entries as a new data entry at a new address location, the new data entry comprising an address location of a subset of a character string represented by the codeword (OMEGA) portion of the new data entry.

8. A system according to claim 7 including means responsive to an OMEGA-K string for traversing a link list of data entries in the memory to regenerate said string of characters.

9. A circuit for compressing and storing data according to a dictionary based data compression algorithm, the circuit comprising:

a content addressable memory including;

(a) a data input for receiving OMEGA-K inputs, each OMEGA-K input containing in part a codeword (OMEGA) and in part a data character string (K);

(b) a plurality of storage locations for storing the OMEGA-K inputs as data entries, each storage location having a corresponding memory address;

(c) a plurality of word select inputs for selecting corresponding storage locations;

(d) means for simultaneously comparing an OMEGA-K input received by the data input with multiple stored data entries to determine if the OMEGA-K input matches any of the stored data entries; and

(e) a plurality of match indication outputs for corresponding storage locations, individual match indication outputs indicating a match between an OMEGA-K input and a stored data entry;

a match address encoder coupled to the match indication outputs of the content addressable memory, the match address encoder outputting (1) in the case of

a match, a match signal and deriving a new codeword (OMEGA'"'"') equal to the address of the storage location of the stored data entry that matches the OMEGA-K input and (2) in the case of no match, a non-match signal;

an address encoder coupled to the match address encoder to activate in response to the non-match signal a word select input of the content addressable memory associated with an unused storage location in order to store the OMEGA-K input at the unused storage location; and

concatenating circuit coupled to the match address encoder to produce in response to the match signal a next OMEGA'"'"'-K'"'"' input containing in part the new codeword (OMEGA'"'"') equal to the address of the storage location of the stored data entry that matches the previous OMEGA-K input and in part a next data character string (K'"'"'), the concatenating circuit supplying the next OMEGA'"'"'-K'"'"' input to the data input of the content addressable memory.

10. The circuit according to claim 9 wherein in the case of no match, the address encoder activates the word select input to store the OMEGA-K input at the unused storage location during the same clock cycle that the content addressable memory simultaneously compares the OMEGA-K input with multiple stored data entries and fails to detect a match.