# Data compression - Entropy

Let's say I have an alphabet $$\Sigma = \{A, B, C, D, E\}$$

with probabilities $$P(A) = P(B) = P(C) = 0.25 \text{ and } P(D)=P(E) = 0.125.$$

I know that the entropy then is: $$H(\Sigma) = 3 \cdot 0.25 \cdot \log 4 + 2 \cdot 0.125 \cdot \log 8 = 2.25.$$

My question now is: What does this mean in relation to the lower limit of compression? How many bits will I at least need to compress a text that consists of the above alphabet?

• According to Shannon's source coding theorem, the entropy of a source is the optimal rate of compression. The theorem gives both an upper bound and a lower bound. Apr 22, 2020 at 12:04
• So I would need min. 2.25 bits per character?
– user119620
Apr 22, 2020 at 12:05
• en.wikipedia.org/wiki/Shannon%27s_source_coding_theorem Apr 22, 2020 at 12:07
• (Keep in mind that Shannon presumes independent distribution: not given in many applications.) Apr 22, 2020 at 16:52

## 1 Answer

The idea is to decode the more frequently used symbols with less number of bits than the less used ones

So ur example means we can compress more if we decode A, B, C in less bits than E, D rather than equiprobable decoding By Huffman Coding A, B, C is represented by 2 bits (that's log 4); while D, E take 3 bits (log 8) This way ur expected coding size is minimal (2.25* text length) because u expect ur file to have 0.25 of its characters as A,... 0.125 as E,...

I hope this makes it clear...