0
$\begingroup$

Theoretically, if I try to compress some data I decrease the length of the data. I will give very simple example just for the sake of the example, in practice it will be similar but with much bigger values. For example: The original data is 2 bytes and I compress it to 1 byte (real example will be more like 1000000 to 900000, but I take 2 bytes for simplicity). So, the original data has 65536 possible combinations, but the compressed data has only 256 combinations. Let's say, I put this data to the files. It means, if I compress 65536 possible different original files I will get only 256 different compressed files. It means again, that for each 256 original files there will be the same compressed files.

In future, I will not be able to uncompress it and distinguish between different original files, because compressed files are the same.

Specific example:

1st Original file (2 bytes): 254, 255

1st compressed file (1 byte): 128

2nd Original file (2 bytes): 198, 199

2nd compressed file (1 byte): 128

So, for 2 different original data, I might get the same compressed data.

The question: Does this kind of collision happen in real life with real compression programs such as zip, rar, etc.? If not, then why it does not happen if theoretically, it should?

UPDATE 1

Since the original example is a bit misleading I am putting a fully realistic example here.

If I have a file - 8192 bytes. It is 65536 bits. The total number of possible different files (permutations) is $2^{65536} \approx 2\times10^{19728}$. If, theoretically, I create all these files (permutations) in the folder (not possible of course). Each file is different. But if I want to create one more file of the same size, it will definitely be the same as the one of the existing file, because I created all possible combinations. Now I want to compress each file with zip with maximum possible compression. If I only count/record zip files, which are 2 times smaller (4096 bytes), then there are only $2^{32768} \approx 1.4 \times 10^{9864}$ combinations (different files).

So, the number of 4096 bytes files is much smaller than the number of 8192 bytes files and if I compress all 8192 bytes files, I should have collisions just because there are much fewer combinations of the compressed 4096 bytes files.

Even if I try to do 1-byte compression (compress 8192 bytes to 8191 bytes), then the number of combinations in case of 8191 bytes will be 256 times less than 8192 bytes.

UPDATE 2

I did some calculations. If I have an original file N bytes size and a compressed file less than N bytes (N-1 or less), then it is only 0.39% of cases when compression can be achieved without collisions. These are my calculations:

enter image description here

Looks like if I generate all possible files with the specific size of N bytes, then 0.39% can be compressed by 1 byte or more and the rest 99.61% is not possible to compress. In other words, the probability, that a random arbitrary file can be compressed is 0.39%. Is it correct? Are we so lucky that we often hit this 0.39%?

$\endgroup$
1
  • $\begingroup$ To answer your update: You're wrong in thinking that files with be half the size after compression, if you create all possible binary files, some will be smaller, some will stay the same size and some will even be larger after compression ! $\endgroup$
    – Nifil
    Commented Apr 23 at 6:22

2 Answers 2

2
$\begingroup$

Lossless compression means that you can take A, yield B (the result of compression), and then, having only B, restore A exactly.

If you have different A1 and A2 that both become B after compression, then such a compression cannot be lossless. Namely, it loses the information of whether it was A1 or A2.

Now, combining this fact with your examples, you should come to the following conclusion: no single lossless compression scheme can guarantee reduction for any possible input.

the probability, that a random arbitrary file can be compressed is 0.39%. Is it correct?

Yes. For any given compressor, most of its possible inputs can't be compressed. For practical compressors it is much lower than 0.39%. For example, when I tried gzip on 10000 files filled with random bytes, none of them reduced in size.

So, why do compressors work at all? It is not because of luck, but simply because they are designed to work with a (very) small subset of possible data: human-readable text-files and various binary formats, which focus on being easy to parse and write, rather than on being extremely succinct. Such data tend to be repetitive and to have very inefficient encoding (I mean, look at the HTML of this page).

$\endgroup$
6
  • $\begingroup$ If A is bigger (wider set) than B, then theoretically collision is possible just because of A has much more possible combinations than B. Was it mathematically proven that, for example, for zip algorithm collision is not possible? The practical test is not possible due to too many combinations. $\endgroup$
    – Zlelik
    Commented Apr 23 at 21:34
  • $\begingroup$ @Zlelik You seem to think that zip always reduces file size. This is false: some files become larger after the zipping. You can easily verify it on your own computer. $\endgroup$ Commented Apr 24 at 5:26
  • $\begingroup$ I understand that zip does not always reduce filesize. I did test it myself :). I did some calculations, that if I summarize all combinations of files which less than original file by 1 byte or more, than it is only 0.3906% of all possible combinations on the original file. I will put the details in the update 2. Have a look and put your comments if I understand it correctly. $\endgroup$
    – Zlelik
    Commented Apr 24 at 7:40
  • $\begingroup$ I put update 2. Now I think my question should be easier to understand. $\endgroup$
    – Zlelik
    Commented Apr 24 at 7:51
  • $\begingroup$ @Zlelik updated this answer $\endgroup$ Commented Apr 24 at 10:15
2
$\begingroup$

No, a lossless compression cannot have any collisions as by definition it must represent exactly the original data. The way you compress here would be a lossy compression where 198, 199 and 254, 255 is considered close enough to be mixed up.

As for the why, imagine you have a 8x8 black image (all pixels are "0"), the original file would have a matrix of 64 zeros, each written on 8 bits for examples. But in a compressed file you could just write "64" (1-byte) and "0" (1-byte) to say "repeat 0 64 times". The decompression algorithm can then recover the original image. In this example the compressed file is then 2 bytes long instead of 64 bytes. But it still represents exactly this specific image.

Of course real compression algorithms are more complex than that.

Note that the lossless compression do not have a fixed final size (unlike hash functions for example), they are limited by the entropy of the original file. So a very random file might not get any smaller once compressed.

To give another example, if you want to compress english text, you might want to represent the commonly found letters such as "e", "a", etc.. in only a few bits, whereas the uncommon letters "w", "z", etc... would be written with more bits, so you can represent the same data as originally but instead of using 8 bits for each letter like the ascii encoding, you save as many bits as possible with a smarter encoding

Followup from comments: An good example for an introduction to lossless compression is Shannon coding

$\endgroup$
5
  • $\begingroup$ Thank you for the answer. You mentioned "lossless compression cannot have any collisions as by definition". What is the definition of lossless compression (maybe give me a link if it is easier for you)? Also, my example is for lossless compression, not for lossy compression. 254, 255 just an example. I can change it for 101, 254, it does not matter. In any event, if I have N files with 1MB size. There are M different combinations. If I compress each file, then some of them becomes smaller and smaller file has fewer combinations by definition. So, why collision does not happen? $\endgroup$
    – Zlelik
    Commented Apr 22 at 12:08
  • $\begingroup$ @Zlelik In lossless compression, the operation of compressing and then decompressing the file must yield the exact original file (for example, ZIP files are lossless). Let's say you have many times a black image with just one pixel being different, and assume each image is 1MB. They can all be compressed as "repeat black pixel x times and then put color Y for the last pixel). All files will be smaller but they still don't collide because the original files had a lot of redundency $\endgroup$
    – Nifil
    Commented Apr 22 at 12:18
  • $\begingroup$ @Zlelik Now if you have many uniformly random images, each 1MB originally. Compressing them will have them still be very close to 1MB because they have a high entropy, whereas the black images have low entropy. I suggest you take a look at Shannon coding, I'll put a link in the answer $\endgroup$
    – Nifil
    Commented Apr 22 at 12:20
  • $\begingroup$ @Zlelik Something else to give you an intuition, when you compress a file, it's size gets closer to the theoretical limit given by the entropy, so compressing a compressed file is useless, it won't make it smaller. It's also why it's better to compress before encrypting a file, because the result of encryption is seemingly random so compressing after encryption doesn't make the content smaller. $\endgroup$
    – Nifil
    Commented Apr 22 at 12:28
  • $\begingroup$ I understand all of this, but I am asking from pure combinatorics and permutation point of view. Let me update the question with a better example. The original example looks like misleading. $\endgroup$
    – Zlelik
    Commented Apr 22 at 17:02

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.