File LempelZiv.h

↰ Parent directory (ADS/compression)

The compressors of Lempel and Ziv (chapter 13 of the notes), whose dictionary is the text itself: they replace a string seen before with a reference to it, and need no model of the source.

Definition (ADS/compression/LempelZiv.h)

Detailed Description

  • LZ77, lz77Parse(): the longest prefix :math:` alpha ` of the text still to parse that starts in the window of the last w symbols (and may end past it, overlapping the prefix itself) gives the triple :math:` langle d , |\alpha| , c rangle , d the distance of the copy and c the symbol after it (none at the end of the text), and the parse moves :math: |\alpha| + 1 ` symbols; the decoder copies one symbol at a time, which is right on an overlapping copy too. Among the longest prefixes the closest is chosen. A search over the window takes :math:` O( w ell ) ` time for a phrase of length :math:` ell , hence :math: O( n w ) ` in the worst case.

  • LZSS, lzssParse(): the variant of Storer and Szymanski emits either a copy :math:` langle d , ell rangle ` or a literal :math:` langle 0 , c rangle , a copy only if :math: ell ` reaches a minimum (1 in the notes, 3 in gzip). lzssParseHashed() finds the copies as gzip does: the positions are chained by the hash of the 3 symbols that start there, from the most recent, and the search follows the chain of the next 3 symbols within the window, up to a number of candidates (the levels of gzip trade the length of the copies for the speed with it); with no bound it gives the parse of lzssParse() with minimum 3. The encoding of the phrases (gzip uses one code of Huffman for the literals and the lengths and one for the distances) is apart: the codes of this folder apply to the fields.

  • LZ78, lz78Parse(): an explicit dictionary of phrases, kept in a trie, starts with the empty phrase 0; the longest phrase f that prefixes the rest of the text gives :math:` langle id( f ) , c rangle `, and fc becomes a new phrase, so the dictionary is closed under prefixes and the trie has one symbol per edge; a phrase costs one step of the trie per symbol. A text that ends inside a phrase f ends with the pair of the parent of f and its last symbol. When the dictionary has the given number of phrases it is discarded and restarts empty, one of the choices of the notes (freezing it and replacing the least recently used phrase are the others).

  • LZW, lzwEncode(): the variant of Welch starts with the 256 phrases of one byte and emits only the identifiers: the phrase f followed by c, fc not in the dictionary, gives id( f ), adds fc, and the next phrase starts at c. The decoder adds fc one step late, when it reads the next phrase f’, whose first symbol is c; if f’ is the phrase just to add, then :math:` c = f[ 1 ] ` and the phrase is :math:` f f[ 1 ] `.

All of them are universal: on the text of an ergodic source their bits per symbol tend to its entropy (Ziv and Lempel), and the number of phrases bounds the entropy of order k of every text (Kosaraju and Manzini), but with a term that vanishes slowly. The practice uses LZ77 with long windows and fast searches: the suffix trees or arrays of an unbounded window, and the parse that minimizes the bits rather than the phrases (Ferragina, Nitto and Venturini); LZMA, Zstandard and Brotli add context models and codes of the arithmetic family to the fields of the phrases.

The contracts [see File Contract.h]: the window and the number of phrases are positive, the minimum length of lzssParseHashed() is at least 3, the phrases decoded refer to symbols already decoded; decode( parse( x ) ) == x, an audit. The functions are defined in LempelZiv.tpp.

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

  1. Ziv, A. Lempel, A universal algorithm for sequential data compression, IEEE Transactions on Information Theory 23(3), 337-343, 1977, doi:10.1109/TIT.1977.1055714

  1. Ziv, A. Lempel, Compression of individual sequences via variable-rate coding, IEEE Transactions on Information Theory 24(5), 530-536, 1978, doi:10.1109/TIT.1978.1055934

    1. Storer, T. G. Szymanski, Data compression via textual substitution, Journal of the ACM 29(4), 928-951, 1982, doi:10.1145/322344.322346

    1. Welch, A technique for high-performance data compression, IEEE Computer 17(6), 8-19, 1984, doi:10.1109/MC.1984.1659158

    1. Kosaraju, G. Manzini, Compression of low entropy strings with Lempel-Ziv algorithms, SIAM Journal on Computing 29(3), 893-911, 1999, doi:10.1137/S0097539797331105

  1. Ferragina, I. Nitto, R. Venturini, On the bit-complexity of Lempel-Ziv compression, SIAM Journal on Computing 42(4), 1521-1541, 2013, doi:10.1137/120869511

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions