US5045852A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dynamic model selection during data compression
Assignee: International Business Machines Corp
•
Filing: 1990-03-30
•
Granted: 1991-09-03
•
Expires: 2010-03-30
Abstract
Abstract A system and method for maximizing data compression by optimizing model selection during coding of an input stream of data symbols, wherein at least two models are run and compared, and the model with the best coding performance for a given-size segment or block of compressed data is selected such that only its block is used in an output data stream. The best performance is determined by 1) respectively producing comparable-size blocks of compressed data from the input stream with the use of the two, or more, models and 2) selecting the model which compresses the most input data. In the preferred embodiment, respective strings of data are produced with each model from the symbol data and are coded with an adaptive arithmetic coder into the compressed data. Each block of compressed data is started by coding the decision to use the model currently being run and all models start with the arithmetic coder parameters established at the end of the preceding block. Only the compressed code stream of the best model is used in the output and that code stream has in it the overhead for selection of that model. Since the decision as to which model to run is made in the compressed data domain, i.e., the best model is chosen on the basis of which model coded the most input symbols for a given-size compressed block, rather than after coding a given number of input symbols, the model selection decision overhead scales with the compressed data. Successively selected compressed blocks are combined as an output code stream to produce an optimum output of compressed data, from input symbols, for storage or transmission.
Inventors
- 👤 Joan L. Mitchell
- 👤 William B. Pennebaker
- 👤 Jorma J. Rissanen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 06:42
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/4006; H03M7/46; H03M7/48
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
167 words
A computerized method of maximizing the compression of a stream of input symbols by dynamically selecting the best of a plurality of data compression models for respectively encoding each of successive portions of said stream, wherein each model, in response to input symbols, generates encoded data, based on model characteristics, in the form of respective strings of data, comprising the steps of: beginning with the same input symbol in said stream, using each model to generate respective strings of data from the stream of input symbols; compression coding said strings of data to produce blocks of compressed data, each of said blocks being at least equal to a given size; selecting the respective block of compressed data for which the most input symbols have been compressed; adding the selected block of compressed data to an output data stream; and beginning with the input symbol following the last symbol input to said selected model, reiterating the foregoing steps on the next succeeding portion of said input symbol stream.
Claim 2
Dependent Claim
167 words
A computerized method of maximizing the compression of a stream of input symbols by dynamically selecting the best of a plurality of data compression models for respectively encoding each of successive portions of said stream, wherein each model, in response to input symbols, generates encoded data, based on model characteristics, in the form of respective strings of data, comprising the steps of: beginning with the same input symbol in said stream, using each model to generate respective strings of data from the stream of input symbols; compression coding said strings of data to produce blocks of compressed data, each of said blocks being at least equal to a given size; selecting the respective block of compressed data for which the most input symbols have been compressed; adding the selected block of compressed data to an output data stream; and beginning with the input symbol following the last symbol input to said selected model, reiterating the foregoing steps on the next succeeding portion of said input symbol stream.
Claim 3
Dependent Claim
13 words
The method of claim 1 wherein the compression coding step comprises arithmetic coding.
Claim 4
Dependent Claim
31 words
The method of claim 1 wherein the compression coding step comprises binary arithmetic coding and said blocks of compressed data are only completed after a less probable symbol has been coded.
Claim 5
Dependent Claim
54 words
The method of claim 1 further comprising the steps of: coding a model identifier at the start of each block of compressed data indicative of the model producing the respective block; and including the model identifier for the selected block therein when adding the selected block of compressed data to the output data stream.
Claim 6
Dependent Claim
17 words
The method of claim 4 wherein said model identifier is used to decode the compressed data block.
Claim 7
Dependent Claim
31 words
The method of claim 1 wherein the past history of said respective strings of data is used for identifying the model to be used for the next block of compressed data.
Claim 8
Dependent Claim
65 words
The method of claim 6 wherein a threshold value is selected based on the number of input symbols coded per compressed data block, and said model to be used for the next block of compressed data continues to be used, and alternate models are not processed, as long as said threshold value is exceeded by the number of input symbols coded per compressed data block.
Claim 9
Dependent Claim
48 words
The method of claim 1 wherein said blocks of compressed data have probability estimation values associated therewith and further comprising the step of resetting the probability estimation values for the models not selected to the previous estimation values at the start of the production of the next block.
Claim 10
Dependent Claim
48 words
The method of claim 1 wherein one of said models comprises comparing the size of the selected block of compressed data to the size of the number of input symbols that have been compressed and selecting the smaller of the two for adding to the output data stream.
Claim 11
Dependent Claim
14 words
The method of claim 1 wherein the compression coding step comprises variable length coding.
Claim 12
Dependent Claim
101 words
A computerized method of selecting one of a plurality of data compression models for compressing data symbols in a stream of data symbols to maximize compression of the stream, comprising the steps of: using each of said plurality of models to form a respective block of compressed data from data symbols input from the stream, said forming beginning with the same data symbol in said stream and ending with said respective blocks of compressed data being of comparable size; and selecting the model which produces the block, from among said respective blocks, for which the most input symbols have been compressed.
Claim 13
Dependent Claim
101 words
A computerized method of selecting one of a plurality of data compression models for compressing data symbols in a stream of data symbols to maximize compression of the stream, comprising the steps of: using each of said plurality of models to form a respective block of compressed data from data symbols input from the stream, said forming beginning with the same data symbol in said stream and ending with said respective blocks of compressed data being of comparable size; and selecting the model which produces the block, from among said respective blocks, for which the most input symbols have been compressed.
Claim 14
Dependent Claim
55 words
The method of claim 11 wherein said blocks of compressed data are formed by the steps of: beginning with the same input symbol in said stream, using each model to generate respective strings of data from the stream of input symbols; and compression coding said strings of data to produce said blocks of compressed data.
Claim 15
Dependent Claim
23 words
The method of claim 12 wherein said respective blocks of compressed data are only completed after a less probable symbol has been coded.
Claim 16
Dependent Claim
167 words
A computerized method of dynamically selecting the best of a plurality of data compression models for use in arithmetic coding and decoding wherein each model generates a string of data in response to a stream of input symbols, comprising the steps of: beginning with the same symbol in said input symbol stream, using each of said models to produce respective strings of data from said input symbols including a model selection decision for the respective model; coding the model selection decision and the string of data for each model with an adaptive arithmetic coder to generate respective blocks of compressed data for each model, with each of said blocks being of at least a given size and starting the coding of each model for a given block with the same code stream and probability interval; and selecting the model with the best coding performance from among the blocks of compressed data generated during the arithmetic coding on the basis of the amount of input symbol data compressed.
Claim 17
Dependent Claim
167 words
A computerized method of dynamically selecting the best of a plurality of data compression models for use in arithmetic coding and decoding wherein each model generates a string of data in response to a stream of input symbols, comprising the steps of: beginning with the same symbol in said input symbol stream, using each of said models to produce respective strings of data from said input symbols including a model selection decision for the respective model; coding the model selection decision and the string of data for each model with an adaptive arithmetic coder to generate respective blocks of compressed data for each model, with each of said blocks being of at least a given size and starting the coding of each model for a given block with the same code stream and probability interval; and selecting the model with the best coding performance from among the blocks of compressed data generated during the arithmetic coding on the basis of the amount of input symbol data compressed.
Claim 18
Dependent Claim
199 words
A computerized system for maximizing the compression of a stream of input symbols by dynamically selecting the best of a plurality of data compression models for respectively encoding each of successive portions of said stream, wherein each model, in response to input symbols, generates encoded data, based on model characteristics, in the form of respective strings of data, comprising: means, beginning with the same input symbol in said stream, for generating respective strings of data from the stream of input symbols using each of said data compression models; means for compression coding said strings of data to produce respective blocks of compressed data, each of said blocks being at least equal to a given size; means for selecting the respective block of compressed data for which the most input symbols have been compressed; means for adding the selected block of compressed data to an output data stream; and means for actuating said foregoing means to act on the next succeeding portion of said input symbol stream, beginning with the input symbol following the last symbol input to said selected model, until all of the portions of said input stream have been compressed and added to said output data stream.
Claim 19
Dependent Claim
199 words
A computerized system for maximizing the compression of a stream of input symbols by dynamically selecting the best of a plurality of data compression models for respectively encoding each of successive portions of said stream, wherein each model, in response to input symbols, generates encoded data, based on model characteristics, in the form of respective strings of data, comprising: means, beginning with the same input symbol in said stream, for generating respective strings of data from the stream of input symbols using each of said data compression models; means for compression coding said strings of data to produce respective blocks of compressed data, each of said blocks being at least equal to a given size; means for selecting the respective block of compressed data for which the most input symbols have been compressed; means for adding the selected block of compressed data to an output data stream; and means for actuating said foregoing means to act on the next succeeding portion of said input symbol stream, beginning with the input symbol following the last symbol input to said selected model, until all of the portions of said input stream have been compressed and added to said output data stream.
Claim 20
Dependent Claim
19 words
The system of claim 15 wherein said compression coding means comprises means for arithmetically coding said strings of data.
Claim 21
Dependent Claim
20 words
The system of claim 15 wherein said compression coding means comprises means for variable length coding said strings of data.
Claim 22
Dependent Claim
41 words
The system of claim 15 further comprising means for resetting the probability estimation values, associated with said blocks of compressed data, for the models not selected to the previous estimation values at the start of the production of the next block.
Claim 23
Dependent Claim
97 words
A computerized system for selecting one of a plurality of data compression models for compressing data symbols in a stream of data symbols to maximize compression of the stream, comprising: means, using each of said plurality of models, for forming a respective block of compressed data from data symbols input from the stream, said forming beginning with the same data symbol in said stream and ending with said respective blocks of compressed data being of comparable size; and means for selecting the block, from among said respective blocks, for which the most input symbols have been compressed.
Claim 24
Dependent Claim
97 words
A computerized system for selecting one of a plurality of data compression models for compressing data symbols in a stream of data symbols to maximize compression of the stream, comprising: means, using each of said plurality of models, for forming a respective block of compressed data from data symbols input from the stream, said forming beginning with the same data symbol in said stream and ending with said respective blocks of compressed data being of comparable size; and means for selecting the block, from among said respective blocks, for which the most input symbols have been compressed.
Claim 25
Dependent Claim
170 words
A computerized system for dynamically selecting one of a plurality of data compression models for use in arithmetic coding and decoding wherein each model generates a string of data in response to a stream of input symbols, comprising the steps of: means, beginning with the same symbol in said input symbol stream, for producing respective strings of data from said input symbols using each of said models and including a model selection decision for the respective model; adaptive arithmetic coder means for coding the model selection decision and the string of data for each model to generate respective blocks of compressed data for each model, with each of said blocks being of at least a given size and starting the coding of each model for a given block with the same code stream and probability interval; and means for selecting the model with the optimum coding performance from among the blocks of compressed data generated during the arithmetic coding on the basis of the amount of input symbol data compressed.
Claim 26
Dependent Claim
170 words
A computerized system for dynamically selecting one of a plurality of data compression models for use in arithmetic coding and decoding wherein each model generates a string of data in response to a stream of input symbols, comprising the steps of: means, beginning with the same symbol in said input symbol stream, for producing respective strings of data from said input symbols using each of said models and including a model selection decision for the respective model; adaptive arithmetic coder means for coding the model selection decision and the string of data for each model to generate respective blocks of compressed data for each model, with each of said blocks being of at least a given size and starting the coding of each model for a given block with the same code stream and probability interval; and means for selecting the model with the optimum coding performance from among the blocks of compressed data generated during the arithmetic coding on the basis of the amount of input symbol data compressed.
References Cited (Backward Citations)
US3394352A
Cited
US4286256A
Cited
US4646061A
Cited
US4891643A
Cited
US4905297A
Cited
US4730348A
Cited
US4929946A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-09-02 | 1995-03-04 | 1995-09-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-09-02 | 1999-03-04 | 1999-09-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-09-02 | 2003-03-04 | 2003-09-03 | $7700.00 | Window Closed / Lapsed |