US5357250A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive computation of symbol probabilities in n-ary strings
Assignee: International Business Machines Corp
•
Filing: 1992-11-20
•
Granted: 1994-10-18
•
Expires: 2012-11-20
Abstract
Abstract A method and apparatus are provided for adaptively and predictively determining probabilities of occurrence for each symbol of a finite alphabet within a symbol string. A plurality of intervals are defined over a portion of the symbol string. As successive new symbols are added to the string, they enter the intervals, and old symbols pass out of the intervals. A probability for each symbol of the alphabet is maintained and updated by the following process. For each new symbol which enters the intervals, it is determined whether the new symbol is a given character of the alphabet, and whether each old symbol leaving each interval is the given character. Accordingly, the number of occurrences of the given character within each interval may change. A probability update value is determined, having a component from each interval determined by whether the number of occurrences of the given character in that interval changed. Preferably the update value is a binary number having a bit position corresponding to each interval. The probability of occurrence of the given symbol is updated using the probability update value.
Inventors
- 👤 Paul D. Healey
- 👤 Jorma J. Rissanen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:57
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/4006
Claims Analysis
Total Claims: 47
Claim 1
Independent Claim
134 words
A method for estimating a probability that a given symbol of a finite alphabet will occur in a symbol string of symbol of the finite alphabet, the method comprising the steps of: weighting occurrences of previously occurring symbols held in a storage medium with weight factors which are greater for more recently occurring symbols than for less recently occurring symbols; and calculating a probability that the next occurring symbol will be the given symbol based on the weighted previous occurrences of the given symbol; wherein the step of weighting includes defining a plurality of intervals within the storage medium, the given symbol having a respective number of occurrences in each of the plurality of intervals, the previously occurring symbols being weighted according to the number of intervals within which the previously occurring symbols fall.
Claim 2
Independent Claim
134 words
A method for estimating a probability that a given symbol of a finite alphabet will occur in a symbol string of symbol of the finite alphabet, the method comprising the steps of: weighting occurrences of previously occurring symbols held in a storage medium with weight factors which are greater for more recently occurring symbols than for less recently occurring symbols; and calculating a probability that the next occurring symbol will be the given symbol based on the weighted previous occurrences of the given symbol; wherein the step of weighting includes defining a plurality of intervals within the storage medium, the given symbol having a respective number of occurrences in each of the plurality of intervals, the previously occurring symbols being weighted according to the number of intervals within which the previously occurring symbols fall.
Claim 3
Dependent Claim
32 words
A method ns recited in claim 1, wherein the step of calculating includes calculating the probability based on the respective numbers of occurrences of the given symbol in the plurality of intervals.
Claim 4
Dependent Claim
23 words
The method of claim 2 wherein the step of defining includes defining a number of intervals equal to an integral power of 2.
Claim 5
Dependent Claim
24 words
The method of claim 2 wherein the step of defining includes defining the intervals as having lengths, ratios therebetween being integral powers of two.
Claim 6
Dependent Claim
17 words
The method of claim 2 wherein the step of defining includes defining the intervals as being nested.
Claim 7
Dependent Claim
44 words
The method of claim 5 wherein the step of defining includes defining each interval of the plurality of intervals to include a most recently arrived symbol of the interval, the most recently arrived symbol being the same for each of the plurality of intervals.
Claim 8
Dependent Claim
44 words
The method of claim 2 wherein: the method further comprises the step of initially calculating and storing a probability; and the step of calculating includes (i) calculating a change of probability, and (ii) modifying the stored probability in accordance with the change of probability.
Claim 9
Dependent Claim
67 words
The method of claim 7 wherein the step of initially calculating and storing includes: identifying a first portion of the symbol string residing within the plurality of intervals; counting the number of occurrences of the given symbol in each of the plurality of intervals; normalizing the numbers of occurrences within the plurality of intervals; calculating an average of the normalized numbers of occurrences; and storing the average.
Claim 10
Dependent Claim
63 words
The method of claim 7 wherein the step of calculating a change of probability includes: (i) determining whether a new symbol of the symbol string, which is entering each of the intervals, is the given symbol, and (ii) determining, for each of the plurality of intervals, whether an old symbol of the symbol string, which is leaving the interval, is the given symbol.
Claim 11
Dependent Claim
102 words
The method of claim 9 wherein the step of calculating a change of probability includes calculating a magnitude value having a respective component corresponding to each of the plurality of intervals, each respective component having: (i) a first value if the new symbol and the old symbol both match the given symbol, or if neither the new symbol nor the old symbol match the given symbol, and (ii) a second value if one of the new symbol and the old symbol matches the given symbol, but the other of the new symbol and the old symbol does not match the given symbol.
Claim 12
Dependent Claim
46 words
The method of claim 10 wherein the step of modifying includes: (i) adding the magnitude to the stored probability if the new symbol matches the given symbol, and (ii) subtracting the magnitude from the stored probability if the new symbol does not match the given symbol.
Claim 13
Dependent Claim
23 words
The method of claim 10 wherein the step of calculating the magnitude value includes weighting the respective components according to respective weight factors.
Claim 14
Dependent Claim
50 words
The method of claim 12 wherein the step of calculating a magnitude value includes calculating a number having a plurality of digits in a number system of a given radix, the digits respectively corresponding with the intervals, the respective weight factors corresponding with reciprocals of integral powers of the radix.
Claim 15
Dependent Claim
41 words
The method of claim 13 wherein the step of calculating a magnitude value includes calculating a binary number having a plurality of binary digits respectively corresponding with the intervals, the respective weight factors corresponding with reciprocals of integral powers of two.
Claim 16
Dependent Claim
58 words
The method of claim 12 wherein the step of calculating a magnitude value includes calculating a plurality of numbers, each of the plurality of numbers having a plurality of digits in a number system of a given radix, the digits respectively corresponding with the intervals, the respective weight factors corresponding with reciprocals of integral powers of the radix.
Claim 17
Independent Claim
136 words
An apparatus for estimating a probability that a given symbol of a finite alphabet will occur in a symbol string of symbols of the finite alphabet, the apparatus comprising: means for storing previously occurring symbols; means for weighting the stored symbols with weight factors that are greater for more recently occurring symbols than for less recently occurring symbols; and means for calculating the probability that the next occurring symbol will be the given symbol based on the weighted previous occurrences of the given symbol; wherein the means for weighting includes means for defining a plurality of intervals within the storage means, the given symbol having a respective number of occurrences in each of the plurality of intervals, the previously occurring symbols being weighted according to the number of intervals within which the previously occurring symbols fall.
Claim 18
Independent Claim
136 words
An apparatus for estimating a probability that a given symbol of a finite alphabet will occur in a symbol string of symbols of the finite alphabet, the apparatus comprising: means for storing previously occurring symbols; means for weighting the stored symbols with weight factors that are greater for more recently occurring symbols than for less recently occurring symbols; and means for calculating the probability that the next occurring symbol will be the given symbol based on the weighted previous occurrences of the given symbol; wherein the means for weighting includes means for defining a plurality of intervals within the storage means, the given symbol having a respective number of occurrences in each of the plurality of intervals, the previously occurring symbols being weighted according to the number of intervals within which the previously occurring symbols fall.
Claim 19
Dependent Claim
34 words
An apparatus as recited in claim 16 wherein the means for calculating includes means for calculating the probability based on the respective numbers of occurrences of the given symbol in the plurality of intervals.
Claim 20
Dependent Claim
25 words
The apparatus of claim 17 wherein the means for defining includes a memory device having an input for sequentially receiving symbols of the symbol stream.
Claim 21
Dependent Claim
19 words
The apparatus of claim 18 wherein the memory device includes one of a shift register and a circular buffer,
Claim 22
Dependent Claim
44 words
The apparatus of claim 18 wherein the device has a plurality of outputs, respectively corresponding with the plurality of intervals, for providing symbols of the symbol string leaving the respective intervals concurrently with the reception of symbols of the symbol stream at the input.
Claim 23
Dependent Claim
25 words
The apparatus of claim 20 wherein the means for defining includes means for defining a number of intervals equal to an integral power of 2.
Claim 24
Dependent Claim
30 words
The apparatus of claim 20 wherein the means for defining includes means for defining the intervals making up the plurality as having lengths, ratios therebetween being integral powers of two.
Claim 25
Dependent Claim
44 words
The apparatus of claim 20 wherein the means for defining includes defining each interval of the plurality of intervals to include a most recently arrived symbol of the interval, the most recently arrived symbol being the same for each of the plurality of intervals.
Claim 26
Dependent Claim
45 words
The apparatus of claim 17 wherein: the apparatus further comprises means for initially storing a probability: and the means for calculating includes: (i) means for calculating a change of probability, and (ii) means for modifying the stored probability in accordance with the change of probability.
Claim 27
Dependent Claim
63 words
The apparatus of claim 24 wherein the means for calculating a change of probability includes: means for determining whether a new symbol of the symbol string, which is entering each of the intervals, is the given symbol; and determining, for each of the plurality of intervals, whether an old symbol of the symbol string, which is leaving the interval, is the given symbol.
Claim 28
Dependent Claim
104 words
The apparatus of claim 25 wherein the means for calculating a change of probability includes means for calculating a magnitude value having a respective component corresponding to each of the plurality of intervals, each respective component having: (i) a first value if the new symbol and the old symbol both match the given symbol, or if neither the new symbol nor the old symbol match the given symbol, and (ii) a second value if one of the new symbol and the old symbol matches the given symbol, but the other of the new symbol and the old symbol does not match the given symbol.
Claim 29
Dependent Claim
17 words
The apparatus of claim 26 wherein the means for calculating a change of probability includes logic circuitry.
Claim 30
Dependent Claim
13 words
The apparatus of claim 26 wherein logic circuitry includes EXCLUSIVE OR (XOR) circuitry.
Claim 31
Dependent Claim
48 words
The apparatus of claim 26 wherein the means for modifying includes: means for adding the magnitude to the stored probability if the new symbol matches the given symbol, and means for subtracting the magnitude from the stored probability if the new symbol does not match the given symbol.
Claim 32
Dependent Claim
49 words
The apparatus of claim 29 wherein the means for modifying includes an adder/subtractor having a control input coupled to receive a signal having a first value if the new symbol matches the given symbol, and having a second value if the new symbol does not match the given symbol.
Claim 33
Dependent Claim
25 words
The apparatus of claim 26 wherein the means for calculating the magnitude value includes means for weighting the respective components according to respective weight factors.
Claim 34
Dependent Claim
52 words
The apparatus of claim 31 wherein the means for calculating a magnitude value includes means for calculating a number having a plurality of digits in a number system of a given radix, the digits respectively corresponding with the intervals, the respective weight factors corresponding with reciprocals of integral powers of the radix.
Claim 35
Dependent Claim
43 words
The apparatus of claim 32 wherein the means for calculating a magnitude value includes means for calculating a binary number having a plurality of binary digits respectively corresponding with the intervals, the respective weight factors corresponding with reciprocals of integral powers of two.
Claim 36
Dependent Claim
60 words
The apparatus of claim 31 wherein the means for calculating a magnitude value includes means for calculating a plurality of numbers, each of the plurality of numbers having a plurality of digits in a number system of a given radix, the digits respectively corresponding with the intervals, the respective weight factors corresponding with reciprocals if integral powers of the radix.
Claim 37
Dependent Claim
169 words
A data encoding system for adaptively and predictively encoding a string of symbols, from a finite alphabet which comprises a plurality of symbols, in accordance with frequencies of occurrence of the symbols in the string, the system comprising: a context extractor for receiving the symbol string to be encoded, the context extractor having an input for receiving each successive symbol of the string as a new symbol, and having a plurality of intervals and respective outputs for each of the plurality of intervals, the outputs being for providing successive final symbols of the intervals as respective old symbols; and a plurality of probability estimators respectively corresponding to given ones of the plurality of symbols in the finite alphabet, each of the probability estimators including circuitry for receiving the new symbol and the old symbols, and for updating a probability value for the occurrence of the given symbol corresponding thereto based on whether the new symbol matches the given symbol, and whether the respective old symbols match the given symbol.
Claim 38
Dependent Claim
169 words
A data encoding system for adaptively and predictively encoding a string of symbols, from a finite alphabet which comprises a plurality of symbols, in accordance with frequencies of occurrence of the symbols in the string, the system comprising: a context extractor for receiving the symbol string to be encoded, the context extractor having an input for receiving each successive symbol of the string as a new symbol, and having a plurality of intervals and respective outputs for each of the plurality of intervals, the outputs being for providing successive final symbols of the intervals as respective old symbols; and a plurality of probability estimators respectively corresponding to given ones of the plurality of symbols in the finite alphabet, each of the probability estimators including circuitry for receiving the new symbol and the old symbols, and for updating a probability value for the occurrence of the given symbol corresponding thereto based on whether the new symbol matches the given symbol, and whether the respective old symbols match the given symbol.
Claim 39
Dependent Claim
19 words
The system of claim 35, wherein the context extractor includes one of a shift register and a circular buffer.
Claim 40
Dependent Claim
70 words
The system of claim 35 wherein each probability estimator includes: a probability register for storing the probability value for the occurrence of the given symbol; circuitry for calculating a probability update value based on whether new symbol matches the given symbol and whether the respective old symbols match the given symbol; and circuitry for updating the probability value stored in the probability register in accordance with the probability update value.
Claim 41
Dependent Claim
15 words
The system of claim 37 wherein the circuitry for calculating includes EXCLUSIVE OR (XOR) circuitry.
Claim 42
Dependent Claim
53 words
The system of claim 37 wherein the circuitry for updating includes an adder/subtractor which (i) adds the probability update value to the stored probability if the new symbol matches the given symbol, and (ii) subtracts the probability update value from the stored probability if the new symbol does not match the given symbol.
Claim 43
Dependent Claim
182 words
A computer program product, for use with a data encoding system which receives and encodes a symbol stream according to a coding scheme based on frequencies of past occurrences of symbols within the symbol stream, the computer program product comprising: a recording medium; means, recorded on the recording medium, for directing the data encoding system to weight occurrences of previously occurring symbols within the symbol stream with weight factors which are greater for more recently occurring symbols than for less recently occurring symbols; means, recorded on the recording medium, for directing the data encoding system to calculate a probability that the next occurring symbol in the symbol stream will be a given one of the symbols based on the weighted previous occurrences of the given symbol; wherein the means for directing to weight includes means, recorded on the recording medium, for directing the data encoding system to define a plurality of intervals within which the previously occurring symbols of the symbol stream fall, the previously occurring symbols being weighted according to which of the intervals within which the previously occurring symbols fall.
Claim 44
Dependent Claim
182 words
A computer program product, for use with a data encoding system which receives and encodes a symbol stream according to a coding scheme based on frequencies of past occurrences of symbols within the symbol stream, the computer program product comprising: a recording medium; means, recorded on the recording medium, for directing the data encoding system to weight occurrences of previously occurring symbols within the symbol stream with weight factors which are greater for more recently occurring symbols than for less recently occurring symbols; means, recorded on the recording medium, for directing the data encoding system to calculate a probability that the next occurring symbol in the symbol stream will be a given one of the symbols based on the weighted previous occurrences of the given symbol; wherein the means for directing to weight includes means, recorded on the recording medium, for directing the data encoding system to define a plurality of intervals within which the previously occurring symbols of the symbol stream fall, the previously occurring symbols being weighted according to which of the intervals within which the previously occurring symbols fall.
Claim 45
Dependent Claim
59 words
A computer program product as recited in claim 40 wherein the means for directing to define includes means, recorded on the recording medium, for directing the data encoding system to define the intervals as each including the most recently arrived symbol of the symbol stream, and as including respective numbers of consecutively arrived symbols ranging backward in time therefrom.
Claim 46
Dependent Claim
54 words
A computer program product as recited in claim 41, wherein the means for defining includes means, recorded on the recording medium, for directing the data encoding system to define: (i) a number of intervals equal to an integral power of two, and (ii) lengths of the intervals having ratios of integral powers of two.
Claim 47
Dependent Claim
100 words
A computer program product as recited in claim 41, wherein the means for directing to calculate includes means, recorded on the recording medium, for directing the data encoding system to: (i) initially calculate and store probabilities for each symbol based on past occurrences of each symbol, (ii) calculate, responsive to receipt of a new symbol of the symbol stream, a change of probability for each symbol based on the new symbol and a respective old symbol leaving each interval as the new symbol enters each interval, and (iii) modify the stored probabilities in accordance with the calculated changes of probability.
References Cited (Backward Citations)
US3769453A
Cited
US4325085A
Cited
US4355306A
Cited
US4516246A
Cited
US4591908A
Cited
US4633490A
Cited
US4791403A
Cited
US4933883A
Cited
US4891643A
Cited
US4905297A
Cited
US4935882A
Cited
US4725885A
Cited
US4862167A
Cited
US4785356A
Cited
US5025258A
Cited
US5023611A
Cited
US4973961A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-10-17 | 1998-04-18 | 1998-10-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-10-17 | 2002-04-18 | 2002-10-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-10-17 | 2006-04-18 | 2006-10-18 | $7700.00 | Window Closed / Lapsed |