10
$\begingroup$

I'm trying to measure now much non redundant (actual) information my file contains. Some call this the amount of entropy.

Of course there is the standard p(x) log{p(x)}, but I think that Shannon was only considering it from the point of view of transmitting though a channel. Hence the formula requires a block size (say in bits, 8 typically). For a large file, this calculation is fairly useless, ignoring short to long distance correlations between symbols.

There are binary tree and Ziv-Lempel methods, but these seem highly academic in nature.

Compressibility is also regarded as a measure of entropy, but there seems to be no lower limit as to the degree of compression. For my file hiss.wav,

  • original hiss.wav = 5.2 MB
  • entropy via the Shannon formula = 4.6 MB
  • hiss.zip = 4.6 MB
  • hiss.7z = 4.2 MB
  • hiss.wav.fp8 = 3.3 MB

Is there some reasonably practicable method of measuring how much entropy exists within hiss.wav?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I don't understand what you mean by "highly academic". $\endgroup$
    – David Richerby
    Commented Aug 22, 2015 at 8:52
  • $\begingroup$ Dead 'ard. I would have thought that with the scale of research dollars globally expended on maximising data transmission and storage, there would be a more developed way of estimating how much of the darned stuff you're actually dealing with. I wouldn't have thought it beyond the realms of possibility that there would be a file utility that you pass over some data that outputs the theoretical entropy estimate. Just what are the telcos and disk manufacturers playing at? $\endgroup$
    – Paul Uszak
    Commented Aug 24, 2015 at 3:37

1 Answer 1

Reset to default
9
$\begingroup$

Entropy is a feature of a random variable. A given file has zero entropy, since it is constant. Entropy makes sense in many situation in which there is no channel, and you can apply it to a random ensemble of, say, WAV files, generated from a given source. In this case, your $x$ is the entire WAV file.

The actual WAV file (excluding the header) can be thought of being generated by some Markovian source. This source produces sounds amplitudes ("samples") in a sequence, each one depending on the ones preceding it. After running the process for very long, the entropy of each sample (more accurately, the conditional entropy given the preceding samples) gets very close to some limiting value, which we define to be the entropy of the source. The entropy of $N$ samples is $N$ times that number (in the limit; again, more accurately, we are measuring the conditional entropy). Lempel and Ziv showed that if the sample entropy is $H$ bits, then their algorithm compresses $N$ samples to $HN + o(N)$ bits, with high probability (the probability is over the samples). Lempel–Ziv compression is quite popular in practice, used for example in the popular gzip format.

Due to this result of Lempel and Ziv, the entropy of a source can be approximated by compressing a long sequence of samples using the Lempel–Ziv algorithm. This doesn't estimate the entropy of the specific samples, which is not a well-defined concept (a constant sequence has zero entropy), but rather the entropy of the source generating it.

A related concept is algorithmic entropy, also known as Kolmogorov complexity. It is the length of the shortest program generating your file. This quantity does make sense for an individual file. In the case of a file generated by a random source, the Lempel–Ziv theorem shows that the algorithmic entropy of a file is bounded, with high probability, by its Shannon entropy. Unfortunately, algorithmic entropy isn't computable, so it's more of a theoretical concept.

To complete the picture, I suggest reading Shannon's paper on Prediction and entropy of printed English for a different approach to estimating the entropy of a source.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I have. And the Schurmann & Grassberger paper. Based on their estimated entropies for English, it seems that the best entropy estimate we can get is via compression with a PAQ8 variant like fp8. There's and my results marry quite well for Shakespearean prose. $\endgroup$
    – Paul Uszak
    Commented Aug 24, 2015 at 3:32
  • $\begingroup$ The problem seems to be though that I would have thought that there must be a limiting theoretical value for a source's entropy. Determination by compression only reflects the efficiency of the compression algorithm. Empirically, your gzip is good, but 7z is better. And fp8 is a lot better as shown in my question. Could I find that hiss.wav only contains 10 bytes of total entropy when I use fp12000 in the far future? $\endgroup$
    – Paul Uszak
    Commented Sep 11, 2015 at 23:08
  • $\begingroup$ Entropy is not a property of a file; every individual file has zero entropy. Rather, entropy is a property of a random source. A measure of randomness which is appropriate for specific files is Kolmogorov complexity (also known as algorithmic entropy), but unfortunately this measure is not computable. $\endgroup$
    – Yuval Filmus
    Commented Sep 12, 2015 at 7:26
  • $\begingroup$ When you're compressing a file to estimate the entropy of a source, you use a theorem that guarantees that the rate of compression of data generated by the source approaches the entropy of the source. However, the actual compression utilities don't apply the vanilla Lempel–Ziv algorithm, but rather a more practical version of it. If you want to estimate entropy, perhaps you should reimplement the algorithm with this goal in mind. $\endgroup$
    – Yuval Filmus
    Commented Sep 12, 2015 at 7:28
  • $\begingroup$ I removed an unconstructive discussion; comments are not for lengthy discussions except for improving the post at hand. If you want to honestly discuss matters of entropy, please create a chat room. Remember to keep it civil. $\endgroup$
    – Raphael
    Commented Nov 20, 2018 at 21:11

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.