File PPM.h

↰ Parent directory (ADS/compression)

Prediction by partial matching (section 12.3 of the notes), the model of contexts of Cleary and Witten in the version C of Moffat, on the arithmetic coder [see File ArithmeticCoding.h].

Definition (ADS/compression/PPM.h)

Detailed Description

For each context :math:` alpha ` of length :math:` 0 le l le K ` the model counts how many times each symbol has followed :math:` alpha ` in the text seen so far. The symbol S[ i ] is coded in the longest context S[ i - l , i - 1 ] that has already seen it, starting from l = min( K , i ): each context on the way that does not predict it emits an escape, whose count in version C is the number q of the distinct symbols seen in the context, so that a symbol of count c( :math:` sigma ` ) in a context seen n times has probability :math:` c( sigma ) / ( n + q ) ` and the escape :math:` q / ( n + q ) ; after K + 1 escapes, the context of order -1 gives the same probability to every symbol. By the principle of exclusion (section 12.3.2), a context that escapes tells the decoder that the symbol is none of those it predicts, so the shorter contexts leave them out of their counts (the escape keeps its count q, as in the example of the notes), and the context of order -1 gives :math: 1 / ( |\Sigma| - q ) ; a context whose symbols are all excluded emits nothing. After each symbol the counts of all its contexts grow by one, and those of a context are halved when their total passes :math: 2^{16} `. The decoder repeats the same walk, reading the escapes instead of writing them.

Coding S[ i ] takes :math:` O( K ( K + sigma_K ) log n ) ` time, with :math:` sigma_K ` the largest number of symbols seen in a context, the contexts being in a balanced tree keyed by their strings; the practice keeps them in a trie of the contexts with links to the suffixes (Moffat), where the next context is a step away. The compression approaches the entropy of order K [see File Entropy.h], and that of the text grows with K up to 4 or 5 symbols, beyond which the escapes cost more than the longer contexts gain (section 12.3.3). The escape methods of the literature are A, :math:` 1 / ( n + 1 ) , and B, :math: q / n , of Cleary and Witten; C, here; D, :math: q / 2 n `; P, X and XC of Witten and Bell, from the symbols seen once; the PPMd of Shkarin estimates it from the statistics of similar contexts, and PPM* of Cleary, Teahan and Witten uses contexts of unbounded length.

The contracts [see File Contract.h]: :math:` K ge 0 , :math: 1 le |\Sigma| le 2^{16} `, a symbol in [ 0 , |\Sigma| ); ppmDecode( ppmEncode( x ) ) == x, an audit. The operations are defined in PPM.tpp.

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

    1. Cleary, I. H. Witten, Data compression using adaptive coding and partial string matching, IEEE Transactions on Communications 32(4), 396-402, 1984, doi:10.1109/TCOM.1984.1096090

  1. Moffat, Implementing the PPM data compression scheme, IEEE Transactions on Communications 38(11), 1917-1921, 1990, doi:10.1109/26.61469

    1. Witten, T. C. Bell, The zero-frequency problem: estimating the probabilities of novel events in adaptive text compression, IEEE Transactions on Information Theory 37(4), 1085-1094, 1991, doi:10.1109/18.87000

    1. Cleary, W. J. Teahan, I. H. Witten, Unbounded length contexts for PPM, Data Compression Conference, 52-61, 1995, doi:10.1109/DCC.1995.515495

  1. Shkarin, PPM: one step to practicality, Data Compression Conference, 202-211, 2002, doi:10.1109/DCC.2002.999958

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions