Apparatus and method for managing multiple dictionaries in content addressable memory based data compression

• US 5,373,290 A
• Filed: 12/23/1992
• Issued: 12/13/1994
• Est. Priority Date: 09/25/1991
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: HP Inc.
• Inventors: Lantz, Carl B., Seroussi, Gadiel, Tobin, Jeffrey P., Lempel, Abraham
• Primary Examiner(s): Logan, Sharon D.
• Application Number:
  US07/996,808
• Time in Patent Office: 720 Days
• Field of Search: 341/51, 341/106, 341/52, 341/55, 341/87, 341/94, 341/95
• US Class Current: 341/51
• 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 class of lossless data compression algorithms use a memory-based dictionary of finite size to facilitate the compression and decompression of data. To reduce the loss in data compression caused by dictionary resets, a standby dictionary is used to store a subset of encoded data entries previously stored in a current dictionary. In a second aspect of the invention, data is compressed/decompressed according to the address location of data entries contained within a dictionary built in a content addressable memory (CAM). In a third aspect of the invention, the minimum memory/high compression capacity of the standby dictionary scheme is combined with the fast single-cycle per character encoding/decoding capacity of the CAM circuit. The circuit uses multiple dictionaries within the storage locations of a CAM to reduce the amount of memory required to provide a high data compression ratio.

Claims

1. A method for compressing and decompressing data in a memory based dictionary comprising:

providing a memory device for receiving compressed and uncompressed character strings, the memory including a plurality of storage locations, each having a unique address, for storing character strings as data entries;

defining at least first and second dictionaries within the plurality of storage locations of the memory device;

assigning multiple states to the storage locations of the memory device;

assigning each stored data entry to at least one of the first and second dictionaries; and

generating a codeword representing a data character string, the codeword value associated with a first address in memory of a previously stored data entry that matches the character string and is assigned to one of said dictionaries.

2. A compression/decompression method according to claim 1 including changing the dictionary assignments for each data entry according to a current state of the memory device.

3. A compression/decompression method according to claim 2 wherein changing the state of the memory device resets at least one of the dictionaries so that storage locations previously assigned to those dictionaries constitute free storage locations no longer assigned to any dictionary.

4. A compression/decompression method according to claim 2 including changing the state of the memory device when one of the dictionaries becomes full.

5. A compression/decompression method according to claim 2 including changing the state of the compressor/decompressor when the compression ratio falls below a predetermined value.

6. A compression/decompression method according to claim 1 including identifying memory device storage locations that do not contain data entries or have data entries not assigned to one of said dictionaries.

7. A compression/decompression method according to claim 1 including locating data entries by searching multiple dictionaries at the same time.

8. A compression/decompression method according to claim 1 including simultaneously storing a data entry in a memory device storage location and assigning that data entry to a dictionary in accordance with a current state of the memory device.

9. A compression/decompression method according to claim 1 wherein the memory device comprises a content addressable memory.

10. A compression/decompression method according to claim 1 including storing a first codeword that does not match one of the previously stored data entries into the first dictionary.

11. A compression/decompression method according to claim 10 including assigning the data entry for the first codeword to the second dictionary if a subsequent data character string matches the string encoded by the first codeword.

12. A compression/decompression method according to claim 1 wherein the memory device in a first state treats the first dictionary as a current dictionary, the second dictionary as a standby dictionary, and storage locations not presently containing a current or standby dictionary data entries as free space.

13. A compression/decompression method according to claim 12 wherein changing the memory device into a second state assigns the storage locations of the current dictionary into free space and assigns the data entries of the standby dictionary as data entries of the current dictionary.

14. A dictionary based data compression/decompression circuit comprising:

a memory device for receiving compressed and uncompressed character strings including means for compressing/decompressing input data to produce encoded/decoded data strings;

the memory having multiple storage locations, each storage location having a data field for storing a character string as a data entry, and a status field comprising at least two bits for assigning at least two dictionaries to the data entry;

a status register having multiple fields each comprising at least two bits for identifying the dictionaries that have been assigned to the data entries and for identifying data entries that are not assigned to a dictionary; and

means for changing the dictionary assignments for each data entry in the memory device by changing the values in the status register fields.

15. A data compression/decompression circuit according to claim 14 wherein the dictionary assignments for each data entry are changed by shifting bits in the status register.

16. A data compression/decompression circuit according to claim 14 including a status register pattern generator for simultaneously searching multiple dictionaries for a data entry.

17. A data compression/decompression circuit according to claim 14 including means for selectively masking bit locations in the status field and data field when searching storage locations in the memory device.

18. A data compression/decompression circuit according to claim 14 including means for selectively comparing any status register field with the status fields of each storage location to determine whether a data entry in said locations is assigned to one of said dictionaries.

19. A data compression/decompression circuit according to claim 14 including means for selectively writing the value of any status register field into a storage location status field to control data entry dictionary assignments.

20. A data compression/decompression circuit according to claim 14 wherein the memory device comprises a content addressable memory.