EP0313190A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Performance-based reset of data compression dictionary
Assignee: HP Inc
•
Filing: 1988-08-03
•
Granted: —
•
Expires: 2008-08-03
Abstract
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 inclludes a data compressor (11), a timer (13), a up-down counter (15), a comparator (17), and a resettable dictionary (21). Initially unassigned codes in the dictionary 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 determined by the up-down counter (15). The comparator (17) compares this difference with a value representing a predetermined performance threshold. The dictionary (21) can be reset if the actual performance falls below a performance threshold set by a threshold programmer (29). The reset can be inhibited while the dictionary (21) 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.
Inventors
- 👤 Jeff J. Kato
- 👤 David W. Ruska
- 👤 David J. Van Maren
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-02 13:31
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42; H03M7/3084; H03M7/46; H03M7/48
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
248 words
A system comprising: compressor means (11) for processing a digital data stream according to a predetermined adaptive compression strategy, said compressor means (11) including: compressor input means (103) for receiving an input stream to be compressed, compressor output means (105) for outputting an output stream yielded by said compression strategy, dictionary means (21) for translating digital input sequences in said input stream into codes constituting said output stream, said dictionary means (21) having a predetermined set of codes including assignable codes, said dictionary means (21) having an initial state in which said assignable codes are not assigned to input sequences, and assignment means ( 11) for, in accordance with said compression strategy, assigning unassigned ones of said assignable codes to digital input sequences as they are received in said input stream by said compressor input means (103); monitor means (15) for providing a performance reading for said compressor means (11) by comparing the bit-lengths of corresponding segments of said input stream and said output stream, said monitor means (15) being coupled to said compressor input means (103) and said compressor output means (105); threshold means (17) for providing a performance comparison of said performance reading with a predetermined performance threshold, said threshold means (17) being coupled to said monitor means (15); and reset means (133) for resetting said dictionary means (21) to said initial state as a function of said performance comparison, said reset means (133) being coupled to said threshold means (17) and said compressor means (11).
Claim 2
Independent Claim
248 words
A system comprising: compressor means (11) for processing a digital data stream according to a predetermined adaptive compression strategy, said compressor means (11) including: compressor input means (103) for receiving an input stream to be compressed, compressor output means (105) for outputting an output stream yielded by said compression strategy, dictionary means (21) for translating digital input sequences in said input stream into codes constituting said output stream, said dictionary means (21) having a predetermined set of codes including assignable codes, said dictionary means (21) having an initial state in which said assignable codes are not assigned to input sequences, and assignment means ( 11) for, in accordance with said compression strategy, assigning unassigned ones of said assignable codes to digital input sequences as they are received in said input stream by said compressor input means (103); monitor means (15) for providing a performance reading for said compressor means (11) by comparing the bit-lengths of corresponding segments of said input stream and said output stream, said monitor means (15) being coupled to said compressor input means (103) and said compressor output means (105); threshold means (17) for providing a performance comparison of said performance reading with a predetermined performance threshold, said threshold means (17) being coupled to said monitor means (15); and reset means (133) for resetting said dictionary means (21) to said initial state as a function of said performance comparison, said reset means (133) being coupled to said threshold means (17) and said compressor means (11).
Claim 3
Dependent Claim
66 words
The system of Claim 1 further comprising dictionary level means (109) for providing dictionary status information regarding the extent to which assignable codes have been assigned at any given time, said dictionary level means (109) being coupled to said reset means (133) so that said reset means (133) can reset said dictionary means (21) as a function of said performance comparison and said dictionary status information.
Claim 4
Dependent Claim
33 words
The system of Claim 2 wherein said dictionary level means (109) provides a dictionary status signal to said reset means (133) indicating whether a predetermined percentage of said assignable codes has been assigned.
Claim 5
Dependent Claim
89 words
The system of Claim 3 wherein said reset means (133) resets said dictionary means (21) to its initial state when said monitor means (15) indicates said compressor means (11) is expanding said digital data stream rather than compressing it, said reset means (133) also resetting said dictionary means (21) when said performance, as determined by said monitor means (15), falls below said performance threshold as determined by said threshold means (17) provided said predetermined percentage of assignable codes has been achieved as indicated by said dictionary level means (109).
Claim 6
Dependent Claim
155 words
The system of Claim 1 wherein: said monitor means (15) includes bi-directional counter means ( 15) for providing a performance measure for said compressor means (11) by counting in one direction in proportion to number of bits in said input stream received by said compressor input means (103) and by counting in the opposite direction in proportion to the number of bits output by said compressor means (11) in said output stream, and uni-directional counter means (13) coupled to said compressor input means (103) for detecting when a predetermined number of input bits have been received, said uni-directional counter means (13) being coupled to said bi-directional counter (15) so as to enable it to provide a bi- directional count output when the predetermined number of input bits has been received; and said threshold means (17) includes a comparator ( 17) for comparing said bi-directional count output from the bi-directional counter (15) with said performance threshold.
Claim 7
Dependent Claim
50 words
The system of Claim 1 further comprising: threshold programming means (29) for programming said performance threshold of said threshold means (17) as a function of performances previously indicated by said monitor means (15), said threshold programming means (29) being coupled to said monitor means (15) and said threshold means (17).
Claim 8
Independent Claim
84 words
A method for enhancing the performance of a compressor embodying a dictionary-based adaptive compression strategy, said method comprising: inputting a data file into an adaptive data compressor (11) having a resettable dictionary (21); monitoring the performance of said compressor (11) by comparing the bit-lengths of corresponding segments of the data input to said compressor (11) and data output by said compressor (11); and clearing assignable codes in said dictionary (21) when the performance of said compressor (11) falls below a first threshold (at 17).
Claim 9
Independent Claim
84 words
A method for enhancing the performance of a compressor embodying a dictionary-based adaptive compression strategy, said method comprising: inputting a data file into an adaptive data compressor (11) having a resettable dictionary (21); monitoring the performance of said compressor (11) by comparing the bit-lengths of corresponding segments of the data input to said compressor (11) and data output by said compressor (11); and clearing assignable codes in said dictionary (21) when the performance of said compressor (11) falls below a first threshold (at 17).
Claim 10
Dependent Claim
38 words
The method of Claim 7 further comprising: setting said first threshold as a function of prior performance of said compressor (11) since the later of a) the beginning of the present file and b) the most recent reset.
Claim 11
Dependent Claim
26 words
The method of Claim 7 further comprising: prior to said clearing step, waiting until a predetermined percentage of assignable codes in said dictionary have been assigned.
Claim 12
Dependent Claim
44 words
The method of Claim 9 wherein: if during said waiting step, the performance of said compressor (11) falls below a second threshold corresponding to poorer performance than said first threshold, clearing said dictionary irrespective of the percentage of assignable codes which have been assigned.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.