mardi 20 septembre 2016

LZMA parametrization

One fascinating property of the LZMA data compression format is that it is actually a family of formats with three numeric parameters that can be set:

  • The “Literal context bits” (lc) sets the number of bits of the previous literal (a byte) that will be used to index the probability model. With 0 the previous literal is ignored, with 8 you have a full 256 x 256 Markov chain matrix, with probability of getting literal j when the previous one was i.
  • The “Literal position” (lp) will take into account the position of each literal in the uncompressed data, modulo 2lp. For instance lp=1 will be better fitted for 16 bit data.
  • The pb parameter has the same role in a more general context where repetitions occur.

For instance when (lc, lp, pb) = (8, 0, 0) you have a simple Markov model similar to the one used by the old "Reduce" format for Zip archives. Of course the encoding of this Markov-compressed data is much smarter with LZMA than with "Reduce".
Additionally, you have a non-numeric parameter which is the choice of the LZ77 algorithm – the first stage of LZMA.

The stunning thing is how much the changes in these parameters lead to different compression quality. Let’s take a format difficult to compress as a binary data, losslessly: raw audio files (.wav), 16 bit PCM.
By running Zip-Ada's lzma_enc with the -b (benchmark) parameter, all combinations will be tried – in total, 900 different combinations of parameters! The combination leading to the smallest .lzma archive is with many .wav files (but not all) the following: (0, 1, 0) – list at bottom [1].
It means that the previous byte is useless for predicting the next one, and that the compression has an affinity with 16-bit alignment, which seems to make sense. The data seems pretty random, but the magic of LZMA manages to squeeze 15% off the raw data, without loss. The fortuitous repetitions are not helpful: the weakest LZ77 implementation gives the best result! Actually, pushing this logic further, I have implemented for this purpose a “0-level” LZ77 [2] that doesn’t do any LZ compression. It gives the best output for most raw sound data. Amazing, isn’t it? It seems that repetitions are so rare that they output a very large code through the range encoder, while weakening slightly and temporarily the probability of outputting a literal - see the probability evolution curves in the second article, “LZMA compression - a few charts”.
Graphically, the ordered compressed sizes look like this:



and the various parameters look like this:

The 900 parameter combinations

The best 100 combinations

Many thanks to Stephan Busch who is maintaining the only public data compression corpus, to my knowledge, with enough size and variety to be really meaningful for the “real life” usage of data compression. You find the benchmark @ http://www.squeezechart.com/ . Stephan is always keen to share his knowledge about compression methods.
Previous articles:
____
[1] Here is the directory in descending order (the original file is a2.wav).

37'960 a2.wav
37'739 w_844_l0.lzma
37'715 w_843_l0.lzma
37'702 w_842_l0.lzma
37'696 w_841_l0.lzma
37'693 w_840_l0.lzma
37'547 w_844_l2.lzma
...
32'733 w_020_l0.lzma
32'717 w_010_l1.lzma
32'717 w_010_l2.lzma
32'707 w_011_l1.lzma
32'707 w_011_l2.lzma
32'614 w_014_l0.lzma
32'590 w_013_l0.lzma
32'577 w_012_l0.lzma
32'570 w_011_l0.lzma
32'568 w_010_l0.lzma

[2] In the package LZMA.Encoding you find the very sophisticated "Level 0" algorithm

    if level = Level_0 then
      while More_bytes loop
        LZ77_emits_literal_byte(Read_byte);
      end loop;
    else
      My_LZ77;
    end if;

Hope you appreciate ;-)

Aucun commentaire:

Enregistrer un commentaire

Pasta!

My first online game (I mean, as an author)... Pasta! is a match-3 puzzle game. Free of charge, no in-app payment. Link on the ima...