Lempel-Ziv compression scheme with enhanced adapation

• US 5,243,341 A
• Filed: 06/01/1992
• Issued: 09/07/1993
• Est. Priority Date: 06/01/1992
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett Packard Company (HP Inc.)
• Inventors: Seroussi, Gadiel, Lempel, Abraham
• Primary Examiner(s): Logan, Sharon D.
• Application Number:
  US07/892,546
• Time in Patent Office: 463 Days
• Field of Search: 341/51, 341/50, 341/67, 341/106, 341/87, 235/310, 235/311
• 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. When the current dictionary (CD) fills up with encoded character strings, it is reset thereby losing the compression information previously contained in the dictionary. To reduce the loss in data compression caused by dictionary resets, a second, standby dictionary (SD) is used to simultaneously store a subset of the encoded data entries stored in the first dictionary. The data entries in the second dictionary represent the data entries of the first dictionary that compress the greatest amount of input data. When the first dictionary is ready to be reset, the first dictionary is replaced with the second dictionary, maintaining high data compression and freeing up memory space for new encoded data strings.

Claims

1. A dictionary based data compression/decompression system comprising:

a memory device including first and second dictionaries, each dictionary including a finite number of locations for storing data from a data sequence;

a data compression engine for reading and writing to a first dictionary in accordance with a predetermined compression algorithm;

the data compression engine including means for compressing/decompressing input data to produce encoded data strings, and means for reading/writing data entries from/into locations within the first dictionary; and

logic means for writing into the second dictionary a selected subset of the data entries written into the first dictionary by the data compression engine while writing data entries into the first dictionary.

2. A dictionary based data compression/decompression system according to claim 1 including means for switching the read/write operations of the data compression engine between the first and second dictionaries so that the data compression engine transfers stored data to/from the second dictionary in accordance with the predetermined compression algorithm and the logic means writes a subset of the data entries into the first dictionary.

3. A data-compression/decompression system according to claim 2 further comprising reset means for activating the switching means when the first dictionary is loaded with a predetermined number of data entries.

5. A data-compression/decompression system according to claim 2 including means for deactivating the switching means so that the data compression engine reads/writes stored data exclusively to/form a single dictionary.

4. A dictionary based data compression/decompression system comprising:

a memory device including first and second dictionaries, each dictionary including a finite number of locations for storing data from a data sequence;

a data compression engine for reading and writing to a first dictionary in accordance with a predetermined compression algorithm;

the data compression engine including means for compressing/decompressing input data to produce encoded data strings, and means for reading/writing data entries from/into locations within the first dictionary;

logic means for writing into the second dictionary selected subset of the data entries written into the first dictionary by the data compression engine;

means for switching the read/write operations of the data compression engine between the first and second dictionaries so that the data compression engine transfers stored data to/from the second dictionary in accordance with the predetermined compression algorithm and the logic means writes a subset of the data entries into the first dictionary; and

reset means for activating the switching means when the data compression engine falls below a predetermined compression threshold ratio.

6. A dictionary based data compression/decompression system comprising:

a memory device including first and second dictionaries, each dictionary including a finite number of locations for storing data from a data sequence;

a data compression engine for reading and writing to a first dictionary in accordance with a predetermined compression algorithm;

the data compression engine including means for compressing/decompressing input data to produce encoded data strings, and means for reading/writing data entries from/into locations within the first dictionary;

logic means for writing into the second dictionary a selected subset of the data entries written into the first dictionary by the data compression engine; and

means for identifying data entries in the first dictionary previously written into the second dictionary.

7. A dictionary based data compression/decompression system comprising:

a memory device including first and second dictionaries, each dictionary including a finite number of locations for storing data from a data sequence;

a data compression engine for reading and writing to a first dictionary in accordance with a predetermined compression algorithm;

the data compression engine including means for compressing/decompressing input data to produce encoded data strings, and means for reading/writing data entries from/into locations within the first dictionary; and

logic means for writing into the second dictionary a selected subset of the data entries written into the first dictionary by the data compression engine;

the logic means being operable to write a data entry into the second dictionary that has matched at least once with one of the data entries of the first dictionary while writing data entries into the first dictionary.

8. A dictionary based data-compression/decompression system comprising:

a memory including a current and standby dictionary for storing data entries, each data entry defining a plurality of data sequences;

a data compression engine for selecting character strings from a data sequence and comparing the character strings to data entries in the current dictionary to determine whether the character string and any of the data entries match;

means for storing unmatched multi-character strings as data entries in the current dictionary;

means for writing a selected subset of the data entries of the multi-character strings previously stored in the current dictionary into the standby dictionary while writing data entries into the current dictionary; and

means for switching the current dictionary with the standby dictionary and initializing the standby dictionary when the data compression engine detects a predetermined reset condition.

9. A dictionary-based data compression/decompression method in which a predetermined compression algorithm reads/writes data in a dictionary to compress/decompress a data sequence, the method comprising:

establishing a current dictionary and a standby dictionary for storing data derived from the data sequence;

inputting a character string from the data sequence;

comparing the input character string to previously stored data entries in the current dictionary to determine whether the input character string and any of the stored data entries match;

storing an unmatched input character string as a data entry in the current dictionary;

storing a subset of the previously stored data entries of the current dictionary in the standby dictionary while writing data entries into the current dictionary; and

replacing the current dictionary with the standby dictionary and initializing a new standby dictionary when a predetermined reset condition occurs.

10. A dictionary based compression/decompression method in which a predetermined compression algorithm reads/writes data in a dictionary to compress/decompress a data sequence, the method comprising;

establishing a current dictionary and a standby dictionary for storing data derived from the data sequence;

inputting a character string from the data sequence;

comparing the input character string to previously stored data entries in the current dictionary to determine whether the input character string and any of the stored data entries match;

storing an unmatched input character string as a data entry in the current dictionary;

storing a subset of the previously stored data entries of the current dictionary in the standby dictionary;

selecting the subset of the previously stored data entries to be stored in the standby dictionary to comprise stored data entries from the current dictionary that have matched at least once with a subsequently encoded character string; and

replacing the current dictionary with the standby dictionary and initializing a new standby dictionary when a predetermined reset condition occurs.

11. A dictionary based compression/decompression method in which a predetermined compression algorithm reads/writes data in a dictionary to compress/decompress a data sequence, the method comprising;

establishing a current dictionary and a standby dictionary for storing data derived from the data sequence;

inputting a character string from the data sequence;

comparing the input character string to previously stored data entries in the current dictionary to determine whether the input character string and any of the stored data entries match;

storing an unmatched input character string as a data entry in the current dictionary;

storing a subset of the previously stored data entries of the current dictionary in the standby dictionary;

selecting the subset of data entries to be stored in the standby dictionary so as to generate, when utilized by the compression algorithm, at least as great an input data compression ratio as any other subset of the current dictionary with the same number of encoded data entries; and

replacing the current dictionary with the standby dictionary and initializing a new standby dictionary when a predetermined reset condition occurs.

12. A dictionary based compression/decompression method in which a predetermined compression algorithm reads/writes data in a dictionary to compress/decompress a data sequence, the method comprising:

establishing a current dictionary and a standby dictionary for storing data derived from the data sequence;

inputting a character string from the data sequence;

comparing the input character string to previously stored data entries in the current dictionary to determine whether the input character string and any of the stored data entries match;

storing an unmatched input character string as a data entry in the current dictionary;

storing a subset of the previously stored data entries of the current dictionary in the standby dictionary;

replacing the current dictionary with the standby dictionary and initializing a new standby dictionary when a predetermined reset condition occurs;

selecting a data sample of an input data sequence;

building the current and standby directories based on the selected data sample; and

disabling the standby dictionary after the current dictionary has been replaced with the standby dictionary built using the data sample.

13. A dictionary based compression/decompression method according to claim 12 including freezing the current dictionary'"'"'s data entries and sending the current dictionary'"'"'s data entries to a decoder.

14. A dictionary based compression/decompression method according to claim 12 including intermittently resetting the dictionaries prior to disabling the standby dictionary.

15. A dictionary based compression/decompression method in which a predetermined compression algorithm reads/writes data in a dictionary to compress/decompress a data sequence, the method comprising:

establishing a current dictionary and a standby dictionary for storing data derived from the data sequence;

inputting a character string from the data sequence;

comparing the input character string to previously stored data entries in the current dictionary to determine whether the input character string and any of the stored data entries match;

storing an unmatched input character string as a data entry in the current dictionary;

compressing/decompressing input data to produce encoded data strings using the current dictionary;

storing a subset of the previously stored data entries of the current dictionary in the standby dictionary; and

replacing the current dictionary with the standby dictionary when the current dictionary reaches a predetermined number of stored character string entries.

16. A dictionary based data compression/decompression system comprising:

a memory device including first and second dictionaries, each dictionary including a finite number of locations for storing data from a data sequence;

a data compression engine for reading and writing to a first dictionary in accordance with a predetermined compression algorithm;

the data compression engine including means for compressing/decompressing input data to produce encoded data strings, and means for reading/writing a first set of data entries from/into locations within the first dictionary; and

means for transferring a selected subset of the first set of data entries from the first dictionary to the second dictionary, the second dictionary receiving the selected subset directly from the first dictionary and using the subset as an initial set of data entries that can be expanded upon with additional data entries taken from the input data.