For traditional algorithms compressed data may vary, while decompression algorithm is always the same. Are there any approaches, when (de)compression algorithm is also changing to provide best compression level? One can think about splitting data as small chunks and for each small chunk iterate all possible (de)compression codes to get best compression. Is there any research or existing algorithms, utilizing ideas like that?

  • 1
    $\begingroup$ If there are multiple decompression algorithms, then how do I know which algorithm to use when given some compressed data? $\endgroup$ – Discrete lizard May 22 '18 at 17:56
  • $\begingroup$ This makes sense for lossy compression, but not for lossless compression. $\endgroup$ – Yuval Filmus May 22 '18 at 18:05
  • $\begingroup$ Probably you can store decompression algorithm code along with compressed data. $\endgroup$ – Stepan Yakovenko May 22 '18 at 19:47

Suppose the first byte of the compressed file indicates which decompression algorithm to use, and then you use that algorithm to decompress the rest. Sure, you could do that. Absolutely. Some compression formats already do exactly this.

That said, it's also possible to view this as a single decompression algorithm. The master algorithm looks at the first byte of the file and then branches to a subroutine that handles the rest of the file. That can be considered a single algorithm. So at a fundamental level there is no fundamental distinction that can be drawn.


DEFLATE the stock standard compression algorithm will do exactly that. There are 3 type of blocks differentiated by a 2 bit value at the start of each block:

  1. the raw bytes for when the other two won't make it any smaller
  2. compressed with a fixed huffman encoding when the custom tree would take too much space for what it would save
  3. compressed with a supplied huffman encoding

The size of each block is free to choose the compressor as it sees fit.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.