짧게 보내기

모스 부호⁠(Morse code)⁠는 왜 E를 점 하나로 보낼까? 섀넌의 엔트로피⁠(entropy)⁠가 정한 압축의 한계와, 허프만 부호⁠(Huffman coding)⁠에서 JPEG까지 그 한계에 다가간 방법들.

이 글의 처럼 점선이 그어진 숫자는 좌우로 끌 수 있고(키보드 ←/→도 됩니다), 색이 칠해진 같은 말은 눌러서 바꿀 수 있습니다. 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 글상자에는 보낼 글을 직접 쓸 수 있고, 그림 속 칸과 글자는 눌러서 바꿀 수 있습니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

1844년 5월 24일, 워싱턴의 미국 의사당에서 새뮤얼 모스가 전신기의 손잡이를 두드렸습니다. 60킬로미터쯤 떨어진 볼티모어에서 동업자 앨프리드 베일이 받아 적은 첫 공개 전보는 성경 민수기의 한 구절, "What hath God wrought"(하나님이 무엇을 이루셨는가)였습니다. 종이 띠에는 짧은 자국과 긴 자국, 곧 점과 선이 찍혀 나왔습니다.

그 띠를 자세히 보면 이상한 점이 있습니다. 글자마다 부호의 길이가 다릅니다. E는 점 하나, T는 선 하나인데, Q는 선·선·점·선으로 네 개나 됩니다. 전선은 한 번에 한 사람의 신호만 실어 나를 수 있었고, 머지않아 전신 회사들은 보낸 낱말 수대로 요금을 받았습니다. 전선 위의 시간은 곧 돈이었습니다. 그러니 이런 질문이 나올 만합니다. 같은 내용을 얼마나 짧게 보낼 수 있을까? 더 줄일 수 없는 한계가 있을까?

이 글은 그 질문이 100년 뒤 벨 연구소에서 정확한 답을 얻는 과정을 따라갑니다. 답은 '엔트로피'라는 수 하나였습니다. 그다음에는 그 한계에 다가간 방법들, 곧 MIT 대학원생의 기말 보고서에서 나온 허프만 부호, 하이파의 두 교수가 만든 사전식 압축, 눈과 귀가 알아채지 못하는 것을 버리는 JPEG와 MP3를 직접 돌려 봅니다. 마지막으로 거꾸로 여분을 더해 메시지를 지키는 방법과, 끝내 더 줄일 수 없는 것이 무엇인지를 봅니다. 필요한 수학(로그, 이진수, 확률⁠(probability)⁠)은 처음 나오는 자리에서 작은 예와 함께 다시 설명합니다.

1 · 점 하나의 E모스, 베일, 그리고 인쇄소의 활자

이 절의 물음은 이것입니다. 흔한 글자에 짧은 부호를 주면 실제로 얼마나 짧아질까? 먼저 그 부호가 어떻게 생겼는지 보고, 그다음 같은 글을 세 가지 부호로 보내 걸리는 시간을 직접 잽니다.

모스는 원래 초상화가였습니다. 뉴욕 대학에서 미술을 가르치던 그는 1830년대에 전자석으로 먼 곳에 신호를 보내는 장치를 연구했습니다. 흔히 전하는 이야기로는 1832년 유럽에서 돌아오는 배 위에서 전자석 이야기를 듣고 이 생각을 품었다고 합니다. 처음 구상한 방식은 지금의 모스 부호와 전혀 달랐습니다. 자주 쓰는 낱말마다 번호를 매긴 두꺼운 사전을 만들고, 그 번호를 전선으로 보내는 것이었습니다. 받는 쪽은 번호를 받아 사전을 뒤져야 했습니다.

이 방식이 글자 단위로 바뀐 자리에는 뉴저지주 모리스타운의 제철소 집안 아들 앨프리드 베일이 있었습니다. 베일은 돈과 기계 솜씨를 보태 동업자가 되었고, 1838년 초 두 사람은 베일 집안의 스피드웰 제철소에서 전신을 시연했습니다. 이 무렵 알파벳 글자마다 점과 선의 짧은 줄을 주는 부호가 자리 잡았습니다. 이 부호를 누가 만들었는지는 지금도 논쟁거리입니다. 모스는 평생 자기 발명이라고 했고, 베일 쪽의 기여를 강조하는 역사가들도 있습니다.

흔히 전해지는 이야기로는, 베일은 어느 글자가 자주 쓰이는지 알아내려고 모리스타운의 신문 인쇄소를 찾아가 활자 상자에 든 활자의 개수를 세었다고 합니다. 인쇄소는 자주 쓰는 글자의 활자를 많이, 드문 글자의 활자를 적게 갖춰 두니, 활자 상자는 영어 글자의 확률을 담은 표본⁠(sample)⁠인 셈입니다. E가 가장 많았고, Z나 Q는 몇 개 되지 않았습니다. 그래서 가장 흔한 E에 점 하나, 그다음인 T에 선 하나를 주고, 드문 글자에는 긴 부호를 주었습니다.

효과를 재 보려면 시간을 세는 단위가 필요합니다. 국제 모스 부호의 규칙은 이렇습니다. 점의 길이를 1로 하면 선은 3, 한 글자 안의 점과 선 사이 쉼은 1, 글자 사이의 쉼은 3, 낱말 사이의 쉼은 7입니다. E는 점 하나이니 1단위입니다. Q(선·선·점·선)는 표시 넷과 그 사이의 쉼 셋을 차례로 더해 선 3, 쉼 1, 선 3, 쉼 1, 점 1, 쉼 1, 선 3으로 $3+1+3+1+1+1+3 = 13$단위가 걸립니다. Q 하나를 보내는 동안 E를 여러 번 보낼 수 있는 셈입니다.

이제 같은 글을 세 가지 방식으로 보내 비교합니다. 아래 글상자의 글을 보낸 띠를 같은 축척으로 그렸습니다. 첫째는 모스 부호, 둘째는 똑같은 26개의 부호를 알파벳 순서대로 나눠 준 것(A가 가장 짧은 점 하나, B가 그다음…), 셋째는 모스의 순위를 거꾸로 뒤집은 것입니다. 세 방식 모두 부호 26개의 모음은 똑같고, 어느 글자에 어느 부호를 주는지만 다릅니다. 그러니 띠 길이의 차이는 오로지 '흔한 글자에 짧은 부호를 주었느냐'에서 나옵니다. 띠의 오른쪽 끝이 어디서 끝나는지 비교해 보세요. 보낼 글:

지금 글은 모스 부호로 단위, 알파벳 순서로 단위, 거꾸로 배정하면 단위가 걸립니다. 모스 부호로 되돌리기

정리하면, 쓰는 부호의 모음이 똑같아도 어느 글자에 짧은 부호를 주느냐에 따라 띠의 길이가 크게 달라집니다. 글에 자주 나오는 글자에 짧은 부호를 줄수록 띠가 짧아집니다. 남은 물음은 '얼마나 짧게까지 되는가'이고, 3절에서 답합니다.

모스의 부호는 대서양을 건너며 다듬어졌습니다. 1848년 함부르크의 전신 기사이자 작가 프리드리히 게르케는 미국식 부호에 섞여 있던 글자 안의 긴 쉼 같은 까다로운 요소를 없애고 글자의 절반 가까이를 고쳐, 점과 선 두 가지만으로 된 부호를 만들었습니다. 1865년 20개 나라가 파리에 모여 국제 전신 연합(오늘날 국제전기통신연합의 전신)을 세웠을 때, 게르케의 부호를 조금 고친 것이 국제 모스 부호가 되었습니다. 위 그림의 부호가 바로 그것입니다.

알파벳을 쓰지 않는 나라들은 다른 길을 찾아야 했습니다. 1871년 덴마크의 대북부전신회사가 놓은 해저 전신선이 상하이에 닿자, 이듬해 상하이 세관의 프랑스인 비기에는 자주 쓰는 한자 6,800여 자에 네 자리 숫자를 하나씩 붙인 부호집⁠(codebook)⁠을 펴냈습니다. 한자 하나를 보내려면 숫자 넷, 곧 점과 선 스무 개를 보내야 했습니다. 모스가 처음 구상한 '번호 사전' 방식이 한자에서 되살아난 셈입니다. 조선에서는 1885년 9월 한성전보총국이 문을 열고 한성과 제물포 사이에 전신이 개통되었습니다. 오늘날의 한글 모스 부호는 글자가 아니라 자모마다 부호를 줍니다.

2 · 낱말값전신 부호집과 한 글자의 무게

이 절의 물음은 둘입니다. 글자 하나하나가 아니라 문장 전체를 짧게 보내는 방법은 없을까? 그리고 그렇게 줄인 메시지에는 어떤 위험이 따를까?

전신은 19세기 후반의 인터넷이었습니다. 신문은 전보로 소식을 받았고, 상인은 전보로 면화와 밀과 양모를 사고팔았습니다. 요금은 낱말 수로 매겨졌고, 대양을 건너는 해저 전신은 특히 비쌌습니다. 사람들은 관사와 조사를 빼고 낱말을 붙여 쓰는 '전보체⁠(telegraphese)⁠'를 쓰게 되었습니다.

더 체계적인 방법도 나왔습니다. 1870년대부터 1950년대까지 상인과 선박 회사들은 두꺼운 상업 전신 부호집을 썼습니다. 부호집은 "선적이 지연되어 도착일을 알 수 없음" 같은 자주 쓰는 문장 하나하나에 가짜 낱말 하나를 붙여 둔 책입니다. 보내는 쪽과 받는 쪽에 같은 책이 있으면, 문장 대신 낱말 하나만 보내고 한 낱말 값만 내면 됩니다. 국제 전신 회의는 무엇을 '한 낱말'로 칠지를 두고 규칙을 여러 번 고쳤습니다. 1879년에는 몇몇 유럽 언어와 라틴어의 실제 낱말만 허용했고, 20세기 초에는 대체로 발음할 수 있는 열 글자 이하의 말이면 한 낱말로 쳐 주었습니다. 부호집 편찬자들은 그 규칙 안에서 가능한 한 많은 문장을 담으려고 경쟁했습니다.

부호집은 '공유된 사전을 가리키는 짧은 이름'으로 압축하는 방법입니다. 긴 문장이 몇 글자짜리 낱말 하나로 줄어드는 대신, 양쪽이 같은 사전을 미리 갖고 있어야 합니다. 이 생각은 5절의 렘펠–지브 압축⁠(Lempel–Ziv compression)⁠으로 다시 돌아옵니다. 거기서는 사전을 미리 나눠 갖지 않아도 되는 방법이 나옵니다.

그런데 압축에는 대가가 있었습니다. 1887년 6월 필라델피아의 양모상 프랭크 프림로즈는 캔자스에 있는 대리인에게 자기들끼리 만든 부호로 전보를 보냈습니다. 부호집에서 문장이나 낱말 하나를 대신하는 짧은 말을 부호어라 합니다. 그 가운데 '샀다'는 뜻의 부호어⁠(codeword)⁠ BAY가 전송 중에 '사라'는 뜻의 BUY로 바뀌었습니다. 대리인은 양모를 잔뜩 사들였고, 프림로즈는 법원 기록에 따르면 2만 달러가 넘는 손해를 보았습니다. 1894년 미국 대법원은, 프림로즈가 전보를 되돌려 받아 대조하는 추가 요금을 내지 않았으므로 전신 회사의 책임은 전보 요금 1달러 15센트까지라고 판결했습니다.

보통의 영어 문장이었다면 글자 하나가 틀려도 앞뒤 문맥으로 알아챘을 것입니다. "I HAVE BOUGHT THE WOOL"이 "I HAVE BOUGHT THE WOAL"로 와도 누구나 WOOL로 읽습니다. 보통의 글에는 이렇게 내용을 전하는 데 꼭 필요하지는 않은 부분, 곧 여분이 많아서, 일부가 틀려도 나머지가 바로잡아 줍니다. 압축은 바로 그 여분을 없애는 일입니다. 그래서 압축된 글에서는 글자 하나하나가 무거워집니다. BAY와 BUY는 둘 다 사전에 있는 말이라, 받는 쪽은 틀린 줄을 알 방법이 없었습니다.

그래서 20세기 초의 여러 부호집은 어떤 두 부호어도 적어도 두 글자가 다르도록 만들어, 한 글자가 틀리면 사전에 없는 말이 되게 했다고 합니다. 정리하면, 줄이는 일과 지키는 일은 서로 반대 방향입니다. 줄이면 여분이 사라지고, 지키려면 여분을 되살려야 합니다. 이 긴장은 7절에서 다시 만납니다.

공유된 책의 번호를 보내는 방법은 전기 전신보다 오래되었습니다. 1794년 혁명기의 프랑스에서 클로드 샤프 형제의 광학 전신⁠(optical telegraph)⁠이 파리와 릴 사이의 언덕 위 탑들을 이었습니다. 탑 꼭대기의 나무 팔을 여러 각도로 꺾어 신호를 만들면, 다음 탑의 사람이 망원경으로 보고 똑같이 따라 했습니다. 전쟁 중이던 혁명 정부에게는 전선의 소식을 몇 시간 안에 받는 것이 무엇보다 급했고, 그해 8월 북쪽 국경의 르케누아를 되찾았다는 소식이 이 선으로 파리에 닿았다고 전합니다. 1795년부터는 92쪽, 쪽마다 92줄짜리 부호책을 썼습니다. 신호 두 개로 쪽과 줄을 보내면 낱말이나 자주 쓰는 구절 $92 \times 92 = 8{,}464$가지 가운데 하나가 정해집니다. 모스가 처음 구상한 '번호 사전'과 같은 생각이고, 신호 하나하나가 비싸다는 사정도 같았습니다. 샤프의 망은 나폴레옹 시대에 프랑스 전역으로 뻗었다가 1850년대에 전기 전신으로 바뀌었습니다.

전신의 시대. 모리스타운과 워싱턴에서 시작한 부호가 함부르크와 파리에서 국제 표준이 되고, 해저선을 따라 상하이와 한성까지 가는 것을 보세요. 역사 줄(분홍)의 부호집과 프림로즈 사건⁠(event)⁠은 요금과 법이 부호를 어떻게 바꾸었는지 보여 줍니다.

3 · 놀람의 평균섀넌의 엔트로피

모스와 베일은 흔한 글자에 짧은 부호를 주면 좋다는 것을 알았지만, 얼마나 짧게 할 수 있는지는 몰랐습니다. 이 절의 물음이 그것입니다. 글자들이 얼마나 자주 나오는지를 알 때, 글자 하나에 평균 몇 자리까지 줄일 수 있을까? 답은 글자들의 확률만으로 계산되는 수 하나, 엔트로피입니다.

그 답은 1948년 뉴저지주 머리힐의 벨 연구소에서 나왔습니다. 전화 회사의 연구소답게 문제는 실용적이었습니다. 전화선과 무선 통로에 얼마나 많은 정보를 실을 수 있는가? 그해 7월과 10월 『벨 시스템 기술 저널』에 두 번에 나뉘어 실린 클로드 섀넌의 논문 「통신의 수학적 이론」은 먼저 '정보의 양'을 정의했습니다. 단위는 이진법⁠(binary)⁠의 한 자리, 곧 비트입니다. 0 아니면 1인 자리 하나, 달리 말하면 예·아니오 답 하나가 1비트입니다. 이 이름은 동료였던 통계학자 존 튜키가 binary digit(이진 숫자)를 줄여 지었다고 섀넌이 논문에 밝혀 두었습니다.

생각의 출발은 스무고개입니다. 똑같이 흔한 기호 4개 가운데 하나를 맞히려면 예·아니오 질문 두 번이면 됩니다("앞의 둘 중 하나인가?", "그중 앞의 것인가?"). 질문 하나가 후보를 절반으로 줄이기 때문입니다. 기호가 8개면 8 → 4 → 2 → 1로 세 번, 16개면 네 번입니다. 일반적으로 $2^k$개(2를 k번 곱한 수)면 $k$번입니다.

'2를 몇 번 곱해야 그 수가 되는가'를 셈하는 것이 밑이 2인 로그입니다. $\log_2 N$('밑이 2인 로그 N'이라 읽습니다)은 2를 몇 번 곱해야 N이 되는지를 뜻합니다. $2 \times 2 \times 2 = 8$이니 $\log_2 8 = 3$이고, $\log_2 4 = 2$, $\log_2 2 = 1$입니다. 그러니 똑같이 흔한 N개 가운데 하나를 가려내는 데 드는 질문 수는 $\log_2 N$입니다. N이 2의 거듭제곱이 아니어도 로그는 정의되어서, 예를 들어 $\log_2 10 \approx 3.32$입니다($2^3 = 8$과 $2^4 = 16$ 사이이니 3과 4 사이입니다).

이제 이것을 확률로 바꿔 적습니다. 똑같이 흔한 8개 가운데 하나의 확률은 $p = \tfrac18$이고, 질문 수 3은 $\log_2 8 = \log_2 \tfrac1p$입니다. $\log_2 \tfrac1p$는 흔히 $-\log_2 p$로 적는데, 둘은 같은 값입니다(분수를 뒤집으면 로그의 부호가 바뀝니다). 일반적으로 $2^k$개 가운데 하나의 확률은 $p = 2^{-k}$이니 $k = -\log_2 p$입니다.

섀넌은 이것을 모든 확률로 넓혔습니다. 확률 $p$인 일이 일어났다는 소식에는 $-\log_2 p$비트의 '놀람'이 들어 있다고 정합니다. 흔한 일은 덜 놀랍고, 드문 일은 많이 놀랍습니다. 앞면이 나올 확률이 0.9인 동전이라면, 앞면이라는 소식의 놀람은 $\log_2 \tfrac{1}{0.9} \approx 0.15$비트뿐이고, 뒷면이라는 소식의 놀람은 $\log_2 \tfrac{1}{0.1} = \log_2 10 \approx 3.32$비트입니다. 0.15비트처럼 1보다 작은 값은 질문 한 번으로는 뜻이 없지만, 많은 소식을 모아 평균을 낼 때 뜻이 생깁니다. 그 뜻은 아래의 동전 셈에서 봅니다.

기호 하나가 평균적으로 담은 정보는 기호마다의 놀람을 그 기호가 나오는 비율만큼 쳐서 평균을 낸 것입니다. 이것이 정보 엔트로피⁠(information entropy)⁠이고, 식으로는 이렇게 적습니다.

식을 말로 읽으면 이렇습니다. $p_i$는 i번째 기호의 확률이고, $-\log_2 p_i$는 그 기호의 놀람입니다. 기호마다 '확률 × 놀람'을 구해, 모든 기호에 대해 더합니다. 큰 시그마 Σ는 '아래 적힌 i를 모든 기호에 걸쳐 바꿔 가며 더하라'는 기호입니다. 앞의 동전이라면 $H = 0.9 \times 0.15 + 0.1 \times 3.32 \approx 0.47$비트입니다. 드문 뒷면은 놀람이 크지만 좀처럼 나오지 않으니, 평균은 1비트의 절반에도 못 미칩니다.

네 기호로 하나 더 확인해 봅시다. 네 기호의 확률이 $\tfrac12, \tfrac14, \tfrac18, \tfrac18$이면 놀람은 차례로 1, 2, 3, 3비트입니다($\tfrac1p$가 2, 4, 8, 8이니까요). 확률만큼 쳐서 더하면 $H = \tfrac12 \cdot 1 + \tfrac14 \cdot 2 + \tfrac18 \cdot 3 + \tfrac18 \cdot 3 = 1.75$비트입니다. 기호가 넷이니 두 자리씩 고정된 부호(00, 01, 10, 11)를 쓰면 2비트가 드는데, 부호를 0, 10, 110, 111로 주면 평균 길이가 $\tfrac12 \cdot 1 + \tfrac14 \cdot 2 + \tfrac18 \cdot 3 + \tfrac18 \cdot 3$, 곧 정확히 1.75비트가 됩니다. 부호의 길이가 놀람과 똑같기 때문입니다. 네 기호가 모두 $\tfrac14$로 똑같이 흔하면 놀람이 모두 2비트라 H = 2이고, 두 자리 고정 부호보다 나을 것이 없습니다. 정리하면, 엔트로피는 확률이 치우칠수록 작아지고, 그 치우침이 짧은 부호의 여지입니다. 엔트로피의 정의와 섀넌이 이것으로 영어 글자의 정보를 잰 실험은 「말을 세는 기계」 5절에 자세히 있습니다. 여기서는 이 수가 압축의 한계라는 쪽을 봅니다.

이제 실제 글로 재 봅니다. 아래 글상자는 1절의 것과 이어져 있습니다. 글에 나오는 기호(공백 ␣ 포함)를 많은 순서로 늘어놓고, 기호마다 나온 비율과 놀람 $-\log_2 p$, 그리고 4절에서 만들 허프만 부호의 길이를 적었습니다. 여기서는 이 글 안에서 센 비율을 그 기호의 확률 p로 삼습니다. 오른쪽은 기호 하나에 드는 평균 비트를 세 가지로 잰 것입니다. 볼 것은 두 가지입니다. 흔한 기호일수록 놀람과 부호 길이가 짧은지, 그리고 오른쪽 세 막대의 높이가 어떤 순서로 서는지입니다. 보낼 글:

이 글에는 기호 개, 서로 다른 기호 가지가 있습니다. 모두 같은 길이로 적으면 기호마다 비트가 들고, 흔한 기호에 짧은 부호를 주는 허프만 부호는 평균 비트, 엔트로피는 비트입니다.

글을 바꿔도 막대의 순서는 바뀌지 않습니다. 고정 길이 부호가 가장 길거나 허프만 부호와 같고, 엔트로피가 가장 짧거나 허프만 부호와 같습니다. 고정 길이 부호도 기호 하나에 부호어 하나를 주는 부호의 하나이고, 허프만 부호는 그런 부호 가운데 가장 짧기 때문입니다(4절). 엔트로피가 그 아래에 있는 까닭이 바로 아래에서 볼 섀넌의 정리입니다.

섀넌은 이 수가 넘을 수 없는 벽이라는 것을 증명했습니다. 정리를 정확히 적으려면 낱말 몇 개가 필요합니다. 원천은 기호를 하나씩 내놓는 출처(글을 쓰는 사람, 전보를 치는 기계)를 말하고, 무손실 압축은 줄였다가 되살렸을 때 원래 글이 한 글자도 틀리지 않고 그대로 돌아오는 압축을 말합니다. 원천이 내놓는 기호들이 서로 독립⁠(independence)⁠이고 같은 확률분포⁠(probability distribution)⁠를 따른다고 합시다. 서로 독립이라는 것은 앞에 무엇이 나왔든 다음 기호의 확률이 바뀌지 않는다는 뜻이고, 같은 확률분포를 따른다는 것은 기호마다 확률을 적은 표(확률분포)가 매번 똑같다는 뜻입니다. 같은 동전을 거듭 던지는 것이 그런 원천입니다.

그 분포의 엔트로피가 $H$일 때 원천 부호화 정리⁠(source coding theorem)⁠는 두 가지를 말합니다. 첫째, 이어 붙여도 한 가지로만 끊어 읽히는(4절에서 봅니다) 어떤 무손실 부호도, 원천이 내놓을 모든 글을 평균해서 기호당 $H$비트보다 짧을 수 없습니다. 둘째, 기호를 하나씩이 아니라 길게 묶어서 부호화하면 평균을 $H$에 얼마든지 가깝게 할 수 있습니다.

흔히 이 정리를 '어떤 글이든 기호당 H비트로 줄일 수 있다'는 뜻으로 읽지만, 정리가 말하는 것은 평균입니다. 드문 글자가 몰린 글은 H비트보다 길어지고, 흔한 글자만 있는 글은 H비트보다 짧아집니다. 원천이 내놓을 모든 글을 확률만큼 쳐서 평균하면 H비트 밑으로는 내려갈 수 없다는 것입니다.

둘째 주장, 곧 묶으면 H에 다가간다는 것의 속뜻은 셈에 있습니다. 앞면이 나올 확률이 0.9인 앞의 동전을 100번 던져 그 결과(앞과 뒤가 100개 늘어선 줄)를 보낸다고 합시다. 한 번에 1비트씩 그대로 적으면 100비트입니다. 엔트로피는 한 번에 약 0.47비트이니, 정리는 100번에 약 47비트 가까이까지 줄일 수 있다고 말합니다. 어떻게 가능할까요?

가능한 결과는 $2^{100}$가지이지만 모두 똑같이 일어날 법하지는 않습니다. 큰 수의 법칙(많이 던질수록 실제로 나온 비율이 확률에 가까워진다는 법칙)에 따라 거의 언제나 앞면이 90번 안팎 나옵니다. 계산해 보면 뒷면이 5번에서 15번 사이일 확률이 약 94%입니다. 그런 결과는 몇 가지일까요? 뒷면이 정확히 10번인 결과의 수는 100자리 가운데 뒷면이 나올 10자리를 고르는 방법의 수, 곧 이항계수⁠(binomial coefficient)⁠ $\binom{100}{10} \approx 1.7 \times 10^{13} \approx 2^{44}$입니다. 뒷면이 5번에서 15번 사이인 결과를 모두 합해도 약 $2^{58}$가지로, $2^{59}$보다 적습니다.

그러니 이렇게 보내면 됩니다. 양쪽이 이 '흔한 결과'들에 0번부터 번호를 매긴 같은 표를 갖고 있다고 합시다. 결과가 흔한 쪽에 들면 표시 비트 0 다음에 번호 59비트를 보내고, 드문 나머지 약 6%에서는 표시 비트 1 다음에 결과 100비트를 그대로 보냅니다. 받는 쪽은 표시 비트를 보고 어느 쪽인지 알고 되살리니 무손실입니다. 평균은 $0.94 \times 60 + 0.06 \times 101 \approx 62$비트쯤으로, 100비트보다 훨씬 짧습니다.

아직 47비트는 아닙니다. 던지는 횟수 n을 늘리면, '흔한 결과'의 범위를 비율로는 더 좁게 잡아도 그 안에 들 확률이 1에 가까워집니다. 스털링 공식(큰 수의 계승⁠(factorial)⁠ $n! = 1 \times 2 \times \cdots \times n$을 어림하는 식)으로 계산하면, 그런 결과의 개수가 대략 $2^{nH}$라는 것이 일반적으로 나옵니다. 번호에 드는 비트가 약 nH이니, 던지기 한 번당 비트 수가 H에 얼마든지 가까워집니다. 정리하면, 엔트로피는 '실제로 일어날 법한 결과의 가짓수'를 비트로 센 것입니다. 경우의 수⁠(number of cases)⁠를 세는 기술은 「세지 않고 세기」에 있습니다.

한 가지 주의할 점이 있습니다. 위 그림의 엔트로피는 글자를 하나씩 따로 본 값입니다. 실제 영어에서는 Q 다음에 거의 언제나 U가 오듯 앞 글자가 다음 글자를 알려 줍니다. 섀넌의 1951년 실험에 따르면, 문맥까지 따진 영어의 엔트로피는 한 글자당 1비트 안팎(섀넌의 어림으로 0.6~1.3비트)까지 내려갑니다. 좋은 압축 프로그램이 글을 몇 분의 일로 줄이는 것은 이 문맥을 쓰기 때문입니다.

0과 1 두 기호만으로 수를 적는 이진법에는 동서양을 오간 내력이 있습니다. 라이프니츠는 1703년 파리 과학 아카데미의 논문집에 이진법 셈을 설명하는 글을 실었는데, 제목에 '복희의 옛 중국 그림에 던지는 빛'이라는 말이 붙어 있었습니다. 베이징에 있던 예수회 선교사 조아킴 부베가 편지로, 11세기 송나라의 학자 소옹이 배열한 『주역』 64괘의 그림을 보내 준 것입니다. 괘는 끊긴 막대와 이어진 막대 여섯 개를 쌓은 기호이고, 끊긴 것을 0, 이어진 것을 1로 읽으면 소옹의 배열은 0부터 63까지의 이진수 차례가 됩니다. 막대 여섯 개, 곧 6비트로 64가지를 가려내는 셈입니다($\log_2 64 = 6$). 라이프니츠는 1과 0만으로 모든 수를 짓는 것을 신이 무에서 만물을 지은 창조의 상징으로 보기도 했습니다. 섀넌의 비트는 이런 신학과 상관없이, 예·아니오 답 하나라는 셈의 단위입니다.

정보를 수로 재자는 생각은 섀넌이 처음이 아니었습니다. 같은 회사의 랠프 하틀리는 1928년 「정보의 전송」에서, 기호가 s가지인 n자리 메시지의 정보를 가능한 메시지 수 $s^n$의 로그, 곧 $n \log s$로 재자고 했습니다. 로그를 쓰면 메시지가 두 배로 길어질 때 정보도 두 배가 됩니다(가능한 메시지 수는 제곱이 되지만, 로그는 곱셈을 덧셈으로 바꾸니까요). 그런데 이 자는 모든 기호가 똑같이 흔하다고 보는 셈이라, E와 Q를 같은 무게로 셉니다. 베일이 활자 상자에서 본 치우침을 담으려면 확률이 식 안에 들어가야 했고, 그것이 섀넌이 보탠 것입니다. 모든 기호의 확률이 $\tfrac1s$로 같으면 섀넌의 엔트로피는 기호당 $\log_2 s$가 되어, 로그의 밑을 2로 잡은 하틀리의 자와 일치합니다. 하틀리와 나이퀴스트가 전신의 속도⁠(velocity)⁠를 재던 이야기는 「잡음 너머로」 2절에 있습니다.

'엔트로피'라는 이름에는 유명한 일화가 붙어 있습니다. 물리학에서 엔트로피는 기체 분자들이 얼마나 뒤섞여 있는지를 재는 양이고, 통계역학⁠(statistical mechanics)⁠은 그것을 '분자들이 놓일 수 있는 방법의 수'로 설명합니다. 폰 노이만이 이 식은 통계역학의 엔트로피와 같은 꼴이니 그 이름을 쓰라고 권하며, 엔트로피가 정말 무엇인지 아무도 모르니 논쟁에서 늘 유리할 것이라고 덧붙였다는 것입니다. 다만 이 이야기는 1971년 공학자 마이런 트라이버스가 『사이언티픽 아메리칸』에 쓴 글에 섀넌에게서 들은 말로 실렸을 뿐, 다른 기록으로는 확인되지 않습니다.

4 · 부호의 나무접두 부호⁠(prefix code)⁠, 크래프트, 그리고 기말 보고서

3절에서는 0, 10, 110, 111이라는 부호를 그냥 받아들였습니다. 이 절의 물음은 둘입니다. 0과 1만 이어 붙인 줄에서 글자의 경계를 어떻게 알아볼까? 그리고 그런 부호에서 가장 짧은 것은 어떻게 찾을까?

모스 부호에는 사실 기호가 세 가지 있습니다. 점, 선, 그리고 쉼입니다. 쉼이 없으면 '점 점'이 I인지 E 두 개인지 알 수 없습니다. 0과 1만 쓰는 컴퓨터에는 쉼이 따로 없으니, 부호 자체가 끊을 곳을 알려 주어야 합니다. 무엇이 잘못될 수 있는지부터 봅시다. A = 0, B = 1, C = 01로 정하면 01이라는 줄은 AB로도 C로도 읽힙니다. C의 부호 01이 A의 부호 0으로 시작하는 것이 문제입니다.

가장 깔끔한 해결은 어떤 부호도 다른 부호의 앞부분이 되지 않게 하는 것입니다. 이런 부호를 접두 부호(앞머리가 겹치지 않는 부호)라고 부릅니다. 0, 10, 110, 111은 접두 부호입니다. 0110111을 읽으면 0에서 한 기호가 끝나고, 다음은 110에서, 그다음은 111에서 끝납니다. 앞에서부터 읽다가 부호표에 있는 줄이 나오는 순간 끊으면 됩니다. 그보다 더 읽어야 하는 경우는 없습니다. 그 줄로 시작하는 다른 부호가 없기 때문입니다.

접두 부호는 이진 트리⁠(tree)⁠로 그릴 수 있습니다. 한 점(뿌리)에서 출발해 갈림길마다 0이면 왼쪽, 1이면 오른쪽으로 내려가는 그림입니다. 더 갈라지지 않는 끝을 잎⁠(leaf)⁠이라 하고, 잎에 닿으면 기호 하나를 읽은 것입니다. 기호를 잎에만 두면 어떤 부호도 다른 부호의 앞부분이 될 수 없습니다. 앞부분이 된다는 것은 한 기호의 자리를 지나 더 내려간 곳에 다른 기호가 있다는 뜻인데, 잎 아래로는 길이 없기 때문입니다.

그렇다면 부호의 길이는 아무렇게나 고를 수 있을까요? 아닙니다. 세 자리 비트열 여덟 개(000, 001, …, 111)로 따져 봅시다. 부호 0을 쓰면 0으로 시작하는 000, 001, 010, 011 넷, 곧 여덟 개의 절반을 차지합니다. 이 넷은 다른 부호의 시작이 될 수 없으니 다른 부호가 쓸 수 없습니다. 부호 10은 100, 101 둘, 곧 4분의 1을 차지합니다. 110과 111은 하나씩, 8분의 1씩입니다. 일반적으로 길이 $l$인 부호는 전체의 $2^{-l}$($\tfrac12$을 l번 곱한 것)을 차지합니다. 접두 부호에서는 두 부호가 같은 비트열을 차지하는 일이 없으니, 차지한 몫을 모두 더해도 1을 넘을 수 없습니다.

식은 '부호마다 $2^{-(\text{길이})}$를 구해 모두 더하면 1 이하'라고 읽습니다. $l_i$는 i번째 기호의 부호 길이입니다. 길이 1, 2, 3, 3은 $\tfrac12 + \tfrac14 + \tfrac18 + \tfrac18 = 1$이니 가능하고(0, 10, 110, 111), 길이 1, 1, 2는 $1.25$이니 불가능합니다. 실제로 길이 1인 부호 둘이 0과 1을 다 가져가면, 길이 2인 부호는 어느 쪽으로 시작해도 앞의 것과 겹칩니다.

거꾸로 합이 1 이하이기만 하면 그 길이들로 접두 부호를 반드시 만들 수 있습니다. 짧은 길이부터 차례로, 아직 아무도 차지하지 않은 자리를 골라 주면 됩니다. 1949년 MIT의 대학원생 레온 크래프트가 석사 논문에서 보인 이 사실을 크래프트 부등식⁠(Kraft inequality)⁠이라고 부릅니다. 1956년 벨 연구소의 수학자 브록웨이 맥밀런은 접두 부호가 아니어도, 이어 붙인 비트열을 끊어 읽는 방법이 늘 한 가지뿐인 부호라면 같은 부등식을 따른다는 것을 보였습니다. 그러니 접두 부호만 살펴도 잃는 것이 없습니다.

그러니 부호를 설계하는 일은 '1이라는 몫을 기호들에게 나눠 주는 일'입니다. 확률 $p$인 기호에 몫 $p$를, 곧 $2^{-l} = p$가 되는 길이 $l = -\log_2 p$를 주면, 부호 길이가 3절의 놀람과 같아져서 평균이 정확히 엔트로피가 됩니다. 확률을 모두 더하면 1이니 부등식도 지켜집니다. 그런데 길이는 정수여야 합니다. 확률 0.3인 기호의 놀람은 약 1.74비트이니 2비트로 올려 줍니다. 길이를 올리면 몫은 작아지니 부등식은 여전히 지켜지고, 기호마다 1비트 미만을 더 쓰니 평균은 엔트로피보다 1비트 미만만 길어집니다.

그럼 가장 좋은 정수⁠(integer)⁠ 길이는 어떻게 찾을까요? 섀넌은 1948년 논문에서, MIT의 공학자 로버트 파노는 1949년 보고서에서 비슷한 목적의 방법을 내놓았고, 둘 다 '섀넌–파노 부호⁠(Shannon–Fano code)⁠'라고 불립니다. 여기서 볼 것은 파노의 방법입니다. 기호들을 확률 순서로 늘어놓고, 무게가 가장 비슷한 두 무리로 자릅니다. 왼쪽 무리에 0, 오른쪽 무리에 1을 붙이고, 각 무리를 다시 같은 방법으로 자릅니다(재귀⁠(recursion)⁠). 뿌리에서 잎으로 내려가며 나무를 짓는 이 방법은 대개 훌륭했지만, 언제나 가장 짧지는 않았습니다.

1951년 파노는 MIT 대학원의 정보 이론 수업에서 학생들에게 선택권을 주었습니다. 기말 시험을 보거나, 아니면 가장 효율적인 이진 부호를 찾는 방법을 다룬 보고서를 내라는 것이었습니다. 보고서를 고른 20대 중반의 데이비드 허프만은 오래 매달리고도 답을 찾지 못했습니다. 1991년 한 잡지와의 인터뷰에서 그는, 시험공부를 시작하려던 참에 답을 찾았다고 회고했습니다. 스승 파노는 물론 섀넌도 이 문제와 씨름했다는 것을 알았다면 시도조차 하지 않았을지 모른다는 말도 덧붙였습니다.

허프만의 생각은 방향을 뒤집는 것이었습니다. 뿌리에서 자르며 내려가지 말고, 잎에서 묶으며 올라가자. 가장 드문 두 기호는 어차피 가장 긴 부호를 받을 테니, 둘을 나무의 가장 깊은 곳에 형제로 두고 한 무리로 묶습니다. 묶은 무리를 무게가 두 기호의 합인 새 기호로 보고, 다시 가장 가벼운 두 무리를 묶습니다. 하나가 남을 때까지 되풀이합니다.

ABRACADABRA로 첫 걸음을 손으로 해 봅시다. 글자 수는 A 5, B 2, R 2, C 1, D 1입니다. 가장 가벼운 둘은 C와 D이니, 둘을 묶어 무게 2인 무리를 만듭니다. 이제 무게는 5, 2, 2, 2이고, 다음에는 무게 2인 셋 가운데 둘을 묶습니다. 나머지는 아래 그림에서 한 걸음씩 따라가 보세요. 그림 아래의 단추로 한 단계씩 앞뒤로 움직이거나 재생하며, 매번 노란 고리가 정말 가장 가벼운 두 무리에 걸리는지 확인하면 됩니다. 원천:

잎 아래의 부호 줄을 보세요. 두 무리를 묶을 때마다 그 아래 모든 기호의 부호 앞에 한 자리가 붙습니다. 그래서 여러 번 묶인 드문 기호일수록 부호가 길어집니다. 부호의 길이는 그 기호가 몇 번 묶였는지와 같습니다.

허프만의 방법은 매번 눈앞에서 가장 가벼운 두 개만 고릅니다. 이렇게 멀리 내다보지 않고 당장 가장 좋아 보이는 것을 고르는 방법을 욕심쟁이 알고리즘⁠(greedy algorithm)⁠이라 하고, 대개는 최선을 보장하지 못합니다. 그런데 허프만 부호는 기호마다 부호어 하나를 주는 부호 가운데서 언제나 최적, 곧 평균 길이가 가장 짧습니다. 까닭은 두 가지로 요약됩니다. 가장 드문 두 기호를 형제로 두는 최적 부호가 늘 있고, 둘을 묶어 하나로 만든 작은 문제의 최적 부호를 다시 풀면 원래 문제의 최적 부호가 됩니다. 가장 가벼운 둘을 빨리 꺼내려면 우선순위 큐⁠(priority queue)⁠를 쓰면 됩니다.

완성된 나무에서 평균 길이는 허프만 부호가 비트, 섀넌–파노 부호가 비트, 엔트로피는 비트입니다. 입니다. 원천을 '무게 15, 7, 6, 6, 5'로 바꿔 보세요. 섀넌–파노 부호는 첫 칼질에서 15와 7을 한쪽에 두는 바람에 허프만 부호보다 2비트를 더 씁니다.

맨 아래 띠는 크래프트 부등식을 그린 것입니다. 부호마다 차지한 몫 $2^{-l}$을 나란히 이어 붙였습니다. 허프만의 나무는 모든 갈림길이 두 갈래로 다 차 있어(빈 가지가 없어) 몫의 합이 정확히 1이고, 띠가 빈틈없이 찹니다.

허프만 부호에도 한계가 있습니다. 부호의 길이는 정수여야 하니, 확률 0.99인 기호도 적어도 1비트를 씁니다. 그 기호의 놀람은 $-\log_2 0.99 \approx 0.0145$비트뿐인데 말입니다. 이 낭비를 거의 없애는 길은 두 가지입니다. 여러 기호를 묶어 하나로 부호화하거나, 메시지 전체를 0과 1 사이의 수 하나로 적는 산술 부호화⁠(arithmetic coding)⁠를 쓰는 것입니다. 산술 부호화는 1976년 무렵부터 IBM의 핀란드 출신 연구자 요르마 리사넨 등이 발전시켰고, 그 군더더기는 메시지 전체에 2비트 미만입니다. 또 허프만 부호는 확률표를 미리 알아야 하고, 그 표도 함께 보내야 합니다.

정리하면, 끊어 읽을 수 있는 부호는 나무의 잎으로 그릴 수 있고, 부호 길이를 정하는 일은 크래프트 부등식의 몫 1을 기호들에게 나눠 주는 일입니다. 허프만의 묶기는 기호 하나에 부호어 하나를 주는 한 그 나눔의 최선이고, 평균은 엔트로피보다 1비트 미만만 깁니다.

5 · 사전을 만들며 읽기렘펠과 지브

4절의 허프만 부호는 기호들의 확률표를 미리 알아야 했습니다. 이 절의 물음은 이것입니다. 확률을 모른다면, 처음 보는 글을 어떻게 줄일까?

1977년 이스라엘 하이파의 테크니온 공과대학에서 정보 이론가 야코브 지브와 컴퓨터 과학자 아브라함 렘펠은 전혀 다른 길을 냈습니다. 확률을 세지 말고, 이미 보낸 글 자체를 사전으로 쓰자는 것입니다. 앞에서 나온 조각이 다시 나오면 조각을 또 보내는 대신 "몇 칸 뒤로 가서 몇 글자를 베껴라"라는 짧은 참조를 보냅니다. 받는 쪽에도 이미 받은 글이 있으니 똑같이 베낄 수 있습니다.

'BLAH BLAH'로 해 봅시다. 처음 다섯 글자 B, L, A, H, 공백은 앞에 나온 것이 없으니 글자 그대로 보냅니다. 여섯째 글자부터의 'BLAH'는 5칸 앞에서 시작하는 네 글자와 같으니 ⟨5, 4⟩ 하나로 보냅니다. 앞의 수가 몇 칸 뒤로 갈지(거리), 뒤의 수가 몇 글자를 베낄지(길이)입니다. 2절의 부호집과 달리 사전을 미리 나눠 가질 필요가 없습니다. 사전은 읽으면서 저절로 만들어집니다.

아래 그림은 이 과정을 한 조각씩 보여 줍니다. 비트는 이렇게 셉니다. 보통 글자 하나는 8비트로 적습니다. 압축한 줄에서는 조각마다 '글자인지 참조인지'를 알리는 1비트를 앞에 붙이니, 글자 하나는 1 + 8 = 9비트입니다. 참조는 표시 1비트, 거리 8비트(255칸 뒤까지), 길이 4비트(3글자부터 18글자까지 16가지)로 1 + 8 + 4 = 13비트입니다. 이 셈으로는 두 글자(18비트)만 같아도 참조가 짧지만, 이 그림은 gzip 같은 실제 프로그램처럼 세 글자 이상 같을 때만 참조를 씁니다. 단추로 한 조각씩 넘기며 분홍 원본과 노란 조각이 정말 같은지 확인해 보세요. 글:

. 'BLAH BLAH …'의 여섯 번째 조각을 보세요. 5칸 뒤로 가서 14글자를 베끼라는데, 뒤로 5칸밖에 없습니다. 괜찮습니다. 한 글자씩 앞에서부터 베끼면 방금 베낀 글자가 곧 다음 원본이 되어, 'BLAH ' 다섯 글자가 세 번 가까이 되풀이됩니다. 참조 하나가 반복을 통째로 담는 것입니다.

이 방식이 렘펠–지브 압축(LZ77)입니다. 이듬해 두 사람은 지나온 조각들을 번호 붙은 사전에 쌓아 가는 변형(LZ78)도 발표했습니다. 중요한 것은 이런 방법이 확률을 전혀 모르면서도, 글이 충분히 길면 원천의 엔트로피(정확히는 엔트로피율⁠(entropy rate)⁠)에 다가간다는 증명입니다. 엔트로피율은 3절 끝에서 말한 '문맥까지 따진' 엔트로피, 곧 앞의 글을 모두 안다고 할 때 다음 기호 하나가 평균적으로 담은 정보입니다. 되풀이되는 조각을 베끼는 방식이라, 글자를 하나씩 따로 볼 때는 잡지 못하는 문맥도 저절로 씁니다.

이 증명에는 조건이 있습니다. 원천의 통계적 성질이 시간에 따라 바뀌지 않고(정상성), 긴 글 하나에서 센 빈도가 원천 전체의 확률을 드러내야 합니다(에르고딕성). 그런 원천이라면 어느 것이든, 확률을 미리 알지 못해도 그 엔트로피에 다가가는 이런 방법을 보편 압축⁠(universal compression)⁠이라고 부릅니다. 실제 프로그램은 긴 글에서 같은 조각을 빨리 찾으려고 세 글자 조각마다 나온 자리를 해시 테이블⁠(hash table)⁠에 적어 둡니다. 정리하면, 사전식 압축은 확률표 대신 지나온 글을 사전으로 삼고, 글이 길어질수록 기호당 비트 수가 확률을 아는 쪽의 한계인 엔트로피율에 다가갑니다.

이 생각은 거의 모든 컴퓨터에 들어갔습니다. 1990년대 초 프로그래머 필 카츠의 PKZIP과, 장루 게이와 마크 애들러가 만든 gzip은 LZ77로 되풀이를 참조로 바꾼 다음, 남은 글자와 참조를 다시 허프만 부호로 줄이는 '디플레이트⁠(Deflate)⁠' 방식을 썼습니다. zip 파일, 웹 페이지를 주고받을 때의 압축, PNG 그림이 모두 이 방식입니다. 3절과 4절의 엔트로피 부호와 이 절의 사전이 한 몸이 된 것입니다.

한편 1984년 스페리 연구소의 테리 웰치는 LZ78을 하드웨어로 빠르게 돌릴 수 있게 다듬었습니다(LZW). 운영 체제 유닉스의 압축 프로그램 compress가 이 방식을 썼고, 1987년 오하이오주 콜럼버스의 온라인 서비스 회사 컴퓨서브는 그림을 주고받는 형식 GIF에 LZW를 넣었습니다. 그런데 LZW에는 스페리의 뒤를 이은 회사 유니시스의 특허가 걸려 있었습니다. 1994년 12월 말, 컴퓨서브가 유니시스와의 합의에 따라 GIF를 만드는 소프트웨어에 사용료를 받겠다고 발표하자 웹 개발자들은 들끓었습니다. 몇 주 만에 인터넷의 자원봉사자들이 특허에 걸리지 않는 디플레이트를 쓴 새 형식을 설계했습니다. 그것이 PNG이고, 1996년 10월 웹 표준을 정하는 국제 기구 W3C의 권고안이 되었습니다. LZW의 미국 특허는 2003년에 끝났습니다.

이 사건은 수학과 법 사이의 오래된 질문을 드러냈습니다. 수학 정리나 공식 자체는 누구의 것도 아니라는 데 대부분 동의합니다. 그런데 그 공식으로 기계를 움직이는 절차, 곧 알고리즘⁠(algorithm)⁠은 발명일까요, 발견일까요? 소프트웨어와 알고리즘을 어디까지 특허로 보호할지는 지금도 나라마다, 시대마다 판단이 다릅니다. 같은 무렵 공개 열쇠 암호의 특허를 둘러싸고도 비슷한 논쟁이 있었습니다. 공개 열쇠 암호가 어떻게 작동하는지는 「나머지로 지키는 비밀」에 있습니다.

디지털의 시대. 머리힐의 벨 연구소와 MIT에서 태어난 이론(수학 줄)이 하이파, 캔자스, 에를랑겐을 거쳐 GIF, JPEG, MP3, PNG 같은 형식(과학 줄, 역사 줄)이 되는 것을 보세요. 지도의 주황 선은 생각이 표준으로 옮겨 간 길입니다.

6 · 알아채지 못할 만큼코사인⁠(cosine)⁠, JPEG, 그리고 MP3

이 절의 물음은 이것입니다. 원래와 똑같이 되살리지 않아도 된다면, 무엇을 버려야 적게 버리고도 많이 줄일 수 있을까?

사진은 무손실로는 잘 줄어들지 않습니다. 하늘의 파란색도 화소마다 밝기가 조금씩 흔들려서, 같은 조각이 정확히 되풀이되는 일이 드물기 때문입니다. 그런데 사진을 보는 사람은 그 작은 흔들림을 정확히 되살려 달라고 하지 않습니다. 눈이 알아채지 못하는 만큼은 버려도 됩니다. 이것이 손실 압축입니다. 얼마나 버리면 얼마나 줄일 수 있는지를 따지는 이론도 섀넌이 세웠습니다. 되살린 것과 원래 것의 차이(왜곡)를 어디까지 참을지 정하면, 기호당 몇 비트(율)까지 줄일 수 있는지가 정해진다는 1959년 무렵의 율–왜곡 이론⁠(rate–distortion theory)⁠입니다. 문제는 무엇을 버릴지입니다.

1972년 캔자스 주립 대학의 나시르 아흐메드는 영상을 코사인 무늬들의 합으로 쪼개는 방법을 구상해 미국 국립과학재단에 연구비를 신청했습니다. 그의 회고에 따르면 한 심사위원은 이 생각이 "너무 단순하다"고 했고 신청은 떨어졌습니다. 그는 대학원생 T. 나타라잔, 텍사스 대학 알링턴의 K. R. 라오와 함께 연구를 이어 가 1974년 1월 논문을 냈습니다. 이것이 이산 코사인 변환(DCT)입니다.

생각의 뿌리는 「원에서 파동으로」의 푸리에입니다. 웬만한 주기 함수⁠(periodic function)⁠를 진동수⁠(frequency)⁠가 다른 사인파⁠(sinusoid)⁠들의 합으로 쓸 수 있다는 푸리에 급수⁠(Fourier series)⁠처럼, 8개의 밝기는 0번부터 7번까지 차례로 빨라지는 코사인 8개에 계수를 곱해 더한 것으로 정확히 쓸 수 있습니다(k번 코사인은 블록 안에서 반 바퀴를 k번 돕니다).

한 줄에 놓인 밝기 8개로 뜻을 풀어 봅시다. 0번 무늬는 여덟 칸이 모두 같은 평평한 무늬입니다. 1번 무늬는 반 바퀴를 한 번 돌아서, 한쪽 끝이 밝고 반대쪽 끝이 어두운 완만한 비탈입니다. 번호가 클수록 밝고 어두운 줄무늬가 촘촘해집니다. 계수는 '그 무늬를 얼마만큼 섞었는가'입니다. 여덟 칸이 모두 같은 밝기라면 0번 계수 하나만 있고 나머지 계수는 모두 0입니다. 한쪽에서 다른 쪽으로 고르게 어두워지는 줄이라면 0번과 1번 계수가 크고 나머지는 작습니다. 사진의 대부분은 이렇게 천천히 변하니, 계수 몇 개가 거의 모든 것을 담습니다.

코사인만 쓰는 까닭은 블록의 가장자리에 있습니다. 보통의 푸리에 분해는 블록이 주기적으로 되풀이된다고 봅니다. 그러면 오른쪽 끝과 왼쪽 끝이 맞닿으며 가짜 절벽이 생기고, 그 절벽을 흉내 내느라 높은 진동수가 잔뜩 필요합니다. 코사인은 블록을 거울에 비춘 것처럼 이어 붙이는 셈이라 절벽이 생기지 않습니다. 그래서 매끄러운 영상의 에너지(밝기 제곱의 합, 곧 신호의 세기)가 낮은 진동수 몇 개에 몰립니다.

사진은 가로세로 두 방향이니, 8×8 블록 하나를 가로 무늬 8개와 세로 무늬 8개를 곱한 64개의 기본 무늬로 나눕니다. 계수 하나는 블록과 그 기본 무늬의 내적⁠(dot product)⁠입니다. 내적은 두 블록의 같은 칸끼리 밝기를 곱해 64개를 모두 더한 값으로, 블록이 그 무늬를 얼마나 닮았는지를 잽니다.

이 변환에는 좋은 성질이 하나 있습니다. 버린 계수가 곧 오차라는 것입니다. 칸이 두 개뿐인 블록으로 확인해 봅시다. 밝기가 (100, 90)인 두 칸을, 평평한 무늬 $(\tfrac{1}{\sqrt2}, \tfrac{1}{\sqrt2})$와 한쪽만 밝은 무늬 $(\tfrac{1}{\sqrt2}, -\tfrac{1}{\sqrt2})$로 나눕니다(이것이 칸이 둘일 때의 코사인 변환입니다). 계수는 내적이니 첫째가 $\tfrac{100 + 90}{\sqrt2} \approx 134.4$, 둘째가 $\tfrac{100 - 90}{\sqrt2} \approx 7.07$입니다.

밝기의 제곱합은 $100^2 + 90^2 = 18{,}100$이고, 계수의 제곱합도 $\tfrac{190^2}{2} + \tfrac{10^2}{2} = 18{,}050 + 50 = 18{,}100$으로 같습니다. 이제 작은 둘째 계수를 버리고 첫째 계수만으로 되살리면 $134.4 \times \tfrac{1}{\sqrt2} = 95$이니 (95, 95)가 됩니다. 오차는 (5, −5)이고, 오차의 제곱합 $5^2 + 5^2 = 50$은 버린 계수의 제곱 $7.07^2 \approx 50$과 같습니다.

왜 그런지는 그림으로 보입니다. 밝기 두 개를 평면 위의 점 (100, 90)으로 보면, 두 무늬는 대각선 방향의 새 좌표축 두 개이고, 계수는 새 축으로 잰 좌표입니다. 두 무늬는 서로 직교⁠(orthogonality)⁠하고(내적이 $\tfrac12 - \tfrac12 = 0$이고) 길이가 1이니, 이 변환은 서로 직각인 두 대각선을 새 좌표축으로 삼아 같은 점을 다시 재는 것일 뿐입니다. 축을 바꿔 재도 원점에서 점까지의 거리는 그대로이니 제곱합이 같고, 계수 하나를 버리는 것은 점을 한 축 위로 떨어뜨리는 것이라 오차가 정확히 버린 좌표만큼입니다. 8×8 블록은 밝기 64개, 곧 좌표 64개로 적히는 점이고, 64개의 기본 무늬도 서로 직교하고 길이가 1이 되게 맞춰 두었습니다. 그래서 이 변환은 64차원 공간에서 서로 직각인 새 좌표축으로 갈아 재는 선형변환⁠(linear transformation)⁠이고, 정보도 에너지(제곱합)도 그대로이며, 버린 계수들의 제곱합이 곧 오차의 제곱합이 됩니다.

아래 그림에서 블록을 고르고, 남길 계수의 개수를 끌어 바꿔 보세요. 계수는 지그재그 순서, 곧 느린 무늬부터 남깁니다. 볼 것은 두 가지입니다. 몇 개를 남겨야 오른쪽의 되살린 블록이 원래 블록처럼 보이는지, 그리고 그 수가 블록마다 얼마나 다른지입니다. 블록: , 남길 계수: 개.

계수를 개만 남기면 블록의 에너지(밝기 제곱의 합)의 %가 남고, 평균 오차는 밝기 0–255 기준으로 입니다. 에너지의 99%를 담는 데 개가 필요합니다. 지그재그 순서는 느린 무늬에서 빠른 무늬로 가는 길입니다.

두 수를 읽는 법을 적어 둡니다. 에너지에는 평균 밝기(0번 계수)의 몫도 들어 있고, 대개 그 몫이 가장 큽니다. '둥근 얼룩'에서는 0번 계수 하나가 에너지의 80%쯤을 차지합니다. 그래서 에너지 비율보다 오차 쪽이 눈에 보이는 차이를 더 잘 알려 줍니다. 평균 오차는 칸마다 원래 밝기와 되살린 밝기의 차이를 제곱해 64칸에 걸쳐 평균 낸 뒤 제곱근을 씌운 값으로, 밝기를 0(검정)에서 255(흰색)까지로 잰 것입니다.

1992년 승인된 JPEG 표준은 이 블록을 중심에 놓았습니다. 이 이름은 1986년 국제 표준 기구들이 함께 꾸린 합동⁠(congruence)⁠ 사진 전문가 그룹의 머리글자입니다. 사진을 밝기와 색으로 나누고, 눈이 덜 예민한 색은 해상도를 줄입니다. 8×8 블록마다 DCT를 하고, 계수를 정해진 수로 나누어 반올림합니다. 이것이 양자화입니다. 예를 들어 나누는 수가 16이면 계수 37은 37 ÷ 16 ≈ 2.3이 반올림되어 2로 적히고, 되살릴 때 2 × 16 = 32가 됩니다(오차 5). 계수 5는 5 ÷ 16 ≈ 0.3이 되어 0으로 사라집니다. 사진 편집기의 '품질' 눈금이 바꾸는 것이 바로 이 나누는 수입니다. 눈은 빠른 무늬의 작은 오차를 잘 못 보니 빠른 무늬일수록 크게 나누고, 그러면 대부분이 0이 됩니다. 계수를 지그재그로 읽으면 0이 길게 이어지고, 그 줄을 4절의 허프만 부호로 적습니다. 품질을 너무 낮추면 8×8 블록의 경계가 격자처럼 드러납니다.

소리에서도 같은 일이 일어났습니다. 귀에는 이상한 성질이 있습니다. 큰 소리가 나는 동안(그리고 그 직후 잠깐) 그와 진동수가 가까운 작은 소리는 들리지 않습니다. 이것을 차폐⁠(auditory masking)⁠라고 합니다. 귀가 무엇을 듣고 무엇을 놓치는지를 수로 재는 연구는 전화 회사에서 크게 자랐습니다. 전화선이 실어야 할 진동수의 폭을 정하려면 사람이 말을 알아듣는 데 어떤 진동수가 필요한지 알아야 했기 때문입니다. 1930–40년대 벨 연구소의 하비 플레처는 통로가 말소리를 얼마나 알아듣게 전하는지 재는 지수를 만들었고, 한 소리는 그와 진동수가 가까운 띠 안의 소리만 가린다는 '임계 대역'의 생각을 세웠습니다. 독일 에를랑겐의 프라운호퍼 집적회로 연구소에서 카를하인츠 브란덴부르크의 연구진은 심리음향 모형⁠(psychoacoustic model)⁠을 썼습니다. 사람이 어떤 소리를 듣고 어떤 소리를 놓치는지를 수로 적은 모형입니다. 연구진은 짧은 소리 조각을 코사인 계수로 바꾼 다음, 들리지 않을 성분은 거칠게, 들리는 성분만 정밀하게 적는 방식을 만들었습니다. 이것이 1993년 MPEG-1 오디오 레이어 3으로 표준이 되었고, 1995년 7월 연구진이 파일 확장자를 .mp3로 정했습니다. 브란덴부르크는 미국 가수 수잰 베가의 노래 「Tom's Diner」의 무반주 목소리를 수없이 들으며 방식을 다듬었다고 전합니다. 목소리 하나만 있는 노래에서는 잡음이 숨을 곳이 없었기 때문입니다.

수를 따져 봅시다. 음악 CD는 1초에 44,100번, 한 번에 16비트, 두 채널로 소리를 적으니 1초에 $44{,}100 \times 16 \times 2 = 1{,}411{,}200$비트입니다. 흔히 쓰던 128킬로비트 MP3는 그 11분의 1쯤입니다. 이 차이 덕분에 전화선 모뎀으로도 노래를 주고받을 수 있게 되었습니다. 1999년 대학생 숀 패닝이 만든 파일 공유 서비스 냅스터는 몇 달 만에 수많은 사용자를 모았고, 음반 산업과의 소송 끝에 2001년 문을 닫았습니다. 압축 형식 하나가 음악을 사고파는 방식을 바꾸어 놓은 것입니다.

정리하면, 손실 압축⁠(lossy compression)⁠은 신호를 코사인 무늬들이라는 새 좌표축으로 다시 적은 뒤, 눈과 귀가 알아채지 못하는 계수를 거칠게 적거나 버립니다. 직각인 축으로 갈아 재는 일은 에너지를 바꾸지 않으니, 버린 만큼이 정확히 오차가 됩니다.

계수를 빨리 구하는 방법에도 곡절이 있습니다. 길이 N인 자료의 계수를 정의대로 모두 구하면 곱셈이 약 N²번 듭니다. 계수 N개마다 자료 N개를 곱해 더하기 때문입니다. 1965년 IBM의 제임스 쿨리와 프린스턴의 존 튜키가 발표한 고속 푸리에 변환⁠(fast Fourier transform)⁠은 자료를 반씩 쪼개 푸는 분할 정복⁠(divide and conquer)⁠으로 이것을 N log N번 정도로 줄였습니다. N = 1,024라면 백만 번 남짓이 1만 번 남짓(1,024 × 10)으로 줄어드는 셈입니다. 튜키가 이 생각을 한 것은 케네디 대통령의 과학 자문 위원회에서 소련의 핵실험을 나라 밖의 지진계로 잡아낼 방법을 논의하던 자리였다고 전합니다. 같은 자리에 있던 IBM의 물리학자 리처드 가윈이 쓸모를 알아보고 튜키를 쿨리와 이어 주었습니다. 뒤에 밝혀진 바로는 가우스가 1805년 무렵 소행성 팔라스와 주노의 궤도⁠(orbit)⁠를 계산하며 같은 쪼개기를 썼지만, 그 원고는 라틴어로 남았다가 그가 죽은 뒤에야 전집에 실렸습니다. JPEG의 코사인 변환도 같은 쪼개기로 빠르게 계산합니다. 이 쪼개기가 분배법칙⁠(distributive law)⁠으로 합을 안쪽으로 밀어 넣는 일이라는 것은 「같은 계산, 다른 덧셈」 7절에 있습니다.

7 · 거꾸로 가는 길여분을 더해 지키기

지금까지는 여분을 없애는 이야기였습니다. 2절의 프림로즈가 겪었듯 여분이 없는 메시지는 잡음에 약합니다. 전화선에는 지직거림이 섞이고, 우주 탐사선의 신호는 희미하고, 디스크의 자기 흔적은 닳습니다. 이 절의 물음은 이것입니다. 일부가 뒤집혀 도착해도 받는 쪽이 스스로 알아채고 고칠 수 있게, 여분을 어떻게 더할까?

섀넌의 1948년 논문은 이쪽에도 답을 주었습니다. 신호가 지나가는 전달 경로를 통로라 부르면, 잡음이 있는 통로에도 통로 용량⁠(channel capacity)⁠이라는 속도의 한계가 있습니다. 통로를 여러 번 쓰며 긴 메시지를 보낼 때, 한 번 쓸 때마다 평균적으로 믿을 수 있게 실을 수 있는 비트 수의 한계입니다. 그보다 느리게 보내기만 하면, 메시지를 길게 묶고 여분을 영리하게 덧붙여 오류 확률을 얼마든지 작게 만들 수 있다는 것이 섀넌의 통로 부호화 정리⁠(noisy-channel coding theorem)⁠입니다. 잡음이 있어도 완벽에 가깝게 통신할 수 있다는 이 결론은 당시 공학자들에게 놀라운 것이었습니다. 흔히 오류를 줄이려면 같은 것을 여러 번 보내 속도를 한없이 낮춰야 한다고 생각했는데, 섀넌은 용량⁠(capacity)⁠보다 느리기만 하면 속도를 0으로 낮추지 않아도 된다고 말한 것입니다.

다만 섀넌의 증명은 무작위로 고른 부호가 평균적으로 잘 된다는 논증이어서, 실제로 쓸 부호를 어떻게 만들지는 알려 주지 않았습니다. 이 이야기의 나머지, 대서양 해저 케이블에서 5G의 극 부호⁠(polar code)⁠까지는 짝이 되는 글 「잡음 너머로」에서 따라갑니다.

실제로 쓸 수 있는 오류 정정 부호⁠(error-correcting code)⁠를 가장 먼저 내놓은 사람 가운데 하나가 같은 연구소의 리처드 해밍이었습니다. 주말마다 오류로 멈추는 계전기⁠(relay)⁠ 계산기에 지친 그가 1950년 발표한 부호와, 그 바탕에 있는 해밍 거리⁠(Hamming distance)⁠의 이야기는 「까마귀와 택시」 5절에 있습니다. 섀넌의 1948년 논문에도 동료 해밍의 이 부호가 예로 실렸습니다. 여기서는 받는 쪽이 틀린 비트를 어떻게 찾아내는지를 직접 봅니다.

가장 쉬운 여분부터 봅시다. 비트마다 세 번씩 보내는 것입니다. 1을 111로 보냈는데 101로 도착하면, 셋 가운데 많은 쪽을 따라 1로 읽습니다. 셋 가운데 하나까지 뒤집혀도 고칠 수 있지만, 데이터 1비트에 3비트를 쓰니 전선을 세 배로 씁니다. 해밍의 부호는 같은 일을 훨씬 적은 여분으로 합니다.

해밍 부호⁠(Hamming code)⁠는 1부터 7까지 번호 붙은 일곱 자리를 씁니다. 데이터 4비트를 3, 5, 6, 7번 자리에 넣고, 1, 2, 4번에는 오류 정정 부호의 검사 비트⁠(check bit)⁠를 넣습니다. 이 번호들을 이진수(0과 1만으로 적는 수, 자리가 오른쪽부터 1, 2, 4를 뜻합니다)로 적어 두면 다음 설명이 쉬워집니다.

1 = 001, 2 = 010, 3 = 011, 4 = 100, 5 = 101, 6 = 110, 7 = 111

원 세 개가 자리들을 나눠 감시합니다. 원 1은 이진수의 맨 오른쪽 자리가 1인 번호(1, 3, 5, 7), 원 2는 가운데 자리가 1인 번호(2, 3, 6, 7), 원 4는 맨 왼쪽 자리가 1인 번호(4, 5, 6, 7)를 감시합니다. 검사 비트는 원 하나 안에 든 1의 개수가 짝수가 되도록 정합니다(2로 나눈 나머지⁠(remainder)⁠가 0이 되도록). 원 1에는 검사 비트가 1번 자리 하나뿐이니, 1번 자리가 원 1을 짝수로 맞춥니다. 2번과 4번도 마찬가지입니다.

데이터 1011로 해 봅시다. 3, 5, 6, 7번 자리에 차례로 1, 0, 1, 1이 들어갑니다. 원 1의 데이터 자리 3, 5, 7에는 1, 0, 1로 1이 두 개이니 1번 자리는 0입니다. 원 2의 데이터 자리 3, 6, 7에는 1, 1, 1로 셋이니 2번 자리는 1입니다. 원 4의 데이터 자리 5, 6, 7에는 0, 1, 1로 둘이니 4번 자리는 0입니다. 그래서 보내는 말은 1번부터 7번까지 0110011입니다.

그림에서 직접 해 보세요. 보낸 말의 데이터 칸을 눌러 데이터를 바꾸고, 받은 말의 칸(또는 원 속의 수)을 눌러 잡음이 비트를 뒤집게 합니다. 볼 것은 어느 원이 빨개지는지와, 그 원들의 번호가 뒤집은 자리와 어떤 관계인지입니다.

보낸 말은 , 받은 말은 입니다. 잡음 지우기

비밀은 번호 붙이기에 있습니다. 보낸 말 0110011의 6번 자리가 뒤집혀 0110001로 도착했다고 합시다. 6 = 110이니 6번 자리는 원 2와 원 4에 들어 있고 원 1에는 없습니다. 그래서 원 2와 원 4에서만 1의 개수가 하나 바뀌어 홀수가 되고, 원 1은 짝수 그대로입니다. 홀수가 된 원의 번호를 더하면 2 + 4 = 6, 곧 틀린 자리입니다. 어느 자리가 뒤집히든 마찬가지입니다. 그 자리의 번호를 이진수로 적었을 때 1인 자리에 해당하는 원들만 홀수가 되니, 홀수가 된 원의 번호를 더하면 뒤집힌 자리의 번호가 그대로 나옵니다. 세 원이 홀수인지(1) 짝수인지(0)를 적은 세 비트를 신드롬⁠(syndrome)⁠이라고 하고, 000이면 '오류 없음'입니다.

같은 것을 계산 한 줄로도 적을 수 있습니다. 받은 말에서 1이 있는 자리의 번호들을 이진수로 적고 배타적 논리합(자리마다 두 비트가 다르면 1, 같으면 0)으로 합치면 신드롬이 나옵니다. 보낸 말 0110011에서 1이 있는 자리는 2, 3, 6, 7이고, 010, 011, 110, 111을 자리마다 합치면 000입니다(자리마다 1이 짝수 개씩 있으니까요). 올바른 부호어에서는 그 값이 0이 되도록 검사 비트를 골라 두었기 때문입니다. 6번이 뒤집힌 0110001에서는 1이 2, 3, 7에 있고, 010, 011, 111을 합치면 110, 곧 6입니다.

7비트 중 4비트가 데이터이니, 보낸 비트 가운데 데이터의 비율인 부호율⁠(code rate)⁠은 $4/7$입니다. 한 묶음에서 한 비트의 오류를 고친다는 점은 같은 비트를 세 번 보내는 방법(부호율 $1/3$)과 같으면서, 데이터 4비트에 12비트가 아니라 7비트만 씁니다. 비트 두 개를 뒤집어 보면 이 부호의 한계도 보입니다. 예를 들어 6번과 7번을 함께 뒤집으면 원 2와 원 4는 두 번 바뀌어 다시 짝수가 되고 원 1만 홀수가 되니, 신드롬은 1번 자리를 가리킵니다. 받는 쪽은 멀쩡한 1번을 '고쳐' 틀린 비트가 셋이 됩니다. 이 부호는 오류가 하나라고 믿고 고칩니다.

섀넌은 두 일을 나눠서 해도, 메시지를 길게 묶어 보내는 극한⁠(limit)⁠에서는 손해가 없다는 것도 보였습니다. 먼저 여분을 모두 짜내 엔트로피까지 압축하고, 그다음 통로에 맞춰 규칙적인 여분을 새로 덧붙이는 것입니다. 영어 글의 여분은 잡음을 막기에 엉성한 여분이고, 검사 비트는 설계된 여분입니다. 오늘날 휴대 전화가 사진 한 장을 보낼 때에도 JPEG가 줄이고 오류 정정 부호가 다시 불리는, 이 분업이 일어납니다. 정리하면, 압축은 쓸모없는 여분을 없애고, 오류 정정 부호는 잡음에 맞게 설계한 여분을 다시 넣습니다.

그 뒤 70년은 섀넌의 한계에 다가가는 역사였습니다. 1960년 어빙 리드와 구스타브 솔로몬이 만든 리드–솔로몬 부호⁠(Reed–Solomon code)⁠는 CD와 QR 코드에 들어갔습니다(「까마귀와 택시」). 1993년 프랑스 브레스트의 클로드 베루 연구진이 발표한 터보 부호⁠(turbo code)⁠는 섀넌의 한계에 바짝 다가가 학계를 놀라게 했습니다. 1998년 로버트 매클리스 등은 이 부호를 푸는 방법이, 인공지능⁠(artificial intelligence)⁠ 연구자 주디아 펄이 1982년 확률 추론을 위해 내놓은 믿음 전파⁠(belief propagation)⁠와 같은 계산이라는 것을 밝혔습니다. 믿음 전파는 서로 얽힌 변수들이 이웃끼리 '내가 보기엔 네가 이 값일 확률이 얼마다'라는 쪽지를 주고받으며 추측을 다듬어 가는 계산입니다(「같은 계산, 다른 덧셈」 7절).

이 무렵 LDPC 부호⁠(low-density parity-check code)⁠도 다시 발견되었습니다. 이름은 저밀도 패리티 검사 부호의 머리글자이고, 패리티⁠(parity)⁠는 1의 개수가 짝수인지 홀수인지를 말합니다. 곧 해밍 부호의 원처럼 1의 개수를 짝수로 맞추는 검사를 여럿 두되, 검사 하나하나가 몇 안 되는 비트만 감시하는 부호입니다. 1960년 MIT의 로버트 갤러거가 박사 논문에서 내놓았다가 당시 컴퓨터로는 풀기가 벅차 잊혔던 것입니다. 2009년에는 튀르키예의 정보 이론가 에르달 아리칸이 극 부호를 내놓았습니다. 통로를 여러 번 쓰는 것을 정해진 방식으로 얽어 묶으면 비트 하나하나가 겪는 통로가 거의 완벽한 것과 거의 쓸모없는 것으로 갈라지는데, 좋은 쪽에만 데이터를 싣는 부호입니다. LDPC 부호와 극 부호는 오늘날 5G 이동통신 표준에 들어가 있습니다.

8 · 더 줄일 수 없는 것비둘기집과 콜모고로프

어떤 파일이든 조금씩은 줄여 주는 압축 프로그램이 있을까요? 그런 프로그램이 있다면 압축한 파일을 다시 압축하고, 또 압축해서 무엇이든 한 비트로 만들 수 있을 것입니다. 무언가 이상합니다. 이 절의 물음은 이것입니다. 무엇이든 줄이는 압축은 왜 불가능하고, 끝내 줄일 수 없는 것은 무엇인가?

이상한 이유는 셈 하나로 드러납니다. 길이 3인 비트열부터 세어 봅시다. 자리마다 0과 1 두 가지이니 $2 \times 2 \times 2 = 8$개(000부터 111까지)입니다. 그보다 짧은 것은 길이 2가 4개, 길이 1이 2개, 길이 0인 빈 문자열 ε(글자가 하나도 없는 줄)이 1개로, 모두 7개뿐입니다. 일반적으로 길이 $n$인 비트열은 $2^n$개이고, 그보다 짧은 비트열은 길이 0부터 $n-1$까지 다 합쳐도

개뿐입니다. 왼쪽에 1을 하나 더 보태 보면 까닭이 보입니다. 1 + 1 = 2, 2 + 2 = 4, 4 + 4 = 8처럼 앞에서부터 차례로 두 배가 되어 끝에는 $2^n$이 되니, 보태기 전의 합은 $2^n - 1$입니다.

무손실 압축⁠(lossless compression)⁠은 서로 다른 입력을 서로 다른 출력으로 보내야 합니다. 두 입력이 같은 출력이 되면, 되살릴 때 둘 중 어느 것이었는지 알 수 없기 때문입니다. 그러니 $2^n$개를 모두 더 짧은 $2^n - 1$개에 서로 다르게 넣을 수는 없습니다. 비둘기가 비둘기집보다 많으면 어느 집엔가 두 마리가 들어가야 한다는 비둘기집 원리⁠(pigeonhole principle)⁠입니다. 길이 $n =$ 인 문자열 개와 더 짧은 문자열 개로 직접 짝을 지어 봅시다. 재생 단추를 누르면 한 쌍씩 짝을 짓습니다. 마지막에 무엇이 남는지 보세요.

어떤 순서로 짝을 지어도 짧은 쪽이 꼭 하나 모자랍니다. 그러니 길이 n인 문자열 가운데 적어도 하나는 줄어들지 못합니다. 흔히 이 결론을 '압축은 쓸모없다'로 잘못 읽지만, 이 셈이 말하는 것은 모든 파일을 줄일 수는 없다는 것뿐입니다. 어떤 파일이 줄어들면 그 대가로 다른 어떤 파일은 줄지 않거나 늘어납니다.

셈을 조금 더 하면 더 강한 말을 할 수 있습니다. 길이 20인 문자열 $2^{20} = 1{,}048{,}576$개 가운데 10비트 이상 줄어드는 것은 몇 개일 수 있을까요? 그런 문자열은 길이 10 이하인 문자열로 가야 하고, 길이 10 이하인 문자열은 위의 셈대로 $2^{11} - 1 = 2{,}047$개뿐입니다. 전체의 약 0.2%입니다. 일반적으로 $k$비트 이상 줄어드는 문자열은 길이가 $n-k$ 이하인 문자열로 가야 하는데, 그런 문자열은 모두 $2^{n-k+1}-1$개뿐이니, 전체 $2^n$개의 $1/2^{k-1}$도 안 됩니다. 10비트 이상 줄어드는 파일은 천 개 중 둘도 안 된다는 뜻입니다($1/2^9 = 1/512$). 압축 프로그램이 쓸모 있는 것은 우리가 다루는 파일이 모든 가능한 비트열 가운데 극히 일부, 곧 규칙이 있는 것들이기 때문입니다. 이미 잘 압축한 파일은 그 규칙을 거의 다 써 버렸으니 다시 압축해도 대개 줄지 않습니다. 모든 파일을 줄여 준다는 광고가 있다면 이 셈과 어긋납니다.

그렇다면 '규칙이 없다'는 것은 정확히 무슨 뜻일까요? 1960년대에 세 사람이 따로 같은 답에 이르렀습니다. 미국의 레이 솔로모노프(1964), 모스크바의 안드레이 콜모고로프(1965), 그리고 10대에 이 문제를 붙잡은 아르헨티나계 미국 수학자 그레고리 차이틴입니다. 문자열 $x$를 출력하고 멈추는 가장 짧은 프로그램의 길이(비트 수)를 $x$의 콜모고로프 복잡도⁠(Kolmogorov complexity)⁠ $K(x)$라고 합니다. 문자열을 가장 짧게 적는 설명의 길이이고, 이때 설명은 '실행하면 그 문자열을 내놓는 프로그램'이어야 합니다.

프로그램을 적는 언어를 바꾸면 값이 달라지지 않을까요? 달라지지만, 그 차이는 문자열과 상관없는 일정한 상수를 넘지 않습니다. 언어 B로 쓴 프로그램은, 언어 B를 읽어 실행해 주는 번역기를 언어 A로 한 번 짜서 앞에 붙이면 언어 A의 프로그램이 됩니다. 그러니 A로 잰 값은 B로 잰 값보다 많아야 그 번역기의 길이만큼만 깁니다. 그래서 긴 문자열에서는 언어를 무엇으로 고르든 상대적으로 거의 같은 값이 됩니다.

01을 500번 되풀이한 1,000비트는 "01을 500번 써라"라는 짧은 프로그램이 있으니 복잡도가 작습니다. 원주율⁠(pi)⁠의 처음 백만 자리는 여러 통계⁠(statistics)⁠ 검사를 통과할 만큼 무작위처럼 보이지만, 원주율을 계산하는 짧은 프로그램이 있으니 역시 복잡도가 작습니다. 반면 동전을 1,000번 던져 얻은 비트열에는 거의 틀림없이 그 자체보다 크게 짧은 설명이 없습니다. 프로그램도 비트열이고 프로그램 하나는 문자열 하나만 출력하니, 위의 셈이 그대로 통합니다. 그래서 10비트 넘게 줄어들 확률조차 500분의 1이 안 됩니다. 콜모고로프가 강조했듯, 이렇게 하면 '무작위'를 확률 없이 대상 하나에 대해 정의할 수 있습니다. 몇 비트 넘게는 줄일 수 없는 것이 무작위한 것입니다. 유한한 문자열에서 무작위는 이처럼 정도의 문제입니다. 엔트로피가 원천이 내놓는 글들의 평균이 넘지 못하는 한계라면, 콜모고로프 복잡도는 문자열 하나가 넘지 못하는 한계입니다.

그런데 이 수는 계산할 수 없습니다. 20세기 초 러셀이 옥스퍼드 보들리 도서관의 사서 G. G. 베리에게서 들었다며 소개한 역설을 요즘 흔히 쓰는 꼴로 적어 봅시다. "스무 단어 이하로 정의할 수 없는 가장 작은 자연수⁠(natural number)⁠"는 방금 스무 단어 이하로 정의되었습니다(러셀의 역설⁠(Russell's paradox)⁠처럼 자기를 가리키는 말이 만든 모순입니다). 말로 된 이 역설은 '정의한다'는 말이 흐릿해서 생기지만, 프로그램으로 옮기면 흐릿함이 사라지고 역설이 증명이 됩니다.

$K$를 계산하는 프로그램이 있다고 해 봅시다. 그러면 이런 프로그램을 짤 수 있습니다. "비트열을 짧은 것부터 차례로 늘어놓고, 하나씩 복잡도를 계산해서, 복잡도가 백만보다 큰 첫 문자열을 출력하라." 그런 문자열은 반드시 있습니다. 위의 셈대로 백만 비트 이하의 프로그램은 유한 개라 그것들이 출력하는 문자열도 유한 개이기 때문입니다. 이 프로그램의 길이는 K를 계산하는 부분과 몇 줄의 명령, 그리고 '백만'이라는 수(이진수로 20자리)를 적은 것이니, 백만 비트보다 훨씬 짧습니다. 그러면 복잡도가 백만보다 큰 문자열을 그보다 훨씬 짧은 프로그램이 출력한 셈이니, 복잡도의 정의와 어긋납니다. 그러므로 K를 계산하는 프로그램은 있을 수 없습니다.

짧은 프로그램을 모두 돌려 보면 되지 않느냐는 방법이 통하지 않는 까닭은, 어떤 프로그램이 끝내 멈출지 미리 알 수 없기 때문입니다. 아직 돌고 있는 프로그램이 조금 뒤에 멈춰 더 짧은 설명을 내놓을지, 영원히 돌지 알 방법이 없습니다. 이것이 정지 문제⁠(halting problem)⁠입니다(「기계가 풀 수 없는 문제」).

차이틴은 같은 논증으로 다음을 보였습니다. 형식 체계⁠(formal system)⁠, 곧 공리⁠(axiom)⁠와 추론 규칙을 정해 둔 증명의 체계가 산수를 담을 만큼 강하고, 모순이 없으며, 증명을 기계적으로 검사할 수 있다고 합시다. 그러면 어느 체계든 충분히 큰 $N$에 대해서는 "이 문자열의 복잡도는 $N$보다 크다"는 참인 문장들을 증명하지 못합니다. 불완전성 정리⁠(incompleteness theorem)⁠의 또 다른 얼굴입니다. 까닭은 앞의 논증과 같습니다. 체계의 증명들을 차례로 검사하다가 "이 문자열의 복잡도는 N보다 크다"는 꼴의 증명이 처음 나오면 그 문자열을 출력하는 프로그램은, N이 크면 N비트보다 훨씬 짧습니다. 그러니 그런 증명이 하나라도 있다면, 그 문자열은 짧은 프로그램이 출력하므로 복잡도가 작다는 사실도 체계 안에서 증명되어 체계가 모순을 품게 됩니다. 정리하면, 대부분의 문자열은 거의 줄일 수 없지만, 어느 문자열이 그런지를 계산으로 가려낼 수는 없습니다.

이 생각은 철학의 오래된 원칙과 닿습니다. 같은 현상을 설명한다면 더 단순한 설명을 택하라는 원칙에는 14세기 영국의 철학자 오컴의 윌리엄의 이름이 붙어 있습니다. 솔로모노프는 이 '오컴의 면도날⁠(Occam's razor)⁠'을 '자료를 출력하는 짧은 프로그램일수록 믿음을 더 주라'는 귀납 추론⁠(inductive inference)⁠의 규칙으로 바꾸었습니다. 이 규칙이 베이즈 정리⁠(Bayes' theorem)⁠와 어떻게 정확히 맞물리는지, 그리고 케플러가 튀코 브라헤의 관측표를 세 법칙으로 줄인 일을 비트로 세는 셈은 「압축하는 것이 이해하는 것이다」에 있습니다.

과학 법칙은 관측 기록을 압축한 것이라는 관점도 있습니다. 행성의 위치를 수천 줄 적는 대신 케플러의 세 법칙과 행성마다 궤도를 정하는 수 몇 개를 적으면 됩니다. 반대로 자료를 통째로 외우는 모형은 압축을 하지 못한 것이고, 새 자료 앞에서 틀립니다(과적합⁠, overfitting⁠).

오늘날의 언어 모델⁠(language model)⁠은 다음 토큰(낱말이나 낱말 조각)의 확률을 예측합니다. 예측이 좋을수록 산술 부호화로 글을 더 짧게 적을 수 있으니, 예측과 압축은 한 동전의 양면입니다(「배우는 기계」, 「다음 단어를 맞히는 기계」). 2006년부터는 위키백과의 일부를 가장 작게 압축하는 사람에게 상금을 주는 대회(후터 상)도 열리고 있습니다. 잘 압축하는 것이 잘 이해하는 것이라는 믿음에서입니다. 그 대회가 풀기 프로그램의 크기까지 셈에 넣는 까닭과, 큰 언어 모델을 같은 자로 재면 어떻게 되는지는 「압축하는 것이 이해하는 것이다」 8절에 있습니다.

9 · 이어지는 길짧게 보내는 수학이 닿는 곳

• 언어: 영어 글의 엔트로피를 사람의 추측 게임으로 잰 섀넌의 실험, n-그램⁠(n-gram)⁠ 언어 모델과 마르코프 연쇄⁠(Markov chain)⁠, 낱말 빈도의 지프의 법칙⁠(Zipf's law)⁠은 「말을 세는 기계」에 있습니다. 부호집과 허프만 부호가 흔한 것에 짧은 이름을 주었듯, 언어도 자주 쓰는 낱말일수록 짧아지는 경향이 있다는 것이 지프의 관찰이었습니다.
• 정렬: $n$개를 비교만으로 정렬하려면 $n!$가지 순서 가운데 하나를 예·아니오 질문으로 가려내야 하니 가장 나쁜 경우 적어도 $\log_2 n!$번의 비교가 듭니다(비교 정렬의 하한⁠, comparison sorting lower bound⁠). 3절의 스무고개와 같은 논증입니다(「줄 세우기의 한계」).
• 암호: 섀넌은 1949년 같은 도구로 비밀 통신을 분석했습니다. 좋은 암호문⁠(ciphertext)⁠은 무작위처럼 보여야 하니 압축되지 않고, 그래서 압축은 암호화보다 먼저 해야 합니다(「나머지로 지키는 비밀」).
• 파동: JPEG와 MP3의 코사인은 푸리에가 열의 흐름을 풀려고 쓴 사인과 코사인⁠(sine and cosine)⁠의 후손입니다. 계산을 빠르게 하는 고속 변환(고속 푸리에 변환)은 분할 정복의 대표 예입니다(「원에서 파동으로」). 그림 한 장을 밝기의 표(행렬⁠, matrix⁠)로 보고 그 그림에 가장 잘 맞는 무늬를 자료에서 직접 구하면 특잇값 분해⁠(singular value decomposition)⁠가 됩니다. 가장 중요한 무늬 k개(특잇값⁠(singular value)⁠이 큰 k개)만 남긴 그림은, 모든 줄을 무늬 k개만 섞어 만들 수 있는 그림(랭크가 k 이하인 행렬) 가운데 원래 그림에 제곱 오차로 가장 가깝습니다. 코사인 무늬는 모든 그림에 같은 축을 쓰므로 축을 따로 적어 보낼 필요가 없습니다.
• 잡음: 7절에서 잠깐 본 반대 방향, 곧 여분을 더해 지키는 일의 역사는 1858년 대서양 케이블에서 하틀리와 나이퀴스트, 섀넌의 통로 용량을 거쳐 5G의 극 부호까지 「잡음 너머로」에서 따라갑니다.
• 과학: 짧게 적는 것이 곧 잘 설명하는 것이라는 생각, 곧 크래프트 부등식으로 부호의 길이를 확률로 읽고, 두 부분 부호⁠(two-part code)⁠로 가설과 자료를 함께 재는 최소 기술 길이⁠(minimum description length)⁠는 「압축하는 것이 이해하는 것이다」에 있습니다. 1절의 모스 띠를 줄이던 셈이 그 글에서는 케플러의 법칙을 재는 자가 됩니다.
• 한 줄의 계산: 오류 정정 부호를 푸는 비터비 알고리즘과 터보 부호의 메시지 전달, 그리고 고속 푸리에 변환이 모두 분배법칙으로 공통 인수를 묶어 내는 같은 계산이라는 것은 「같은 계산, 다른 덧셈」에 있습니다.
• 언어 모델: 1994년 필립 게이지가 파일 압축을 위해 내놓은 바이트 쌍 부호화⁠(byte-pair encoding)⁠가 오늘날 언어 모델이 글을 토큰⁠(token)⁠으로 자르는 방법이 된 내력, 그리고 교차 엔트로피⁠(cross-entropy)⁠가 곧 산술 부호화의 길이라는 것은 「다음 단어를 맞히는 기계」 2절과 7절에 있습니다.
• 질서와 무질서: 대부분의 긴 비트열은 콜모고로프의 뜻에서 무작위이지만, 램지 이론⁠(Ramsey theory)⁠은 아무리 무작위한 구조에도 충분히 크면 작은 질서의 섬이 반드시 있다고 말합니다. 두 사실은 어긋나지 않습니다. 무작위한 문자열 안에도 짧은 규칙적 조각은 있지만, 그 조각들로 전체를 짧게 적을 수는 없습니다(「완전한 무질서는 없다」).
• 확률: 엔트로피는 놀람의 기댓값⁠(expected value)⁠이고, 원천 부호화 정리의 속은 큰 수의 법칙⁠(law of large numbers)⁠입니다. 확률이라는 생각의 출발은 「도박판에서 온 편지」에 있습니다.
• 계산: 콜모고로프 복잡도는 튜링 기계⁠(Turing machine)⁠ 위에서 정의되고, 정지 문제 때문에 계산할 수 없습니다(「기계가 풀 수 없는 문제」).