3
$\begingroup$

If we compare multimedia and text, if we have n bytes of text and compare it with n bytes of video, then we would be likely to think that n bytes of text is "more" information than n bytes of video data. Is there a name or measure of this difference in data? Loosely speaking it is a "density" or a "quality" of information per unit.

$\endgroup$
  • 4
    $\begingroup$ Look up "entropy". $\endgroup$ – Yuval Filmus Jun 27 '16 at 22:33
  • 1
    $\begingroup$ Also, perhaps Kolmogorov complexity is relevant? $\endgroup$ – jmite Jun 28 '16 at 1:04
4
$\begingroup$

The classical measure of information is the entropy. Entropy measures the information content of a random source. Consider the case of text files: someone has generated some text, and she wants to communicate this text to you. Since you know that the text is in English, there is no need for her to spell out all the words in full; instead, she can replace each word by its index in some dictionary. Most of the time this scheme will be very efficient, but sometimes she might use uncommon words, and then the scheme could fare less well.

More generally, the entropy of a random source is the average number of bits that need to be communicated in order to guarantee that the receiver decodes the message successfully with high probability. You can check out the formal definition in textbooks on information theory, in Wikipedia, or in Shannon's classical paper from 1948 (still the best source on the subject).

Suppose now that you have a given text file. What is its entropy? Under the definition above, its entropy is zero: if both parties know that the text being communicated is this one particular text, then there is no need to pass any information; there is no uncertainty. Randomness and uncertainty underline the concept of knowledge which entropy tries to capture.

There are at least two ways out of this paradox. The first way is to use a universal compression mechanism, like Lempel-Ziv compression. This is a compression scheme that achieves the entropy (with small error) for all long random sources which are well behaved. If you apply such a universal compression mechanism on a random text file, on average you get roughly the entropy of the random source generating the text file. Therefore one way to estimate the entropy of the mechanism generating your text files is by compressing a given text file.

Another way out of the paradox is Kolmogorov complexity. The Kolmogorov complexity of a given string is the length of the shortest program (in some fixed programming language) that generates the string. This is a notion of complexity which does make sense for a fixed string, with no randomness assumed. However, Kolmogorov complexity is uncomputable, and it cannot even be approximated. While Kolmogorov complexity has some applications in theoretical computer science, in your case the notion of entropy seems more appropriate.

$\endgroup$

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.