Arithmetic Coding

Arithmetic Coding
The main steps of arithmetic coding are as follows:-
1. Start by defining the “current interval” as [0,1).
2. Repeat the following two steps for each symbol S in the input stream:
2.1 Divide the current interval into subintervals whose sizes are proportional to the symbols probabilities.
2.2 Select the subinterval for S and define it as the new current interval.
3. When the entire input stream has been processed in this way, the output should be any number that uniquely identifies the current interval.
The symbols and probabilities are written on the output stream before any of the bits of the compressed code, and this will be the first thing input by the decoder. The encoding process starts by defining two variables LOW and HIGH which define an interval [LOW, HIGH) as follow:-
LOW=LOW+RANGE × LOWRANGE(X)
HIGH=LOW+RANGE × HIGHRANGE(X)
Where RANGE=HIGH-LOW, LOWRANGE(X) and HIGHRANGE(X) indicate the low and high limits of the range of symbol X, respectively. The method reads the input stream symbol by symbol and appends more bits to the code each time a symbol is input and processed.

The following example is a little more involved. We show the compression steps for the short string SWISS_MISS. Table 1 shows the information prepared in the first step (the statistical model of the data). The five symbols appearing in the input may be arranged in any order. For each symbol, its frequency is first counted, followed by its probability of occurrence (the frequency divided by the string size, 10). The range [0, 1) is then divided among the symbols, in any order, with each symbol getting a chunk, or a subrange, equal in size to its probability. Thus S gets the subrange [0.5, 1.0) (of size 0.5), whereas the subrange of I is of size 0.2 [0.2, 0.4).