Lecture 10 min.
Arithmetic coding is one of the entropy compression algorithms.
Unlike the Huffman algorithm, it has no rigid, fixed correspondence between input symbols and groups of bits in the output stream. This gives the algorithm greater flexibility in representing fractional symbol frequencies.
It generally outperforms the Huffman algorithm in compression efficiency and can compress data with an entropy of less than 1 bit per encoded symbol, but some versions are subject to patent restrictions from IBM.
It provides a nearly optimal compression ratio in terms of Shannon's entropy estimate of coding. Each symbol requires almost 
bits, where is the information entropy of the source.
Unlike the Huffman algorithm, arithmetic coding is highly efficient for fractional, non-uniform probability distributions of the encoded symbols. However, in the case of equiprobable symbols, for example for the bit string 010101…0101 of length s, arithmetic coding approaches the Huffman prefix code and may even take one bit more.
Suppose we have an alphabet and, optionally, data on the frequency of use of its symbols. Consider the segment from 0 to 1 on the coordinate line.
Call this segment the working segment. Place points on it so that the lengths of the resulting segments equal the frequency of use of a symbol, and each such segment corresponds to one symbol.
Now take a symbol from the stream and find its segment among the ones just formed; this segment now becomes the working segment. Divide it in the same way as the segment from 0 to 1 was divided. Perform this operation for a certain number of consecutive symbols. Then choose any number from the working segment. The bits of this number, together with the length of its binary representation, are the result of arithmetic coding of the used stream symbols.
Using arithmetic coding, one can achieve a nearly optimal representation for a given set of symbols and their probabilities (according to Shannon's source entropy coding theory, the optimal representation tends to −log2P bits for each symbol whose probability is P). Data compression algorithms that use arithmetic coding build a model of the input data before the actual encoding, based on quantitative or statistical characteristics, as well as on repetitions or patterns found in the sequence being encoded, that is, any additional information that helps refine the probability P of a symbol occurring during encoding. Obviously, the more accurately the symbol probability is determined or predicted, the higher the compression efficiency.
Consider the simplest case of a static model for encoding information coming from a signal processing system. The signal types and their corresponding probabilities are distributed as follows:
For the decoder, the appearance of the last symbol means that the entire sequence has been successfully decoded (as an alternative approach, though not necessarily a more successful one, a fixed-length block algorithm can be used).
It should also be noted that any set of symbols can be treated as the alphabet of the method's probability model, depending on the specifics of the problem being solved. More heuristic approaches that use the basic arithmetic coding scheme employ dynamic or adaptive models. The idea of these methods is to refine the probability of the symbol being encoded by taking into account the probability of the preceding or future context (that is, the probability of the symbol occurring after a certain number k of symbols to the left or right, where k is the order of the context).
Take the following sequence as an example:
NEUTRAL NEGATIVE END-OF-DATA
First, divide the segment from 0 to 1 according to the signal frequencies. We divide the segment in the order given above: NEUTRAL from 0 to 0.6; POSITIVE from 0.6 to 0.8; NEGATIVE from 0.8 to 0.9; END-OF-DATA from 0.9 to 1.
Now start encoding with the first symbol. The first symbol, NEUTRAL, corresponds to the segment from 0 to 0.6. Divide this segment in the same way as the segment from 0 to 1.
Encode the second symbol, NEGATIVE. Within the segment from 0 to 0.6, it corresponds to the segment from 0.48 to 0.54. Divide this segment in the same way as the segment from 0 to 1.
Encode the third symbol, END-OF-DATA. Within the segment from 0.48 to 0.54, it corresponds to the segment from 0.534 to 0.54.
Since this was the last symbol, encoding is complete. The encoded message is the segment from 0.534 to 0.54, or any number in it, for example 0.538.
Suppose we need to decode a message by arithmetic coding according to the model described above. The message in encoded form is represented by the fractional value 0.538 (for simplicity, decimal rather than binary representation of the fraction is used). It is assumed that the encoded message contains exactly as many digits in the number under consideration as are needed to unambiguously restore the original data.
The initial state of the decoding process is the same as in encoding, and the interval [0,1) is considered. Based on the known probability model, the fractional value 0.538 falls into the interval [0, 0.6). This determines the first symbol chosen by the encoder, so its value is output as the first symbol of the decoded message.
Arithmetic coding is a method that allows input alphabet symbols to be packed losslessly, provided the frequency distribution of these symbols is known. Arithmetic coding is optimal, reaching the theoretical limit of the compression ratio. Arithmetic coding is block-based and the output code is unique for each possible input message; it cannot be split into codes of individual symbols, unlike Huffman codes, which are non-block, i.e. each letter of the input alphabet is assigned a specific output code.
Text compressed by an arithmetic coder is regarded as a binary fraction from the interval [0, 1). The compression result can be represented as a sequence of binary digits from the notation of this fraction. Each symbol of the source text is represented by a segment on the number line whose length equals the probability of its occurrence and whose start coincides with the end of the segment of the symbol preceding it in the alphabet. The sum of all segments must obviously equal one. If at each step the current interval is regarded as a whole, then each newly arriving input symbol "cuts out" of it a subinterval proportional to its length and position.
Constructing the interval for the message "ABVG...":
 |
Let us explain how the method works with an example:
Suppose the alphabet consists of two symbols, “a” and “b”, with probabilities 3/4 and 1/4 respectively.
Consider the interval [0, 1), open on the right. We divide it into parts whose lengths are proportional to the symbol probabilities. In our case these are [0, 3/4) and [3/4, 1). The essence of the algorithm is as follows: each word over the input alphabet corresponds to some subinterval of [0, 1). The empty word corresponds to the whole interval [0, 1). After receiving each successive symbol, the arithmetic coder narrows the interval, choosing the part that corresponds to the newly received symbol. The code of the message is the interval obtained after all of its symbols have been processed, or more precisely, the number of minimal length lying within this interval. The length of the resulting interval is proportional to the probability of occurrence of the text being encoded.
Let us run the algorithm on the string “aaba”:
| Step | Processed string | Interval |
| 0 | “” | [0, 1) = [0, 1) |
| 1 | “a” | [0, 3/4) = [0, 0.11) |
| 2 | “aa” | [0, 9/16) = [0, 0.1001) |
| 3 | “aab” | [27/64, 36/64) = [0.011011, 0.100100) |
| 4 | “aaba” | [108/256, 135/256) = [0.01101100, 0.10000111) |
At the first step we take the first 3/4 of the interval, corresponding to the symbol "a", and then keep only 3/4 of that again. After the third step, only the right quarter of the previous interval remains, in accordance with the position and probability of the symbol "b". Finally, at the fourth step we keep only the first 3/4 of the result. This is the interval to which the original message belongs.
Any number from the range obtained at step 4 can be taken as the code. The question arises: "Where is the compression here? The original text could be encoded with four bits, but we obtained an eight-bit interval." The point is that as the code we can choose, for example, the shortest code within the interval, equal to 0.1, and obtain a fourfold reduction in the size of the text. By comparison, Huffman coding would not be able to compress such a message, although in practice the gain is usually small and preference is given to the simpler and faster algorithm from the previous section.
The arithmetic decoder works in synchrony with the coder: starting from the interval [0, 1), it determines the symbols of the input string one after another. In particular, in our case it will first divide the interval [0, 1) (in proportion to the symbol frequencies) into [0, 0.11) and [0.11, 1). Since the number 0.1 (the code of the string "aaba" transmitted by the coder) lies in the first of them, the first symbol can be obtained: "a". Then we divide the first subinterval [0, 0.11) into [0, 0.1001) and [0.1001, 0.1100) (in proportion to the symbol frequencies). Again we choose the first one, since 0 < 0.1 < 0.1001. Continuing this process, we unambiguously decode all four symbols.
Two problems arise with this method: first, it requires real-number arithmetic of, generally speaking, unbounded precision, and second, the result of encoding becomes known only when the input stream ends. Further research, however, showed that one can do practically without loss with integer arithmetic of small precision (16-32 bits), and also make the algorithm incremental: the digits of the code can be output sequentially as the input stream is read.
Like the Huffman algorithm, the arithmetic coder is also two-pass and requires the table of symbol frequencies to be transmitted along with the encoded text. In general, these algorithms are very similar and can easily be interchanged. Consequently, an adaptive arithmetic coding algorithm exists, with all the resulting advantages and disadvantages. Its main difference from the static one is that the new probability intervals are recalculated after each successive symbol is received from the input stream.
Comments