can anybody explain to me what data structure results after data is compressed? I just try to find out the difference between random data and compressed data, the entropy of both is very high while the distribution seems to be different (e.g. when I use chi-square-test).

i hope somebody can help me and thanks in advance! tom

  • $\begingroup$ You'll need to specify a specific compression algorithm. $\endgroup$ Aug 18, 2012 at 13:54
  • $\begingroup$ any compression algorithm, e.g. huffman $\endgroup$
    – tom
    Aug 18, 2012 at 16:03
  • $\begingroup$ There is no algorithm that can detect any kind of compressed data. It's only possible to detect specific compressed file formats. $\endgroup$ Aug 18, 2012 at 16:11
  • $\begingroup$ the program "ent" can do using the chi-square test (fourmilab.ch/random). I tried this test and it is possible to distinguish between compressed and random data, I just want to know how this is possible. $\endgroup$
    – tom
    Aug 18, 2012 at 17:15
  • $\begingroup$ i didnt take any specific file type but data from /dev/urandom $\endgroup$
    – tom
    Aug 18, 2012 at 17:19

1 Answer 1


Well, the data structure of a compressed data is whatever the decompression algorithm needs to be able to reconstruct the original data (assuming a lossless compression method; it's an approximation of the original data if we're talking about a lossy compression method).

That might not be the answer you're looking for; you might be looking for details on the actual format (and why it isn't precisely random). The problem is that the precise details depends on the compression method, and those details vary wildly.

As for why the compressed file doesn't look precisely like a random file, I can think of two reasons:

  • The compression technique doesn't try as hard as it could to compress the file as small as it could. A compression algorithm needs to meet several goals, one of which is compression efficiency, however another goal is computational efficiency. Because of the requirement for efficiency, the compression format may place things on bit boundaries; this may make the compression format distinguishable from random (an spending the extra time to squeeze out that (perhaps) 0.1% of compressed file length might not be worth it).

  • You might be detecting residual redundancy from the original file that the compression algorithm doesn't remove. Compression formats have a model of what redundancy looks like (and they work well only if the file they're given has those redundancies). However, even if the file does, real files tend to have subtle redundancies beyond what the compression algorithm expects; those redundancies would remain in the compressed file, and may be detectable.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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