Inspired by this question: Does a simple photograph contain more information than a complex painting? Say that I have a discrete representation of some physical object - eg an image file. What is the true degree of "unpredictableness" or the size that a potential (lossless) compression scheme might never improve upon?
I could try to measure its entropy assuming that each element is independent. Or I could try to model dependency as eg neighbour correlation (1st order or higher order), remove it and then do my entropy estimate. Or I could apply some lossless entropy coding in a black-box fashion and measure the number of bits in the output.
But for a given file where no simplified generation model is assumed, is there any way to know how many bits of information it fundamentally «contains»?
If I do a few lines of MATLAB:
rng('default'); N = 1e6; x = randi([0 255], N, 1);
I get 1MB of presumably "good entropy" pseudo randomness. I assume that most lossless encoders are going to have a hard time finding any pattern in that - the compression ratio is going to be close to 1. However, if the bitstream allowed to inject MATLAB code and the encoder somehow recognized that particular stream, it could simply send an uncompressed 49 ascii codes ala : "do_MATLAB; rng('default'); randi([0 255], 1e6, 1)"
I fail to see how such a limit can be found. The number of ways to «re-represent» a file is practically infinite. We can always make a compression algorithm that works extremely well for one particular file (by incorporating implicit/explicit features of that file in the algorithm that is know beforehand by encoder as well as decoder, but that does not tell us anything useful. The extreme being a encoder/decoder that both contains the actual image and just transmits a bit saying "reproduce the image that you know"...
So perhaps an adhoc measure where you count the summed number of bits needed to:
- represent the information particular to the file, as well as
- some code written in a generic (touring complete?) programming language to decode the first piece of information? Itself compressed using some entropy coding suited to "typical" usages of that language
That still sounds like a "near infinite" volume to search, but at least you have an approach where you can tailor your encoding to the actual content - at the price of the added entropy of that tailoring? Now, what if you also want to have the possibility of embedding custom code in order to compress the size of the first code that is used to decompress the "payload"? That sounds like a solution biting its own tail.
If we include a large library of more or less related input (such as the most prominent million images from google image search), the size in bits of a compliant general decoder (description) (to be amortized among all of those images), and any "per image" particular decoder expression like above, we would have some idea about the average unpredictability of each file under the requirement that the whole thing was/could be optimized for global compression?
Or is the solution a more mundane "capture a large dataset relevant to your domain. Split it in two. Optimize your encoder globally for the training set. Apply that codec on the remainder of the dataset. Whatever file size is achieved for each file of the latter set is as close to an entropy measure that we are currently able to make"?