1

Is there a scientific limit to how much data can be compressed?

What I mean is, compression is essentially representing a larger amount of data with a smaller one, such as representing a=abc b=def etc... or you could have a database of larger chunks of data and represent them with a hash, write the hashes on a file, and rebuild it by replacing the hashes with their corresponding data, but here the birthday paradox comes in to play very early, for example, if you wanted to represent two digits with only one digit, one digit has a maximum combination of 10, whereas two digits has a maximum of 100 digits, which means the compression ratio here would be only 10% at best... is there any better way of compressing files?

Some way to store a large database of data combinations, represent them in a file that totals less than the original file, transfer it, and then rebuild it at its destination?

3
  • 3
    Given the right algorithm, there is no real limit for how much compression can occur if the actual information content is essentially zero. Eg, you could have a simple algorithm that compresses adjacent identical characters into an escape character, the repeated character, and a 2-byte count. So 65000 "A" characters could compress into 4 bytes. But if there's more information (entropy) in the data, there is less compression that can theoretically occur. Sep 14, 2013 at 1:57
  • @DanielRHicks That's a good answer. :) Sep 14, 2013 at 2:11
  • If you try and research the things you see on Silicon Valley, you will come up disappointed from an academic perspective, however you will find that much of the source of the content is even funnier than the content itself Jul 29, 2014 at 17:32

2 Answers 2

3

Shannon Entropy is the limit for loss-less data compression.

2
  • 4
    can you somehow give us the general idea behind it instead of relying exclusively on a Wikipedia link? if the link ever gets broken so does your whole answer. Sep 14, 2013 at 0:54
  • 3
    It should be noted that entropy makes my head hurt, but basically the amount of "information" in a stream of data is based on how unpredictable the next bit is, given all the bits that went before it. English text, eg, is moderately predictable, since certain characters tend to follow others, and you can (like the auto-speller in a cellphone) often predict a word based on the first few characters. The less predictable the data the higher its information content, and that places a theoretical limit on the amount of (lossless) compression possible. Sep 14, 2013 at 2:04
1

Well, it depends on your algorithm, your data, the length of your data, and how badly you want the exact data back. Data with less patterns in it will compress worse than data with more patterns in it.

I don't have any research to back it up, but your best-case scenario is likely going to be something like RLE or similar algorithm on a file full of zeroes or the same bytes.

With lossy compression you get into subjectives - i.e. compressing files into JPEG at the lowest quality settings can produce images that look little to nothing like the original image - but according to whom?

Not the answer you're looking for? Browse other questions tagged .