Performance-based reset of data compression dictionary

• US 4,847,619 A
• Filed: 10/19/1987
• Issued: 07/11/1989
• Est. Priority Date: 10/19/1987
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Van Maren, David J., Kato, Jeff J., Ruska, David W.
• Primary Examiner(s): Shoop, Jr., William M.
• Assistant Examiner(s): YOUNG, BRIAN K
• Application Number:
  US07/109,970
• Time in Patent Office: 631 Days
• Field of Search: 364/900, 364/200, 358/261, 360/39, 360/40, 360/48, 340/347 DD, 341/106, 341/90, 341/87, 341/89, 341/50, 341/59, 341/67
• US Class Current: 341/106
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence
• CPC Class Codes: H03M 7/48 alternating with other codes during the code conversion process, e.g. run-length coding being performed only as long as sufficientlylong runs of digits of the same kind are present

Abstract

An adaptive data compression system is reset when performance drops below a predetermined threshold to permit greater compression of long files with evolving distributions of symbol combinations. The compression system uses a resettable dictionary in which initially unassigned codes are strategically assigned to symbol combinations as they are encountered in the data stream.

The difference between the bit-lengths of corresponding lengths of the compressor input and output is compared with a value representing a predetermined performance threshold. The dictionary can be reset if the actual performance falls below the performance threshold. The reset can be inhibited while the dictionary is less than half-full to ensure that performance measures are statistically significant. However, if the performance is such that data expansion is occurring, reset is not so delayed.

Claims

1. A system comprising:

compressor means for processing a digital data stream according to a predetermined adaptive compression strategy, said compressor means including;

compressor input means for receiving an input stream to be compressed, said input stream including strings of input codes, each string including at least one input code, each input code having a respective bit-length,

compressor output means for outputting an output stream yielded by said compression strategy, said output stream including output codes, each output code having a respective bit-length,

dictionary means for translating said strings into said output codes, said dictionary means having a predetermined code set of entries, each of said entries corresponding to a respective one of said output codes, said code set including an assignable set of assignable entries, said assignable set including an assigned subset of assigned entries and an unassigned subset of unassigned entries, at any given time said assigned subset having a non-negative number of elements, at any given time said unassigned subset having a non-negative number of elements, each of said assigned entries having its respective output code assigned to a respective one of said strings, each of said unassigned entries having no string assigned to its respective output code; and

assignment means for, in accordance with said compression strategy, assigning unassigned ones of said assignable entries to strings received by said compressor input means;

monitor means for providing a bit-length comparison value as a function of the bit-lengths of a string series of said strings and a translation of said string series into said output codes, said monitor means being coupled to said compressor input means and said compressor output means; and

clearing means for converting at least some of said assigned entries to unassigned entries when said bit-length comparison value meets a predetermined comparison criterion, said clearing means being coupled to said monitor means and said compressor means.

2. The system of claim 1 wherein said dictionary means has an initial state in which all assignable entries are unassigned entries, said clearing means converting all of said assigned entries to unassigned entries when said bit-length comparison value meets said predetermined comparison criterion, said clearing means being coupled to said monitor means and said compressor means.

3. The system of claim 2 further comprising dictionary level means for providing dictionary status information regarding the extent to which said assignable entries are assigned entries at any given time, said dictionary level means being coupled to said clearing means so that said clearing means can reset said dictionary as a function of said bit-length comparison value and said dictionary status information.

4. The system of claim 2 wherein said dictionary level means provides a dictionary status signal to said clearing means indicating whether a predetermined percentage of said assignable entries has been assigned.

5. The system of claim 4 wherein said clearing means resets said dictionary means to its initial state when said comparison value indicates that the bit-length of said translation exceeds the bit length of said series of strings, said clearing means also resetting said dictionary means when said comparison value meets said predetermined comparison criterion provided said predetermined percentage of assignable entries has been achieved as indicated by said dictionary level means.

6. The system of claim 2 wherein:

said monitor means includes

bi-directional counter means for providing said comparison value in the form of a bi-directional count by counting in one direction in proportion to a number of bits in said string series and by counting in the opposite direction in proportion to the number of bits in said translation of said string series, and

unidirectional counter means coupled to said compressor input means for detecting when a predetermined number of input bits have been received, said uni-directional counter means being coupled to said bi-directional counter so as to enable it to provide a bi-directional count to said clearing means when the predetermined number of input bits has been received; and

a comparator for comparing said bi-directional count output from the bi-directional counter with said comparison criterion.

7. The system of claim 1 further comprising:

programming means for programming said clearing means with comparison criteria as a function of comparison values previously indicated by said monitor means, said programming means being coupled to said monitoring means.

8. A method for compressing data using a data compressor for processing a digital data stream according to a predetermined adaptive compression strategy, said compressor including:

compressor input means for receiving an input stream to be compressed, said input stream including strings of input codes, each string including at least one input code, each input code having a respective bit-length,

compressor output means for outputting an output stream yielded by said compression strategy, said output stream including output codes, each output code having a respective bit-length, and

dictionary means for translating said strings into said output codes, said dictionary means having a predetermined code set of entries, each of said entries corresponding to a respective one of said output codes, said code set including an assignable set of assignable entries, said assignable set including an assigned subset of assigned entires and an unassigned subset of unassigned entries, at any given time said assigned subset having a non-negative number of elements, at any given time said unassigned subset having a non-negative number of elements, each of said assigned entries having its respective output code assigned to a respective one of said strings, each of said unassigned entries having no string assigned to its respective output code, said dictionary means having an initial state in which said assignable entries are unassigned entries,

said method comprising;

inputting said input stream into said compressor, said input stream including input blocks, each input block including code strings, each code string including at least one input code, said compressor translating each input block into a respective output block, each output block including output codes each of which corresponds to a respective one of said strings, each input block being characterizable by an input bit-length and each output block being characterizable by an output bit-length;

assigning, in accordance with said compression strategy, unassigned ones of said assignable entries to strings received by said compressor input means;

comparing the input bit-length of each input block with the output bit-length of the corresponding output block so as to provide a bit-length comparison value for each input block, the comparison value for a given block being determined after said given block is translated by said dictionary means; and

clearing at least some of said assigned entries to unassigned entries when an input block received by said compressor results in a comparison value meeting a predetermined comparison criterion.

9. The method of claim 8 wherein said clearing step involves converting all of said assigned entries to unassigned entries so that said dictionary is reset to said initial state.

10. The method of claim 9 further comprising:

setting said comparison criterion as a function of comparison values associated with input blocks received since the most recent reset of said dictionary to said initial state.

11. The method of claim 9 further comprising:

prior to said clearing step, waiting until said assignment means has assigned strings to a predetermined percentage of assignable entries in said dictionary.

12. The method of claim 11 wherein:

if during said waiting step, said comparison value meets a predetermined second comparison criterion, resetting said dictionary to its initial state irrespective of the precentage of assignable entries which have been assigned.