산술 부호화(Arithmetic coding)

허프만 부호⁠(Huffman coding)⁠는 기호 하나마다 정수⁠(integer)⁠ 개의 비트를 줍니다. 확률이 0.95인 기호의 이상적인 길이는 $-\log_2 0.95 \approx 0.074$비트인데 부호어⁠(codeword)⁠는 1비트보다 짧을 수 없으니, 치우친 원천에서는 엔트로피⁠(entropy)⁠의 몇 배를 쓰게 됩니다. 기호를 여러 개씩 묶으면 손해가 줄지만(원천 부호화 정리⁠, source coding theorem⁠) 묶음의 가짓수가 지수적으로 늘어 부호표가 감당할 수 없이 커집니다. 산술 부호화는 부호표를 버리고, 메시지 전체를 [0, 1) 안의 수 하나로 적습니다. 씨앗은 1948년 섀넌의 논문에 이미 있었습니다. 누적 확률을 이진 소수⁠(binary expansion)⁠로 적어 부호어로 쓰는 방법입니다. 이것을 기호마다 구간을 좁혀 가는 방식으로 이어 쓰자는 생각은 1960년대 초 미국의 정보 이론가 피터 일라이어스에게서 나왔다고 하며, 1963년 노먼 에이브럼슨의 교과서에 소개되었습니다. 문제는 구간이 좁아질수록 필요한 자릿수가 끝없이 늘어난다는 것이었습니다. 1976년 IBM의 요르마 리사넨과 스탠퍼드의 리처드 파스코가 유한한 정밀도⁠(precision)⁠로 계산하는 방법을 각각 찾았고, 1987년 캐나다 캘거리 대학의 이언 위튼, 래드퍼드 닐, 존 클리어리가 누구나 가져다 쓸 수 있는 구현을 발표하면서 널리 퍼졌습니다.

a, b, c 세 글자가 확률 0.6, 0.3, 0.1로 나온다고 합시다. [0, 1)을 확률에 비례해 a는 [0, 0.6), b는 [0.6, 0.9), c는 [0.9, 1)로 나눕니다. 첫 글자가 b이면 [0.6, 0.9)로 들어가 이 구간을 다시 같은 비율로 나누고, 둘째 글자에 해당하는 칸으로 또 들어갑니다. 글자를 넣어 보세요: a b c 하나 지우기 비우기 모형: . 지금 메시지는 입니다.

구간의 폭은 글자마다 그 확률을 곱한 것이니, 끝에 남는 폭 W는 메시지 전체의 확률입니다. 폭이 W인 구간 안에는 길이 $2^{-k}$인 이진 구간 $[m/2^k, (m+1)/2^k)$이 $2^{-k} \le W/2$이기만 하면 반드시 통째로 들어가므로, 그 구간의 k자리 이진 소수 $m$을 보내면 됩니다. 이진 구간이 통째로 들어 있으니 뒤에 어떤 비트가 붙어도 여전히 W 안이라, 길이가 같은 다른 메시지의 부호어와 앞부분이 겹치지 않습니다. 길이가 다른 메시지끼리는 구간이 겹칠 수 있으므로(메시지 'b'의 구간은 'ba'의 구간을 품습니다), 받는 쪽이 메시지 길이를 따로 알거나 '끝' 기호를 하나 더 두어야 어디서 멈출지 압니다. 접두 부호⁠(prefix code)⁠의 부호어마다 [0, 1) 안의 겹치지 않는 구간이 하나씩 돌아간다는, 원천 부호화 정리의 크래프트 부등식⁠(Kraft inequality)⁠ 이야기와 같습니다. 조건 $2^{-k} \le W/2$를 만족하는 가장 작은 k는 $-\log_2 W + 2$보다 작으니, 메시지 하나에 $-\log_2 W + 2$비트 미만이 듭니다. 글자마다 따로 올림하지 않으니 글자 하나가 $-\log_2 p$라는 분수 비트를 그대로 치르는 셈입니다. 대신 끝에서 한꺼번에 2비트 가까이를 더 내므로, 몇 글자짜리 짧은 메시지에서는 허프만 부호보다 길 수도 있습니다.

부호기는 끝까지 기다릴 필요도 없습니다. 지금 구간의 두 끝을 이진 소수로 적으면 두 끝이 같은 앞자리는 앞으로 어떤 글자가 와도 바뀌지 않으니 곧바로 내보내고, 구간을 두 배로 늘려 잃은 정밀도를 되찾습니다. 구간이 1/2을 사이에 두고 좁아져 앞자리가 좀처럼 같아지지 않는 경우는 따로 셈해 두는 요령으로 처리합니다. 실제 구현은 이렇게 32비트 정수 두어 개로 끝없이 긴 메시지를 부호화합니다.

이득은 치우친 원천에서 두드러집니다. 두 글자 가운데 흔한 쪽의 확률이 이고, 메시지는 글자입니다.

산술 부호화는 네 글자씩 묶은 허프만 부호표 같은 것을 미리 만들어 두지 않습니다. 구간을 나누는 데 필요한 것은 다음 글자의 확률뿐이고, 그 확률이 글자마다 달라져도 됩니다. 위 그림의 모형을 '적응'으로 바꾸면 지금까지 나온 횟수에 1씩 더한 값에 비례하게 확률을 매깁니다. 두 결과 가운데 한쪽이 n번 중 s번 나왔을 때 다음 확률을 $(s+1)/(n+2)$로 어림하는 라플라스의 계승 규칙(rule of succession)을 글자가 여럿인 경우로 넓힌 것입니다. a를 거듭 넣으면 a의 칸이 점점 넓어지고 a 한 글자의 값이 싸집니다. 복호기⁠(decoder)⁠도 이미 풀어낸 글자로 같은 수를 세니 확률표를 따로 보낼 필요가 없습니다.

그래서 압축을 잘하는 일은 다음 글자를 잘 예측하는 일과 같아집니다. 모형이 글자 $x_i$에 준 확률이 $q(x_i \mid x_1 \cdots x_{i-1})$이면 메시지 길이는 거의 정확히 $\sum_i -\log_2 q(x_i \mid x_1 \cdots x_{i-1})$비트이고, 글자당 평균은 실제 분포에 대한 모형의 교차 엔트로피⁠(cross-entropy)⁠, 곧 실제로 나온 글자에 모형이 매긴 확률 q로 $-\log_2 q$를 구해 평균한 값입니다. 글자들이 서로 독립⁠(independence)⁠인 원천이라면, 모형이 틀린 만큼 글자당 쿨백–라이블러 발산⁠(Kullback–Leibler divergence)⁠만큼의 비트를 엔트로피보다 더 냅니다. 다음 글자를 더 잘 맞히는 모형이 곧 더 좋은 압축기입니다. 앞 몇 글자로 다음 글자를 맞히는 n-그램⁠(n-gram)⁠ 문맥 모형에 산술 부호화를 붙인 PPM(1984년 클리어리와 위튼. 부분 일치에 의한 예측⁠(prediction by partial matching)⁠이라는 뜻입니다)은 오랫동안 글 압축의 선두였고, 요즘은 신경망⁠(neural network)⁠ 언어 모델⁠(language model)⁠의 예측을 산술 부호화에 넣어 더 줄이기도 합니다. 거꾸로 언어 모델의 퍼플렉시티⁠(perplexity)⁠는 이 압축 길이를 지수로 되돌린 값입니다. 글자당 H비트가 든다면 퍼플렉시티는 $2^H$이고, 모형이 매번 똑같이 그럴듯한 후보 몇 개 사이에서 고르는 것만큼 헷갈리는지를 뜻합니다.

JPEG(1992)은 산술 부호화를 선택 사항으로 넣었지만 특허 문제 등으로 거의 쓰이지 않고 대부분 허프만 부호를 씁니다. 반면 H.264와 H.265 동영상 표준의 CABAC(문맥 적응 이진 산술 부호화)은 비트 하나하나의 확률을 문맥에 따라 적응시키는 이진 산술 부호기이고, 구간을 큰 정수 범위로 다루며 바이트 단위로 내보내는 범위 부호화(range coding)도 같은 계열입니다. xz가 쓰는 LZMA는 렘펠–지브 참조를 범위 부호기로 적습니다. 2009년 무렵부터 폴란드의 컴퓨터 과학자 야레크 두다가 발표한 비대칭 숫자 체계(ANS)는 산술 부호화와 거의 같은 만큼 압축하면서 더 빨리 돌아, Zstandard 같은 최신 압축기에 들어갔습니다.

이어지는 곳. 문맥에 기대는 원천에서 산술 부호화가 닿는 한계는 엔트로피율, 곧 앞의 글자들을 다 알 때 다음 글자에 남는 불확실성(조건부 엔트로피⁠, conditional entropy⁠)이며, 마르코프 연쇄⁠(Markov chain)⁠가 가장 단순한 예입니다. 되살릴 때 조금 달라져도 되는 손실 압축⁠(lossy compression)⁠의 한계는 율–왜곡 이론⁠(rate–distortion theory)⁠이 다루고, 거기서도 양자화⁠(quantization)⁠한 값을 마지막에 산술 부호화로 적습니다. 모형이 없는 문자열 하나의 정보량은 콜모고로프 복잡도⁠(Kolmogorov complexity)⁠이고, 적어 둔 비트를 지우는 데 드는 물리적 비용은 란다우어 원리⁠(Landauer's principle)⁠가 말해 줍니다. 적응 모형이 글자를 볼 때마다 확률을 고쳐 가는 과정은 새 증거를 볼 때마다 베이즈 정리⁠(Bayes' theorem)⁠로 믿음을 갱신하는 것과 같은 모양입니다. 실제로 '나온 횟수 + 1' 규칙은, 세 글자의 확률에 대해 아무 쪽도 편들지 않는(균등한) 사전 분포⁠(prior distribution)⁠를 두고 베이즈 정리로 갱신한 예측과 정확히 같습니다.