Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

closed as too broad by Mokubai, mpy, Scott, Nifle, Tog Sep 16 '13 at 13:36

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

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. – Daniel R Hicks Sep 14 '13 at 1:57
@DanielRHicks That's a good answer. :) – Ƭᴇcʜιᴇ007 Sep 14 '13 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 – OneChillDude Jul 29 '14 at 17:32

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

share|improve this answer
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. – Lorenzo Von Matterhorn Sep 14 '13 at 0:54
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. – Daniel R Hicks Sep 14 '13 at 2:04

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?

share|improve this answer

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