Adaptive computation of symbol probabilities in n-ary strings
First Claim
1. 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.
1 Assignment
0 Petitions
Accused Products
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.
123 Citations
43 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. 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. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. 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. - View Dependent Claims (36, 37, 38, 39)
-
-
40. 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. - View Dependent Claims (41, 42, 43)
-
Specification