Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
You'll need to specify a specific compression algorithm. –  CodesInChaos Aug 18 '12 at 13:54
    
any compression algorithm, e.g. huffman –  tom Aug 18 '12 at 16:03
    
There is no algorithm that can detect any kind of compressed data. It's only possible to detect specific compressed file formats. –  CodesInChaos Aug 18 '12 at 16:11
    
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. –  tom Aug 18 '12 at 17:15
    
i didnt take any specific file type but data from /dev/urandom –  tom Aug 18 '12 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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