File ArithmeticCoding.h

↰ Parent directory (ADS/compression)

The arithmetic code (section 12.2 of the notes), exact and in integers.

Definition (ADS/compression/ArithmeticCoding.h)

Detailed Description

A text S of n symbols, with the probabilities P[ :math:` sigma ` ] and the cumulative ones :math:` f_sigma = sum_{c < sigma} P[ c ] , is the interval [ l , l + s ) of [ 0 , 1 ) that the symbols narrow in turn, :math: s_i = s_{i - 1} P[ S[ i ] ] ` and :math:` l_i = l_{i - 1} + s_{i - 1} f_{S[ i ]} , so that :math: s_n = prod_i P[ S[ i ] ] ; the code is the first :math: lceil log_2 ( 2 / s_n ) rceil ` bits of :math:` l_n + s_n / 2 , a dyadic fraction inside the interval (Corollary 12.1), and hence at most :math: 2 + n H_0 ` bits (Theorem 12.3) [see File Entropy.h], against the :math:` n + n H_0 ` of the code of Huffman. arithmeticInterval(), arithmeticCodeExact() and arithmeticDecodeExact() do it in exact rationals [see File Rational.h], in time that grows with the length of the numbers; they are the reference for the integer coder, and they give the numbers of the example of the notes.

The integer coder is that of Witten, Neal and Cleary (section 12.2.6, the range coding of the notes): [ 0 , 1 ) is [ 0 , M ), :math:` M = 2^w , a probability is a count over a total T, and the interval [ L , H ) of a symbol of cumulative counts [ c , c’ ) is [ L + :math: lfloor r c / T rfloor ` , L + :math:` lfloor r c’ / T rfloor ` ), r = H - L, so that the intervals of the symbols tile the current one with no gap. After each symbol the interval is expanded: inside [ 0 , M / 2 ) it emits 0, inside [ M / 2 , M ) it emits 1, inside [ M / 4 , 3 M / 4 ) it emits nothing but counts an underflow, whose bit, the opposite of the next one emitted, follows that bit; so r stays above M / 4, and a total up to M / 4 keeps every interval of a symbol nonempty. At the end, 01 or 10 (and the pending bits) pick a point of the last interval. The decoder keeps the w bits read in v and finds the symbol whose interval holds v, with the same expansions; the bits past the end are zeros. With w = 32 the loss against the exact code is about :math:` 10^{-4} ` bits per symbol, as Witten, Neal and Cleary measured; the coders of the practice emit bytes instead of bits (the range coder of Martin), or use the asymmetric numeral systems of Duda, which reach the same compression with a table lookup per symbol.

The model can change at each symbol, as long as the decoder changes it in the same way. The adaptive coder starts from P[ :math:` sigma ` ] = 1 / | :math:` Sigma | and, after a prefix of length l with :math: l_sigma ` occurrences of :math:` sigma , takes P[ :math: sigma ` ] = :math:` ( l_sigma + 1 ) / ( l + |\Sigma| ) , so nothing is sent in advance; the counts are halved when their total passes :math: 2^{16} , which keeps it under M / 4 and makes the model follow a text whose statistics change. The cumulative counts are in a tree of Fenwick, where an increment, a prefix sum and the search of the symbol of a count take :math: O( log |\Sigma| ) ` time; so a symbol costs :math:` O( log |\Sigma| ) ` time and the code O( n log |\Sigma| ).

The contracts [see File Contract.h]: the probabilities are positive and sum to 1, the counts are positive with a total of at most M / 4, :math:` 2 le w le 32 , the alphabet of the adaptive coder has at most :math: 2^{20} ` symbols and a text only symbols of the model; decode( encode( x ) ) == x, an audit. The functions are defined in ArithmeticCoding.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 12

    1. Witten, R. M. Neal, J. G. Cleary, Arithmetic coding for data compression, Communications of the ACM 30(6), 520-540, 1987, doi:10.1145/214762.214771

    1. Howard, J. S. Vitter, Arithmetic coding for data compression, Proceedings of the IEEE 82(6), 857-865, 1994, doi:10.1109/5.286189

      1. Martin, Range encoding: an algorithm for removing redundancy from a digitised message, Video & Data Recording Conference, 1979

    1. Fenwick, A new data structure for cumulative frequency tables, Software: Practice and Experience 24(3), 327-336, 1994, doi:10.1002/spe.4380240306

  1. Duda, Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding, arXiv:1311.2540, 2013

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions