6

The ent program can be run on a file to give output such as the following:

Entropy = 4.731183 bits per byte.

Optimum compression would reduce the size of this 15731 byte file by 40 percent.

Chi square distribution for 15731 samples is 235086.62, and randomly would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 87.3796 (127.5 = random). Monte Carlo value for Pi is 4.000000000 (error 27.32 percent). Serial correlation coefficient is 0.140065 (totally uncorrelated = 0.0).

How does the program determine what "optimum compression" could achieve?

I note that this estimate is typically beaten even by gzip.

11

The entropy gives the variety of information contained in the file, i.e. a representation of the number of different values present in the file; optimum compression, or perhaps more accurately, optimum encoding, would use exactly that amount of storage.

In your case, the file is currently 15,731 bytes in length, but stores 4.731183 bits per byte; thus overall it contains 4.731183 × 15,731 bits of information, i.e. 74,426.24 bits of information, or 9,303.28 bytes. Optimum compression would yield a 9,304-byte file, which is 59.14% of the original. The same calculation can be done without referring to the file length: 4.733183 is 59.16% of 8. Expressed as a reduction, (8 - 4.733183) is 40.84% of 8, and that is the calculation performed in ent, truncating the percentage to an integer:

           printf("Entropy = %f bits per %s.\n", ent, samp);
           printf("\nOptimum compression would reduce the size\n");
           printf("of this %lld %s file by %d percent.\n\n", totalc, samp,
            (short) ((100 * ((binary ? 1 : 8) - ent) /
                  (binary ? 1.0 : 8.0))));

Real-world compression tools beat this by representing repetitions in a more concise way. Compare the results of

$ (printf %5000s; printf %5000s | tr ' ' '1') | ent
Entropy = 1.000000 bits per byte.

Optimum compression would reduce the size
of this 10000 byte file by 87 percent.

$ (printf %5000s; printf %5000s | tr ' ' '1') | gzip | wc -c
48

The input consists of a large number of bytes, but with only two distinct values, present in equal amounts, so the entropy is 1 bit per byte. ent considers that the input could be encoded using 1 bit per byte, i.e. eight times less. gzip however represents the runs of spaces and ones, and produces a file that’s 208 times smaller even with the gzip header.

1
  • 6
    Maybe worth pointing out that there are serious theoretical obstacles to producing a "better" measurement of "optimal compressibility"; Kolomogorov complexity, for instance, is provably uncomputable.
    – zwol
    Aug 5 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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