Editing Arithmetic coding (section)

===Defining a model===

In general, arithmetic coders can produce near-optimal output for any given set of symbols and probabilities. (The optimal value is −log<sub>2</sub>''P'' bits for each symbol of probability ''P''; see ''[[Source coding theorem]]''.) Compression algorithms that use arithmetic coding start by determining a [[model (abstract)|model]] of the data – basically a prediction of what patterns will be found in the symbols of the message. The more accurate this prediction is, the closer to optimal the output will be.

'''Example''': a simple, static model for describing the output of a particular monitoring instrument over time might be:
*60% chance of symbol NEUTRAL
*20% chance of symbol POSITIVE
*10% chance of symbol NEGATIVE
*10% chance of symbol END-OF-DATA. ''(The presence of this symbol means that the stream will be 'internally terminated', as is fairly common in data compression; when this symbol appears in the data stream, the decoder will know that the entire stream has been decoded.)''

Models can also handle alphabets other than the simple four-symbol set chosen for this example. More sophisticated models are also possible: ''higher-order'' modelling changes its estimation of the current probability of a symbol based on the symbols that precede it (the ''context''), so that in a model for English text, for example, the percentage chance of "u" would be much higher when it follows a "Q" or a "q". Models can even be ''[[adaptive coding|adaptive]]'', so that they continually change their prediction of the data based on what the stream actually contains. The decoder must have the same model as the encoder.