US4494108A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive source modeling for data file compression within bounded memory
Assignee: International Business Machines Corp
•
Filing: 1984-06-05
•
Granted: 1985-01-15
•
Expires: 2004-06-05
Abstract
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.
Inventors
- 👤 Glen G. Langdon, Jr.
- 👤 Jorma J. Rissanen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 12:24
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30
Claims Analysis
Total Claims: 4
Claim 1
Independent Claim
133 words
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.
Claim 2
Dependent Claim
133 words
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.
Claim 3
Dependent Claim
119 words
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.
Claim 4
Dependent Claim
119 words
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.
References Cited (Backward Citations)
US4099257A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1988-01-15 | 1988-07-16 | 1989-01-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1992-01-15 | 1992-07-16 | 1993-01-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1996-01-15 | 1996-07-16 | 1997-01-15 | $7700.00 | Window Closed / Lapsed |