Shannon Code

Summary

Shannon Code는 자주 나오는 메시지는 짧게, 드문 메시지는 길게 표현하는 압축 코드다.

핵심 insight

정보량은 $-{\log }_{2}p(x)$다. 자주 나오는 것은 정보량이 작으니 짧은 코드로 충분하고, 드문 것은 정보량이 크니 긴 코드가 필요하다.

코드 길이

Shannon code는 각 symbol $x$에 대해 코드 길이를 대략 다음처럼 정한다.

$$l(x)=\lceil -{\log }_{2}p(x)\rceil$$

여기서 $\lceil \cdot \rceil$는 올림이다. 코드 길이는 정수여야 하기 때문이다.

예시

문자 A, B, C의 확률이 다음과 같다고 하자.

symbol	probability	ideal length
A	0.5	1 bit
B	0.25	2 bits
C	0.25	2 bits

가능한 코드는:

• A: 0
• B: 10
• C: 11

자주 나오는 A는 1비트만 쓰고, 덜 나오는 B/C는 2비트를 쓴다.

Entropy와 연결

Entropy는 평균 코드 길이의 이론적 한계다. Shannon code는 이 한계 근처로 가는 단순한 방법이다.

관련 노트

• Entropy
• Source Coding Theorem
• Hamming Code