허프만 부호는 기호마다 정수 길이의 부호를 준다. 단순하고 최적이지만, 한 기호의 정보량이 1비트보다 훨씬 작으면 반올림 손실이 크다. 산술 부호는 기호별 경계를 버리고 메시지 전체에 하나의 이진 소수를 붙인다. 거대한 블록 부호표 없이도 엔트로피에 가까운 압축률을 얻는다.
교재: 5장 Symbol Codes, 6장 Stream Codes.
확률을 구간으로 바꾸기
단위 구간 $[0,1)$을 기호의 확률만큼 나눈다. $P(A)=0.6$, $P(B)=0.3$, $P(C)=0.1$이면
A: [0.0, 0.6)
B: [0.6, 0.9)
C: [0.9, 1.0)
첫 기호가 $B$라면 현재 구간을 $[0.6,0.9)$로 좁힌다. 다음 기호가 $A$라면 이 구간을 다시 6:3:1로 나눈 뒤 첫 60퍼센트 구간을 고른다. 메시지를 끝까지 읽으면 아주 작은 구간 하나가 남는다. 그 안에 들어가는 이진 소수 하나를 보내면 수신자는 같은 분할을 반복해 원문을 복원한다.
메시지 $x_1,\ldots,x_N$에 배정된 최종 구간의 폭은
$$ P(x_1,\ldots,x_N)=\prod_{n=1}^N P(x_n\mid x_{다. 메시지의 놀람값이 그대로 부호 길이가 된다.
기호를 차례로 눌러 보면 같은 분할이 현재 구간 안에서 반복된다. 각 행은 지금까지 읽은 메시지가 차지하는 구간을 다시 $6:3:1$로 확대한 모습이다.
순차 예측기가 곧 압축기다
산술 부호는 매 순간 다음 기호의 확률만 받으면 된다. 독립 분포일 필요가 없다. 앞 문맥 $x_{ 연쇄 규칙에 따라 전체 메시지의 로그 확률은 각 예측의 로그 확률 합이다.
실수 정밀도 없이 구현하기
메시지가 길어지면 구간은 너무 작아져 일반 부동소수점으로 다룰 수 없다. 실제 산술 부호기는 정수 구간을 쓰고, 위쪽과 아래쪽 경계의 앞 비트가 같아질 때마다 그 비트를 즉시 출력한다. 공통 앞부분을 내보낸 뒤 남은 구간을 다시 확대한다.
복호기도 같은 정수 연산을 같은 순서로 수행한다. 보내는 쪽과 받는 쪽의 확률 모형이 완전히 같아야 한다. 한 번이라도 확률 갱신이 어긋나면 이후 경계가 전부 달라져 복호가 무너진다.
알 수 없는 분포를 배우며 압축하기
자료의 분포를 미리 안다면 그 확률을 사용하면 된다. 하지만 보통은 자료를 보며 모형을 갱신해야 한다. 이때 아직 보지 못한 기호에 확률 0을 주면 안 된다. 확률 0인 사건의 부호 길이는 무한대이기 때문이다.
동전의 앞뒤 횟수를 세는 경우, 단순히 지금까지의 빈도를 쓰는 대신 작은 가상 횟수를 미리 더해 둔다. 베이즈 관점에서는 사전분포를 두고 예측분포를 사용하는 것이다. 관측이 쌓일수록 자료가 모형을 지배하지만 처음에도 모든 가능성이 살아 있다.
모형 자체의 비용
압축기는 자료만 보내는 것이 아니다. 수신자가 확률분포를 모른다면 모형이나 매개변수도 알려야 한다. 복잡한 모형은 자료를 더 잘 맞출 수 있지만 모형 설명에 더 많은 비트가 든다.
전체 설명 길이는 대략
$$ L(\text{모형})+L(\text{자료}\mid\text{모형}) $$이다. 너무 단순한 모형은 두 번째 항이 길고, 너무 복잡한 모형은 첫 번째 항이 길다. 가장 짧은 전체 설명을 고르는 생각이 최소 설명 길이이며, 뒤의 베이즈 모형 비교와 맞닿는다.
손실 압축은 다른 문제다
지금까지는 원문을 한 비트도 틀리지 않고 되살리는 무손실 압축을 다뤘다. 사진이나 소리는 작은 왜곡을 허용해 훨씬 더 줄일 수 있다. 그때는 허용하는 왜곡과 필요한 비율 사이의 관계인 비율 왜곡 이론이 필요하다. 엔트로피만으로는 답할 수 없다.
이 강의까지가 데이터 압축의 첫 묶음이다. 다음 강의부터는 반대 방향의 문제로 간다. 압축이 불필요한 가능성을 버리는 일이라면 오류 정정은 잡음 뒤에도 메시지를 구별하도록 여분의 구조를 넣는 일이다.