원천 부호화 정리(Source coding theorem)

기계 하나가 a, b, c, d 네 글자를 하나씩 뱉는다고 합시다. a가 나올 확률⁠(probability)⁠은 절반(0.5), b는 4분의 1(0.25), c는 0.15, d는 0.1이고, 앞에 무엇이 나왔든 다음 글자의 확률은 늘 같습니다. 이 글자열을 0과 1로 적어 보내되, 받는 쪽이 원래 글자열을 정확히 되살릴 수 있어야 합니다. 글자 하나에 평균 몇 비트가 필요할까요? 네 글자에 00, 01, 10, 11을 붙이면 글자당 2비트로 됩니다. 자주 나오는 a에 더 짧은 부호를 주면 줄일 수 있을 것 같은데, 얼마까지 줄일 수 있을까요?

1948년 클로드 섀넌이 이 물음에 정확히 답했습니다. 이 기계처럼 기호가 하나씩 나오되, 각 기호가 앞의 기호들과 상관없이(독립적으로) 늘 같은 확률분포에서 뽑히는 것을 원천이라 합니다. 답은 그 분포의 엔트로피 $H$입니다. 위의 예라면 $H = 0.5 \times 1 + 0.25 \times 2 + 0.15 \log_2 \tfrac{1}{0.15} + 0.1 \log_2 10 \approx 0.5 + 0.5 + 0.411 + 0.332 = 1.743$비트입니다. 정리는 두 부분으로 되어 있습니다. 첫째, 이어 붙인 비트열을 한 가지로만 끊어 읽을 수 있는 부호라면 어떤 것도 기호당 평균이 H보다 짧을 수 없습니다. 둘째, 기호를 n개씩 묶어 부호화하면 기호당 $H + 1/n$보다 짧게 할 수 있습니다. 이 정리가 엔트로피를 '정보의 양'이라 부르는 근거입니다.

먼저 말 두 개를 정합시다. 기호 하나에 붙이는 0과 1의 줄을 부호어라 합니다. 부호어⁠(codeword)⁠를 이어 붙여 보내므로 받는 쪽은 어디서 끊을지 알아야 합니다. 가장 쉬운 방법은 어떤 부호어도 다른 부호어의 앞부분이 되지 않게 하는 것입니다. 예를 들어 a = 0, b = 10, c = 110, d = 111이라면 0110100은 0 | 110 | 10 | 0, 다시 말해 a c b a로만 읽힙니다. 이런 부호를 접두 부호라 합니다.

하한⁠(lower bound)⁠은 접두 부호⁠(prefix code)⁠의 부호어가 차지하는 '자리'에서 나옵니다. 부호어 10을 쓰면 10으로 시작하는 비트열(100, 101, 1011, …)은 더 이상 다른 부호어가 될 수 없습니다. 이 몫을 수로 재 봅시다. 0과 1이 끝없이 이어지는 비트열 앞에 '0.'을 붙여 이진 소수⁠(binary expansion)⁠로 읽으면 0 이상 1 미만의 수가 됩니다. 이 범위를 [0, 1)로 씁니다. 10으로 시작하는 비트열은 0.10…₂ 꼴이므로 0.5 이상 0.75 미만의 수가 되어 구간 [0.5, 0.75)를 차지하고, 그 길이는 $1/4 = 2^{-2}$입니다. 일반적으로 길이 ℓ인 부호어는 [0, 1) 안에서 길이 $2^{-\ell}$인 구간 하나를 차지합니다. 접두 부호에서는 한 부호어가 다른 부호어의 앞부분이 아니므로 이 구간들이 겹치지 않고, 그래서 길이의 합이 1을 넘을 수 없습니다. 식으로 쓰면 $\sum_i 2^{-\ell_i} \le 1$(모든 부호어의 $2^{-\ell}$를 더한 값이 1 이하)이고, 이것을 크래프트 부등식⁠(Kraft inequality)⁠이라 합니다.

거꾸로, 합이 1 이하인 길이들이 주어지면 그런 길이의 접두 부호를 언제나 만들 수 있습니다. 짧은 부호어부터 차례로 [0, 1)의 왼쪽 끝에서 구간을 떼어 주면 되고, 아래 그림의 부호가 그렇게 만든 것입니다. 접두 부호가 아니면서도 한 가지로만 끊어 읽히는 부호도 있는데, 그런 부호도 같은 부등식을 따릅니다. 그래서 아래의 하한은 접두 부호만이 아니라 한 가지로만 끊어 읽히는 부호 전체에 대한 것입니다. 부등식은 1949년 미국의 레온 크래프트가 접두 부호에 대해 밝혔고, 1956년 브록웨이 맥밀런이 이렇게 넓혔습니다.

처음의 네 글자로 해 봅시다. 부호 길이를 정해 보고, 그림의 아래 줄이 테두리 밖으로 넘치는지 보세요. a , b , c , d 비트.

평균 길이는 비트이고 엔트로피는 비트입니다. 처음 값인 2, 2, 2, 2비트라면 평균은 2비트로, 엔트로피보다 약 0.257비트 깁니다. 1, 2, 3, 3비트로 두면 평균은 $0.5 \times 1 + 0.25 \times 2 + 0.15 \times 3 + 0.1 \times 3 = 1.75$비트가 됩니다. 허프만 부호⁠(Huffman coding)⁠와 같은 길이이고, 엔트로피(약 1.743비트)에 0.007비트쯤 차이로 다가갑니다. 길이를 어떻게 바꿔 보아도 아래 줄이 넘치지 않는 한 평균은 엔트로피 아래로 내려가지 않습니다.

왜 그럴까요? 평균 길이에서 엔트로피를 뺀 차는 $\sum p_i \log_2 \bigl(p_i / 2^{-\ell_i}\bigr)$로 쓸 수 있습니다. 그림으로 말하면 위 줄의 칸 너비 $p_i$와 아래 줄의 칸 너비 $2^{-\ell_i}$가 얼마나 어긋났는지를 잰 값입니다. 아래 줄의 너비 합이 1 이하인 한(크래프트 부등식) 이 값은 음수가 될 수 없고, 두 줄의 칸 너비가 꼭 같을 때, 다시 말해 $\ell_i = -\log_2 p_i$일 때만 0입니다. 이 사실을 미국 물리학자 깁스의 이름을 따 깁스 부등식⁠(Gibbs' inequality)⁠이라 부릅니다.

깁스 부등식의 열쇠는 로그 곡선의 모양입니다. 로그 곡선은 위로 볼록하게 휘어 있어서 곡선 위 두 점을 잇는 선분이 늘 곡선 아래에 놓입니다. 이 성질을 오목성이라 합니다. 그래서 로그 값들을 평균한 것은 평균의 로그를 넘지 못하고, 이를 위의 차에 쓰면 차가 0 이상임이 나옵니다. 같은 내용을 두 분포가 얼마나 다른지의 언어로 말한 것이, 쿨백–라이블러 발산⁠(Kullback–Leibler divergence)⁠이 0 이상이라는 사실입니다.

이상적인 길이 $-\log_2 p_i$는 보통 정수⁠(integer)⁠가 아니어서, 올림하면 기호당 최대 1비트 가까이(1비트보다는 적게) 손해를 봅니다. 그런데 기호 n개를 한 덩어리로 부호화하면 그 1비트를 n개가 나눠 내니 기호당 손해가 $1/n$ 밑으로 줄어듭니다. 앞면 확률이 인 동전의 엔트로피는 비트입니다. 던진 결과를 번씩 묶어 허프만 부호로 적으면 한 번 던질 때마다 가 듭니다. 묶음 크기 n을 1부터 늘려 가며 노란 점이 어디로 가는지 보세요.

n을 늘리면 노란 점은 대체로 보라 선(엔트로피)을 향해 내려가지만, 결코 그 아래로 가지는 않습니다. 정리의 첫째 부분이 말하는 하한입니다. 점선(H + 1/n)은 정리의 둘째 부분이 보장하는 상한이고, 노란 점은 늘 그 아래에 있습니다. 처음 값 p = 0.1에서 엔트로피는 약 0.469비트입니다. 묶지 않으면(n = 1) 한 번에 1비트가 들지만, 3개씩 묶으면 0.533비트, 5개씩 묶으면 0.480비트로 줄어듭니다.

다른 설명도 있습니다. 동전을 n번 던지면 큰 수의 법칙⁠(law of large numbers)⁠에 따라 앞면이 거의 언제나 np번 안팎 나옵니다. 앞면이 꼭 np번인 결과열의 개수는 n개의 자리 가운데 앞면이 나올 np개의 자리를 고르는 가짓수, 이항계수⁠(binomial coefficient)⁠ $\binom{n}{np}$입니다. n이 클 때 스털링 공식⁠(Stirling's formula)⁠으로 어림하면 이 수는 대략 $2^{nH}$입니다. 이 어림은 지수만 맞는 거친 어림입니다. n = 10, p = 0.1이면 실제 개수는 $\binom{10}{1} = 10$인데 $2^{10 \times 0.469} \approx 26$입니다. 그래도 n이 커질수록, 두 수에 $\log_2$를 취해 n으로 나눈 값(기호당 비트 수)은 같은 H로 다가갑니다. 앞면 수가 np 둘레의 좁은 범위에 드는 '전형적인' 결과열을 다 모아도 개수의 지수는 거의 nH입니다. 이것들에만 번호를 매기면 약 nH비트면 충분합니다. 드문 나머지는 따로 표시해 길게 적으면 되고, 그런 결과가 나올 확률이 n이 커질수록 0으로 가니 평균에는 거의 보태지 않습니다.

한편 모든 파일을 줄이는 압축기는 없습니다. n비트 파일은 $2^n$개인데 더 짧은 비트열은 길이 0인 빈 열부터 n − 1비트짜리까지 모두 합쳐 $1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1$개뿐입니다. 그러니 비둘기집 원리⁠(pigeonhole principle)⁠에 따라 어떤 파일은 줄지 않습니다. 압축은 확률이 치우친 곳에서만 이득을 봅니다.

역사. 자주 쓰는 글자에 짧은 부호를 주는 생각은 1830–40년대 모스와 베일의 전신 부호에 이미 있었습니다. 가장 흔한 E는 점 하나, 드문 Q는 점과 선 네 개입니다. 그러나 얼마나 짧게 할 수 있는지의 한계는 한 세기 동안 아무도 몰랐습니다. 1920년대 전화 회사 AT&T와 그 벨 연구소에서 해리 나이퀴스트와 랠프 하틀리가 전선 하나로 보낼 수 있는 신호의 양을 재려 했고, 벨 연구소의 섀넌은 그 물음을 이어받았습니다. 1948년 『벨 시스템 기술 저널』에 실린 「통신의 수학적 이론」에서 그는 원천이 내는 기호 하나당 정보를 엔트로피로 정의하고, 그것이 바로 압축의 한계임을 이 정리로 보였습니다. 크래프트 부등식(1949)과 맥밀런의 확장(1956)은 그 뒤에 나와, 위에서 본 것처럼 부호어 하나하나의 길이로 하한을 따지는 길을 열었습니다.

이어지는 곳.

• 기호가 앞 기호에 기대는 원천, 예컨대 마르코프 연쇄⁠(Markov chain)⁠에서는 엔트로피 대신 엔트로피율⁠(entropy rate)⁠이 한계가 됩니다. 엔트로피율은 기호 n개의 결합 엔트로피⁠(joint entropy)⁠를 n으로 나눈 값이 n이 커질 때 다가가는 값입니다. 통계적 성질이 시간에 따라 바뀌지 않는 원천이라면, 앞의 기호들을 다 알 때 다음 기호 하나에 남는 평균 불확실성과 같습니다.
• 섀넌은 1951년 사람들에게 다음 글자를 맞히게 하는 실험으로 영어의 엔트로피율을 글자당 약 0.6~1.3비트로 어림했습니다. 오늘날 n-그램⁠(n-gram)⁠이나 신경망⁠(neural network)⁠ 언어 모델⁠(language model)⁠의 성능도 같은 잣대로 잽니다. 모델이 실제 글에 준 확률로 잰 기호당 평균 비트 수(교차 엔트로피⁠, cross-entropy⁠) H가 작을수록 좋은 모델이고, 흔히 쓰는 퍼플렉시티⁠(perplexity)⁠는 $2^H$입니다.
• 렘펠–지브 압축⁠(Lempel–Ziv compression)⁠은 분포를 모르고도 이 한계에 다가가는 방법입니다.
• 콜모고로프 복잡도⁠(Kolmogorov complexity)⁠는 분포 없이 문자열 하나의 정보량을 묻습니다.
• 섀넌의 같은 논문에는 짝이 되는 정리도 있습니다. 잡음이 있는 통로로 얼마나 빨리 믿을 만하게 보낼 수 있는지를 말하는 통로 부호화 정리⁠(noisy-channel coding theorem)⁠이고, 이를 실제로 해내는 방법이 오류 정정 부호⁠(error-correcting code)⁠입니다.
• 산술 부호화⁠(arithmetic coding)⁠는 기호를 묶는 대신 글 전체를 수 하나로 적어 올림 손해를 거의 없앱니다.
• 조금 틀려도 되는 손실 압축⁠(lossy compression)⁠의 한계는 율–왜곡 이론⁠(rate–distortion theory)⁠이 정합니다.