부호로서의 트리
접두사 없는 부호는 이진 트리로 매핑된다: 루트는 복호화의 시작을 나타내고, 왼쪽 분기는 비트 0을 나타내고, 오른쪽 분기는 비트 1을 나타내고, 잎은 완전한 부호어를 나타낸다.
기하학적 제약: 모든 잎은 루트에서 잎까지의 경로를 종료한다. 어떤 잎도 자식을 가질 수 없다 (만약 그렇다면, 그 부호어는 자식의 부호어의 접두사가 되어 접두사 없는 성질을 위반한다).
이것은 Kraft 부등식에 기하학적 해석을 제공한다:
깊이 d의 각 잎은 전체 트리 용량의 2^(−d) 부분을 '차지한다.' 깊이 D의 완전한 이진 트리의 전체 용량은 1이다. 접두사 없는 부호는 다양한 깊이의 잎을 사용한다; Kraft 합은 총 차지도를 측정한다.
Kraft 합 = 1: 완전한 부호 (모든 경로가 잎에서 끝난다 — 완벽한 패킹).
Kraft 합 < 1: 불완전한 부호 (일부 트리 용량이 사용되지 않음 — 더 많은 기호가 추가될 수 있다).
Kraft 합 > 1: 접두사 없는 부호로는 불가능하다 (일부 경로는 잎을 공유해야 한다).
더 깊은 잎 = 더 긴 부호 = 더 적은 용량
깊이 1의 잎은 트리 용량의 절반을 사용한다 (2^(−1) = 0.5).
깊이 3의 잎은 8분의 1을 사용한다 (2^(−3) = 0.125).
짧은 부호어를 트리의 높은 곳에 배치하면 모든 자식이 사용되지 않도록 막는다 — 하나의 짧은 부호를 많은 가능한 더 긴 부호로 교환한다.
접두사 없는 트리 구성하기
5개의 기호를 길이 l = {1, 2, 3, 3, 3}으로 고려하라. Kraft 합 = 2^(−1) + 2^(−2) + 3·2^(−3) = 0.5 + 0.25 + 0.375 = 1.125 > 1.
이것은 1을 초과한다: 이 길이들은 접두사 없는 부호와 호환되지 않는다. 최소한 하나의 길이는 증가해야 한다.
수정: l_1을 1에서 2로 변경한다. 새로운 길이 {2, 2, 3, 3, 3}: Kraft = 2·2^(−2) + 3·2^(−3) = 0.5 + 0.375 = 0.875 < 1. 유효하지만 불완전하다.
엔트로피가 부호 길이를 제한하는 이유
Kraft 부등식은 부호 구조를 제한한다 (길이는 트리에 맞아야 한다). Shannon의 엔트로피는 부호 효율을 제한한다 (평균 길이는 이론적 하한을 이길 수 없다).
최적 부호 길이. 확률 p_i를 가진 기호의 경우, 이상적인 부호 길이는 log₂(1/p_i)이다. 드문 기호는 긴 부호를 받을 자격이 있고; 빈번한 기호는 짧은 부호를 받을 자격이 있다. 이것은 Kraft 동등성을 반영한다: l_i = log₂(1/p_i)일 때 2^(−l_i) = p_i이다.
하지만 log₂(1/p_i)는 거의 정수가 아니다. ⌈log₂(1/p_i)⌉로 올림하면 H ≤ L < H + 1을 만족하는 Huffman 길이를 얻는다.
기하학적 해석. 각 기호를 깊이 l_i의 이진 트리 위의 점으로 그려라. Kraft 합은 총 잎 범위를 측정한다. 엔트로피는 확률로 가중된 가중 평균 깊이를 측정한다. Shannon의 정리: 확률-가중 평균 깊이 ≥ 확률-가중 정보 내용.
엔트로피 하한 검증
풀이 예제: 기호 {A, B, C, D}에 대한 p = [1/2, 1/4, 1/8, 1/8].
최적 길이: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
이들은 모두 정수다 — 완벽한 일치. Huffman 부호: A=0, B=10, C=110, D=111.
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75.
H = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75. L = H 정확히: 최적 부호.
완전한 풀이 예제
완전한 파이프라인: 주어진 확률에서, 엔트로피를 계산하고, 부호가 하한을 만족하는지 검증하라.
원본: p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125.
H = 1.75 비트 (위에서 계산됨).
순진한 블록 부호: 4개 기호 → 각각 2 비트 → L = 2.0. 엔트로피 위의 오버헤드: 2.0 − 1.75 = 0.25 비트/기호 = 12.5% 낭비.
가변 길이 부호는 고정 길이에 비해 12.5%를 절감한다. 큰 메시지의 경우, 이것은 상당하다.
영어의 엔트로피 속도. Shannon은 5비트 ASCII 부호를 사용하는데도 불구하고 쓰인 영어의 엔트로피를 약 1.0~1.3 비트/문자로 추정했다. 그 4:1 비율은 자연어의 막대한 중복성을 반영한다 — 일반적인 글자가 클러스터를 형성하고, 단어가 반복되고, 문법이 수열을 제한한다.
압축은 엔트로피를 이길 수 없다
압축 비율: H / (블록 부호 길이). 우리의 예제: 1.75/2.0 = 0.875 — 87.5% 효율.
더 압축할 수 있을까? 오직 문맥을 사용함으로써만: 기호의 쌍이나 삼중쌍을 함께 인코딩하면, 결합 엔트로피 H(X,Y)는 통계적 종속성 때문에 2·H(X)보다 작을 수 있다. 이것은 무잡음 부호화 정리의 n-그램으로의 확장이다.