Adaptive source modeling for data file compression within bounded memory

• US 4,494,108 A
• Filed: 06/05/1984
• Issued: 01/15/1985
• Est. Priority Date: 11/09/1981
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rissanen, Jorma J., Langdon, Glen G. Jr.
• Primary Examiner(s): NOT, DEFINED
• Application Number:
  US06/617,303
• Time in Patent Office: 224 Days
• Field of Search: 340/347 DD, 235/310, 235/311, 364/200, 364/900
• US Class Current: 341/51
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

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.

Claims

1. 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.

2. 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.