Adaptive source modeling for data file compression within bounded memory
AssigneeInternational Business Machines Corporation
InventorsGlen G. Langdon, Jr., Jorma J. Rissanen
Life of this patent
Estimating the term…
Abstract
A two-stage single pass adaptive modeling method and means for a finite alphabet first order MARKOV symbol source where the model is used to control an encoder on a per symbol basis thereby enabling efficient compression within a fixed preselected implementation complexity.
Claims2
A machine implementable method for dynamically selecting conditioning states thereby enabling an efficient compression with fixed preselected implementation complexity in the adaptive compression of a symbol string generated from an N distinguishable symbol alphabet MARKOV type symbol source with adaptation in the run on piecewise stationary source statistics, the method steps comprising within a single pass process:
- ascertaining the first (k-1)<N symbols appearing M times, initially treating all symbols as a single conditioning state, and thereafter distinguishing and removing at most k symbols as their occurrence count exceeds M where M varies according to the remaining number of states yet to be ascertained;
- pairing each of the conditioning states with each symbol and determining the associated conditional symbol probability distribution;
- and
- passing parameters indicative of the distribution to an extrinsic compression coding process.
In the method of coding symbols generated by an N-distinguishable symbol alphabet source in a single pass comprising the steps of modeling the source;
- and selecting and combining a code word from one of N tables of code words with a code word string, said selecting and combining step being jointly responsive to the model and each symbol occurrence from the source, wherein the modeling step includes:
- (a) ascertaining the first (k-1)<N symbols appearing (M>1) times as generated by the source;
- (b) forming and associating a conditional symbol probability distribution with respect to each ascertained symbol;
- and
- (c) passing parameters indicative of the distribution to the extrinsic coding steps of selecting and combining responsive to each source symbol occurrence.
Dependencies are inferred from the claim text.