I watched a very well done video about information entropy, and I thought I got the concept in my mind but then I asked my self a question that denied every certainty I had. The video if you are interested: https://www.youtube.com/watch?v=2s3aJfRr9gE&t

My question is about data compression, image these 2 strings:

String1: $\mathbf{AAAABBBB}$ and String2: $\mathbf{ABABABAB}$

In both string I have the same number of $\mathbf{A}$ and $\mathbf{B}$ so the chance of getting an $\mathbf{A}$ is the same of the chance of getting a $\mathbf{B}$ in both strings.

With only 2 symbols I can make a Huffman encoding of 1 bit each. This means every symbol has "weight 1"

I will call $\mathbf{N_1} := number\,\, of\,\, bits\,\, for\,\, encoding\,\, A$

And $\mathbf{N_2} := number\,\, of\,\, bits\,\, for\,\, encoding\,\, B$

And $\mathbf{P(N_i)} := The\,\,probablity\,\,of\,\,this\,\,simboly $

In this case $\mathbf{N_1=N_2=1}$

So the entropy is calculated in this way: $$\mathbf{ H=\sum_{i=1}^2 i = N_i\,P(N_i)}$$

So for both strings the result is $\mathbf{N_1\,P(N_1) + N_2\,P(N_2) = 1\cdot0,5 + 1\cdot0,5 = 1}$

But string1 is clearly more easy to compress with RLE, I can say: I have 4 $\mathbf{A}$ and 4 $\mathbf{B}$ -> 4A4B.

So if I encode $\mathbf{A}$ with 1 and $\mathbf{B}$ with 0 the result will be 4140, also if the number of $\mathbf{A}$ and $\mathbf{B}$ is very large but symmetric I can say $\mathbf{n1n0}$ and $\mathbf{n}$ can be every big number I can image.

I can't make the same with string2.

So WHY if they have the same entropy it seems that string1 is more easy to compress than string2? Where is my fault? Thx :)


You are applying multiple layers of compression here.

Huffman is only optimal with fixed tokens and probabilities. If you were to just use Huffman encoding then you could only map string1 -> 00001111 and string2->010101 which would compress identically.

Converting string1 -> 4A4B is another compression step. Once you have done this then you can apply the Huffman encoding for more compression. Each step has different optimality properties.


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.