2
$\begingroup$

Say I have a file containing words from the English language. Not meaningful text, just a repetition of a few words. The original size is 1559454 bytes and it is compressed by a certain program to 75742 bytes. (A very good compressor, it seems.) Can I estimate the entropy of the source producing such file using essentially the byte reduction?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
2
$\begingroup$

Can I estimate the entropy of the source producing such file using essentially the byte reduction (when compressing the source's output)?

No, at least for Shannon entropy. Entropy is a characteristic of the source, that can't be determined from a finite sample of the output of the source. It's can't even be estimated in practice without information about what the source is, and the question gives no such information.

The best we can is estimate a plausible upper bound of the entropy of the source that generated the file: $75742/1559454$ entropy bit per output bit. That's not a mathematical certainty: it's mathematically possible that a perfectly random source generated that file (the probability is $2^{-8\times1559454}>0$). And that's not a practical certainty either, unless we add a vague hypothesis that the observed characteristic goes on: a device which output consists of the $1559454$ fixed bytes followed by indefinitely many uniformly random bytes is a source with $1$ entropy bit per output bit.

We do not get any lower bound better than $0$. Proof: any deterministic program that indefinitely outputs is a source with zero entropy. And it is trivial to make a deterministic program that indefinitely outputs a sequence starting with the $1559454$ bytes (perhaps, repeated). That's not merely theoretical:

  • The program which output consists of the repeated sequence of two bytes a produces output which first $1559454$ bytes matches the problem statement, even for some actual compressor; say, one that never compresses by more than a factor of 20 (that's quite plausible for e.g. an audio compressor).
  • Even if we restrict to files that could reasonably occur in actual use, it's entirely possible that a program designed to obfuscate a file into english words, written as an (elementary and rather poor) steganography tool, has output that matches the problem statement (for an actual text compressor) when fed as input a file of about $50000$ bytes, including if it is all-zero.

Conclusion: practical procedures that attempt to assess the entropy of a source from its output only are doomed to, at best, give a plausible upper bound of that entropy (and can do so only under the hypothesis that the output tested is representative). Computing a compression ratio is one such method.

Improve this answer
$\endgroup$
-1
$\begingroup$

In this case compression would be a terrible way to measure entropy; compressing the file would lead to a non-English result, guaranteeing your entropy calculations are next to useless (although technically correct). A better way for your case would be to do some math with the selection of the words.

Calculating entropy through compression is good for binary data, not text.

  • How many possible words are there to choose?
    • More words to choose from will mean greater entropy:word ratio.
  • How randomly are they selected? Does the word selector have near-perfect randomness?
    • The entropy of this selector will make or break your word entropy levels. This is the part to direct your focus to.
  • How many words do you have?
    • if each word is selected randomly from a set of $256$ words (with perfect entropy), then each word corresponds to $1$ random byte (8 bits of entropy).

Since the English language has words of varying lengths and structure calculating entropy through compression will lead to inconsistent results. If, however, you want to measure it through compression:

  • Your results will be in terms of the entropy:byte ratio, not the entropy:word ratio.
    • To correct for this, find the average byte length of all words in your sample, then divide the entropy by that average to get the entropy:word ratio.
  • Certain words will be more similar, thus looking to the compressor to have less entropy.
    • This cannot be corrected. You can only filter this as "noise" by taking more samples of different data.
    • If your file is constant (you're measuring a specific file, not a random word generator) this will forever contaminate your results. A larger file will, however, lessen this.
    • The entropy of the English language itself will affect your results. This will be the case no matter how many samples you take.
      • Certain words will appear to have less or more entropy than others, while in reality each word has the same amount of entropy if chosen randomly.
      • Your compression function doesn't know this.
  • A better compression function will lead to better results
    • The idea of using compression to measure entropy is to compare data to an "ideally compressed" version of itself. The closer you get to ideal compression the better your results.
    • Once compressed with an ideal compression function, you can take the output size divided by the input size (this should be between 0.0 and 1.0). If the ideal data has 1 bit per bit entropy, the data you tested must have the number you got before.
    • If the compression isn't ideal compression, which it isn't, you can take the compressed data's entropy (which requires you to know the entropy of the compressed data) and multiply by the size ratio from before.
      • Or, just assume your compressor is perfect and accept the resulting inaccuracy. This might be more practical.
      • You might be able to estimate the entropy of the compressed data by repeatedly applying the compression until you get perfect entropy (no compression). Then just multiply the size ratios as stated before.
        • This only works if the compression function can effectively compress its own output.
        • In this case you end up recursively measuring entropy.
  • For the best possible results, you could craft a compression function for your specific data.
    • If you have 65536 words, you can obtain ideal compression by converting each word to a unique 16-bit sequence. This only works if the number of words is a power of 2.
      • Unless the number of words is a power of 256, you must be able to handle bit-length data instead of byte-length. This will take some cleverness on your part.
      • If you want to audit your word selection, you must then compress this using a normal compression function (this becomes the data you test the entropy of).
        • This could remove many biases associated with compressing the English language.
        • In this case you end up recursively measuring entropy.

As you can see, it might be a lot better to do a little math on your word selection. If, however, you want to know the entropy of the word selector itself, you have no choice but to use compression.

And a final takeaway:

  • If every sample is generated by the same way, each sample will have equal entropy.
    • Your compression test will disagree and say different samples have different amounts of entropy.
    • Compression is a good way to estimate entropy, but it doesn't determine entropy.
      • You can simply take the average of many samples to find the actual entropy of each sample.
Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Sources have entropy, and the question is about that. Samples don't. $\endgroup$
    – fgrieu ♦
    Commented Sep 12, 2020 at 10:11
  • $\begingroup$ I do think that this answer starts off well, but that part in the middle for estimating entropy, I just cannot agree on it. Multiple compression rounds using the same technique? Is that even useful? What will it do when the sample contains next to no entropy? Will it produce zero bits? $\endgroup$
    – Maarten Bodewes ♦
    Commented Sep 12, 2020 at 10:35
  • $\begingroup$ The reason you use multiple compression rounds is to eventually obtain a sample with perfect entropy; if you keep compressing, eventually even a bad compression function should create a result with ideal entropy. $\endgroup$
    – Serpent27
    Commented Sep 12, 2020 at 17:31
  • $\begingroup$ What will it do when the sample contains next to no entropy? Will it produce zero bits? That's the idea (well, not zero but close to zero. If it had exactly zero entropy, the result could be exactly zero bits, but then there's no point in measuring the entropy anyway). $\endgroup$
    – Serpent27
    Commented Sep 12, 2020 at 17:33
  • $\begingroup$ Sources have entropy, and the question is about that. Samples don't. Tell that to howsecureismypassword.net $\endgroup$
    – Serpent27
    Commented Sep 12, 2020 at 17:35

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.