3강에서는 긴 메시지의 확률 대부분이 약 $2^{NH(X)}$개의 전형적인 문자열에 모이므로 기호당 $H(X)$비트까지 압축할 수 있음을 보았다. 이번에는 그 존재 정리를 실제 부호 설계로 가져온다. 어떤 길이들이 해독 가능한 부호를 이루며, 주어진 확률에 가장 짧은 심볼 부호를 어떻게 붙일까.
교재: 4장 The Source Coding Theorem, 5장 Symbol Codes.
한계의 두 방향
정보원 부호화 정리는 달성 가능성과 불가능성을 함께 말한다. 독립이고 같은 분포를 따르는 기호를 긴 블록으로 묶으면 평균 길이를 $H(X)+\epsilon$ 아래로 만들 수 있다. 반대로 $H(X)-\epsilon$보다 적은 비트로 거의 모든 메시지를 구별할 수는 없다.
불가능성은 단순한 세기에서 나온다. 비율 $R$로 길이 $N$인 메시지를 부호화하면 부호어는 $2^{NR}$개다. 전형적인 메시지는 약 $2^{NH(X)}$개다. $R 이 정리는 최적 압축률을 알려주지만 거대한 전형 집합 표를 만들라고 요구하지는 않는다. 실제 압축기는 계산 가능한 심볼 부호와 스트림 부호로 같은 경계에 접근한다. 가변 길이 부호는 기호의 경계를 잃지 않아야 한다. 어느 부호어도 다른 부호어의 앞부분이 아니면 접두 부호이고, 왼쪽부터 읽으며 즉시 해독할 수 있다. 접두 부호는 이진 나무로 그릴 수 있다. 왼쪽 가지에 0, 오른쪽 가지에 1을 붙이고 기호는 잎에만 둔다. 깊이 $l$인 잎은 전체 나무 공간의 $2^{-l}$을 차지한다. 따라서 부호 길이 $l_i$는 크라프트 부등식을 만족한다. 놀랍게도 역도 성립한다. 양의 정수 길이들이 이 부등식을 만족하면 그 길이를 가진 접두 부호를 실제로 만들 수 있다. 부호 설계가 문자열 조작 문제에서 길이 최적화 문제로 바뀐다. 기호 $i$의 확률이 $p_i$일 때 평균 부호 길이는 이다. 길이를 실수로 허용하고 크라프트 합이 1이라 두면 최적해는 가 된다. 확률이 두 배면 부호는 한 비트 짧다. 이 길이를 평균내면 엔트로피가 나온다. 정수 길이 제약 때문에 심볼 하나씩 부호화할 때는 보통 약간의 여분이 생긴다. 허프만 알고리즘은 주어진 기호 확률에서 평균 길이가 가장 짧은 이진 접두 부호를 만든다. 예를 들어 확률이 $(0.4,0.3,0.2,0.1)$이면 먼저 $0.1$과 $0.2$를 합쳐 $0.3$을 만든다. 두 $0.3$을 합쳐 $0.6$, 마지막으로 $0.4$와 $0.6$을 합친다. 흔한 기호는 나무 위쪽의 짧은 잎, 드문 기호는 아래쪽의 긴 잎이 된다. 허프만 부호의 평균 길이는 모든 심볼별 접두 부호 가운데 최적이며접두 부호와 이진 나무
평균 길이를 최소화하기
허프만 부호
묶으면 반올림 손실이 줄어든다
기호를 $N$개씩 묶어 하나의 거대 심볼로 보고 허프만 부호를 만들면 블록당 여분은 1비트보다 작다. 기호당 여분은 $1/N$보다 작다.
$$ H(X)\le \frac{L_N}{N}압축과 모형의 오차
실제 분포가 $p(x)$인데 압축기가 $q(x)$라고 믿으면 이상적인 길이는 $-\log_2q(x)$다. 실제 자료에서의 평균 길이는 교차 엔트로피가 된다.
$$ H(p,q)=-\sum_x p(x)\log_2q(x)=H(p)+D_{\mathrm{KL}}(p\|q) $$상대 엔트로피 $D_{\mathrm{KL}}$는 잘못된 모형 때문에 더 내는 비트 수다. 항상 0 이상이며 두 분포가 같을 때만 0이다. 압축률로 확률 모형을 평가할 수 있는 이유가 이 식에 담겨 있다.
다음 강에서는 심볼마다 정수 길이를 붙이는 방식을 넘어, 메시지 전체를 수직선의 작은 구간 하나로 나타내는 산술 부호를 배운다.