1
$\begingroup$

Lossless compression is not magic. It just gives the common patterns a short notation, compensating by the less common patterns ending up with a longer notation. By that logic, all lossless compression algorithms must sometimes give you a larger file back. A real world example of that is for instance giving a file containing 'a' and a line feed to gzip (2 bytes), it subsequently returns a 30 byte file. In general, compression tools do not break even for very small files.

My question is: Are some compression utilities bloating out larger files by some significant amount? (While "Give this file to 7z and watch you harddrive fail!" is cool, things like "This 4kb file will grow to 6kb." are also good.)

I can see a reason why such behaviour might not exist. If you for instance always put an extra bit to the output telling if the file is actually compressed, or just the original file in the cases where the compression fails, your output can never be worse than the original file plus 1 bit. I am however not sure if any such protection against unexpected large files is used.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I don't see how this is a question about computer science. It just seems to be, "Hey, are there any inputs that make some program behave badly?" Note that it's trivial to write a compression program that ensures that no string ever grows by more than one character (If the string has been compressed, store "0" followed by the compressed string; otherwise, store "1" followed by the original) so this just boils down to asking about the behaviour of software currently in use. $\endgroup$
    – David Richerby
    Jul 25, 2016 at 9:17
  • $\begingroup$ @DavidRicherby It is more like that compression programs can be written in one of two ways here, and I wonder what is actually chosen in practise. $\endgroup$
    – SE - stop firing the good guys
    Jul 25, 2016 at 9:31
  • $\begingroup$ Then that is not a question about computer science. $\endgroup$
    – David Richerby
    Jul 25, 2016 at 9:36
  • $\begingroup$ So this is a survey? This makes your question off-topic. $\endgroup$
    – Evil
    Jul 25, 2016 at 11:58

1 Answer 1

Reset to default
1
$\begingroup$

If you take vanilla RLE in bitmap which does not have any consecutive runs it will increase file size two times. It is apparently very rarely used fact that BMP, TIFF and PCX allows compression, (not all applications supporting these formats even implement RLE scheme). This is very pathological case and since it mostly increase file size it is abandoned.

Normal compression algorithms include information of failure, so instead of huge increase you can expect several bytes per chunk increase. In those that do not check there are three methods of checking how far we can increase file: take already compressed file, take encrypted file or find pathological cases from algorithm.

I have generated $256 \text{ bytes}$ file with consecutive numbers.
Compressed as 7z LZMA: $349 \text{ bytes}$, LZMA2:$356 \text{ bytes}$, Deflate or Deflate64: $400 \text{ bytes}$, bz2: $388 \text{ bytes}$, PPMd: $421 \text{ bytes}$ so not that cool.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Looking up BMP specs, it does indeed seem like it supports simple RLE. You learn something new every day. $\endgroup$
    – SE - stop firing the good guys
    Jul 25, 2016 at 0:40
  • $\begingroup$ @Hohmannfan are you interested in some more pathological cases or more sophisticated inputs? $\endgroup$
    – Evil
    Jul 25, 2016 at 0:57
  • $\begingroup$ Preferably something more sophisticated. Your 256 byte file is more an example of most algorithms not breaking even for small files. $\endgroup$
    – SE - stop firing the good guys
    Jul 25, 2016 at 1:05
  • $\begingroup$ Taking 4KB gives range of 4.11 to 4.29KB, while encrypted file boosts to 4.30KB. Random files behaves similarly. But it does not exceed 10% in simple attempts. To find some extreme (like with RLE) it will take some time, probably hot feeding data... $\endgroup$
    – Evil
    Jul 25, 2016 at 1:28
  • $\begingroup$ @Hohmannfan I know that it is hard to cut 256 bytes in archive, but keep in mind that you were looking for some kind of protection of file size, taking small input shows there is apparently none (it would work in files of any size, right?). $\endgroup$
    – Evil
    Jul 25, 2016 at 1:36

Your Answer

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

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