0
$\begingroup$

I know that there is an inherent limit to how much you can compress data using lossless compression.

Basically, the only thing lossless compression can do is reduce dependencies between symbols, remove repetitions, and so on, so that the result looks more like completely random data rather than what we usually see.

From what I understand, nowadays the optimal method of compression, which gets very close to the theoretical optimum of making your data look like random garbage, is arithmetical coding that doesn't really operate on the level of characters at all, but this isn't used in most applications. (I'll save the why not? for a different question).

Instead, we use algorithms like DEFLATE that combine Huffman coding and LZ77 to achieve better efficiency than either alone.

How efficient are these algorithms, as commonly implemented, compared to the optimal efficiency?

Improve this question
$\endgroup$
4
  • $\begingroup$ What do you mean by efficiency? Do you mean the time it takes to compress, or the compression ratio? In any case, I doubt the question is answerable, as the answer may depend on the particular workload (the type of data you're processing) and the particular implementation of DEFLATE you're using. $\endgroup$ – D.W.♦ May 24 '17 at 20:43
  • $\begingroup$ I'm actually talking about the difference between the compression ratio achieved using DEFLATE and the maximum compression ratio theoretically possible, in terms of entropy. $\endgroup$ – GregRos May 25 '17 at 12:53
  • $\begingroup$ OK. Please edit the question accordingly, then, so people don't need to read the comments to understand your question. Efficiency often means running time. I don't see any mention about maximum theoretically possible compression ratio in the question. $\endgroup$ – D.W.♦ May 25 '17 at 16:32
  • $\begingroup$ Maximum compression ratio, you mean by a generic algorithm that does not know specifics about some file format? you might want to compare Compressed files of different methods. For example SEE: mattmahoney.net/dc/dce.html?#Section_214 Remember, which compression to use is not just how much compression, but how long are you going to wait, and how much computing resources do you have available? $\endgroup$ – Phillip Williams Jun 26 '17 at 5:31

Your Answer

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

Browse other questions tagged or ask your own question.