Lempel-Ziv compression scheme with enhanced adapation
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
16 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. - View Dependent Claims (2, 3, 5)
-
-
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. - View Dependent Claims (13, 14)
-
-
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.
-
Specification