데이비드 허프만(David A. Huffman)

데이비드 허프만은 1925년 미국 오하이오주에서 태어났습니다. 열여덟 살에 오하이오 주립 대학 전기 공학과를 마치고, 2차 세계대전 뒤 해군 장교로 복무한 다음 MIT 대학원에 들어갔습니다. 그 무렵 정보 이론은 막 태어난 분야였습니다. 섀넌의 원천 부호화 정리⁠(source coding theorem)⁠는 기호당 평균 부호 길이가 엔트로피⁠(entropy)⁠보다 짧을 수 없다는 한계를 알려 주었지만, 주어진 확률⁠(probability)⁠에 대해 가장 짧은 부호를 실제로 어떻게 찾는지는 알려 주지 않았습니다. 섀넌과 MIT의 로버트 파노가 내놓은 방법은 기호들을 무게가 비슷한 두 무리로 거듭 자르는 것이었는데, 대개 훌륭했지만 언제나 가장 짧지는 않았습니다.

나이 세 ·

해군에서 그는 구축함에 타고 전쟁 뒤 일본과 중국 앞바다의 기뢰를 치우는 일을 도왔고, 오하이오 주립 대학에서 석사 학위를 받은 뒤 MIT로 갔습니다. 당시 MIT에는 전쟁 중 레이더를 개발한 방사선 연구소의 뒤를 이은 전자 공학 연구소가 있었고, 군의 연구비로 통신, 신경생리학, 언어학의 연구자들이 한 지붕 아래 모여 있었습니다. 노버트 위너의 사이버네틱스⁠(cybernetics)⁠와 섀넌의 정보 이론이 한창 새롭던 때였고, 파노는 막 생겨난 정보 이론을 대학원 과목으로 가르치고 있었습니다.

1951년 파노는 정보 이론 수업의 학생들에게 기말 시험을 보거나, 가장 효율적인 이진 부호를 찾는 방법에 대한 보고서를 내라는 선택권을 주었습니다. 보고서를 고른 대학원생 허프만은 오래 매달리고도 답을 찾지 못해 시험공부를 시작하려던 참에 답을 찾았다고 1991년 한 잡지의 인터뷰에서 회고했습니다. 스승 파노와 섀넌도 이 문제와 씨름했다는 것을 알았다면 시도조차 하지 않았을지 모른다는 말도 덧붙였습니다. 그의 생각은 방향을 뒤집는 것이었습니다. 뿌리에서 무리를 둘로 자르며 내려가지 말고, 잎⁠(leaf)⁠에서 묶으며 올라가자. 가장 드문 두 기호는 어차피 가장 긴 부호를 받을 테니 트리⁠(tree)⁠의 가장 깊은 곳에 형제로 두고, 둘을 확률이 그 합인 새 기호 하나로 봅니다. 그리고 다시 가장 드문 둘을 묶기를 하나가 남을 때까지 되풀이합니다.

확률이 1/2, 1/4, 1/8, 1/8인 네 기호라면 먼저 두 1/8을 묶어 1/4을 만들고, 그것을 남은 1/4과 묶어 1/2을, 마지막으로 두 1/2을 묶습니다. 가지마다 0과 1을 붙이면 부호는 0, 10, 110, 111이 되고, 평균 길이는 1.75비트로 엔트로피와 꼭 같습니다. 매번 눈앞에서 가장 가벼운 둘만 고르는 욕심쟁이 알고리즘⁠(greedy algorithm)⁠인데도 결과는 언제나 최적입니다. 가장 드문 두 기호를 형제로 두는 최적 부호가 늘 있고, 둘을 묶은 작은 문제의 최적 부호를 풀면 원래 문제의 최적 부호가 되므로 수학적 귀납법⁠(mathematical induction)⁠으로 증명이 끝납니다. 눈앞의 최선이 전체의 최선이 되는 드문 경우를 알아본 것입니다(가장 좋은 것 고르기). 가장 가벼운 둘을 빨리 꺼내는 데에는 우선순위 큐⁠(priority queue)⁠를 씁니다. 논문 「최소 중복 부호의 구성법」은 1952년에 나왔습니다.

허프만 부호⁠(Huffman coding)⁠의 평균 길이는 언제나 엔트로피 이상, 엔트로피에 1비트를 더한 값 미만입니다. 부호 길이가 정수여야 하니 확률 0.99인 기호도 1비트를 쓰는 손해가 남습니다(이 기호의 정보량은 약 0.0145비트입니다). 이 손해는 메시지 전체를 수 하나로 적는 산술 부호화⁠(arithmetic coding)⁠가 메시지가 길수록 거의 없앱니다. 그래도 단순하고 빠른 덕분에 허프만 부호는 70년 넘게 쓰입니다. 1980년 국제 표준이 된 팩스는 흑백 점이 이어지는 길이를 허프만 부호를 고친 부호로 적었고, zip과 PNG가 쓰는 DEFLATE는 지브와 렘펠이 만든 렘펠–지브 압축⁠(Lempel–Ziv compression)⁠으로 반복을 줄인 뒤 그 결과를 다시 허프만 부호로 적으며, JPEG도 이산 코사인 변환⁠(discrete cosine transform)⁠으로 얻은 계수를 마지막에 허프만 부호로 줄입니다. 허프만은 이 방법으로 특허를 내지 않았습니다.

정작 그의 박사 논문(1953)은 부호가 아니라 스위치 회로에 관한 것이었습니다. 지금의 입력뿐 아니라 지나온 상태에 따라 출력이 달라지는 순차 회로⁠(sequential circuit)⁠를 체계적으로 설계하는 방법을 다루었는데, 그런 회로는 상태 사이를 옮겨 다니는 유한 오토마톤⁠(finite automaton)⁠과 같습니다. 필요 없는 상태를 합쳐 회로를 줄이는 그의 방법은 조지 밀리와 에드워드 무어의 연구와 함께 오토마톤⁠(automaton)⁠ 이론의 출발점으로 꼽힙니다. 섀넌이 불 대수⁠(Boolean algebra)⁠로 연 회로 설계를 기억을 가진 회로로 넓힌 셈입니다. 그는 MIT에서 가르치다 1967년 캘리포니아 대학 샌타크루즈로 옮겨 컴퓨터 과학과를 세우는 데 힘을 보탰습니다.

그는 한 분야에 머물지 않는 연구자였습니다. 1971년 논문 「말이 안 되는 문장으로서의 불가능한 도형」에서는 선으로 그린 입체 그림의 선마다 볼록한 모서리, 오목한 모서리, 앞의 면이 뒤를 가리는 경계라는 딱지를 붙이고, 한 꼭짓점⁠(vertex)⁠에서 만나는 선들의 딱지 조합은 몇 가지만 허락된다는 규칙을 세웠습니다. 모든 선에 규칙에 맞는 딱지를 붙일 수 없으면 그 그림은 실제 입체일 수 없습니다. 영국의 맥스 클로스가 같은 해 따로 같은 생각을 내놓아 '허프만–클로스 딱지 붙이기'라 불리는 이 방법은, 컴퓨터가 그림 속 입체를 알아보게 하려던 초기 컴퓨터 비전의 고전이 되었습니다. 제목 그대로 그림을 문법에 맞는지 따지는 문장처럼 다룬 것입니다.

말년의 그는 종이접기의 수학에 빠졌습니다. 종이는 늘이거나 줄일 수 없어서, 접힌 선 밖의 매끈한 부분은 어느 점에서나 가우스 곡률⁠(Gaussian curvature)⁠이 0인 곡면으로만 휘어집니다. 그는 곧은 선이 아니라 곡선을 따라 접을 때 접힘선 양쪽의 곡면이 어떻게 휘어야 하는지를 연구해 1976년 「곡률⁠(curvature)⁠과 접힘: 종이 입문」을 발표했고, 많은 종이 조형을 남겼습니다. 생전에 거의 발표하지 않은 이 작품과 설계도들은 그가 세상을 떠난 뒤 MIT의 에릭 드메인과 동료들이 되살려 분석했고, 오늘날 곡선 종이접기 연구의 출발점으로 꼽힙니다. 1999년 IEEE의 리처드 해밍 메달을 받았고, 그해 10월 세상을 떠났습니다.

이어지는 곳. 흔한 글자에 짧은 부호를 준다는 생각은 모스 부호에서 이미 보였고, 허프만은 그것이 얼마나 짧아질 수 있는지의 답을 알고리즘⁠(algorithm)⁠으로 주었습니다. 틀린 확률표로 짠 부호가 치르는 대가는 쿨백–라이블러 발산⁠(Kullback–Leibler divergence)⁠으로 재고, 스무고개처럼 후보를 반씩 줄이는 이진 탐색⁠(binary search)⁠의 나무도, 예·아니오 질문 하나로 얻는 정보는 많아야 1비트이고 두 답이 반반일 때 꼭 1비트라는 같은 셈을 합니다. 여분을 짜내는 허프만 부호의 반대편에는 여분을 더해 잡음을 이기는 해밍의 오류 정정 부호⁠(error-correcting code)⁠가 있습니다. 그의 종이접기 연구가 기댄 곡률, 곧 곡면을 늘이지 않고 구부리기만 해서는 바꿀 수 없는 휘어짐의 양은 가우스에게서 왔습니다.

관계.

• 영향을 받음 클로드 섀넌 — 허프만 부호는 섀넌의 원천 부호화 정리가 알려 준 한계, 곧 평균 길이는 엔트로피보다 짧을 수 없다는 한계에 가장 가깝게 다가가는 접두 부호를 실제로 찾는 방법이었고, 섀넌–파노 부호⁠(Shannon–Fano code)⁠를 넘어섰습니다.

연표.

• 1944년 열여덟 살에 오하이오 주립 대학 전기 공학과를 마치다
• 1949년 해군 복무를 마치고 오하이오 주립 대학에서 석사 학위를 받다
• 1951년 파노의 정보 이론 수업에서 기말 시험 대신 보고서를 고르다
• 1952년 「최소 중복 부호의 구성법」을 발표하다
• 1953년 순차 스위칭 회로 연구로 MIT에서 박사 학위를 받고 교수진에 합류하다
• 1967년 캘리포니아 대학 샌타크루즈로 옮기다
• 1971년 선 그림에 딱지를 붙여 불가능한 도형을 가려내는 논문을 내다
• 1976년 곡선 접기를 다룬 「곡률과 접힘: 종이 입문」을 발표하다
• 1994년 은퇴하다
• 1999년 IEEE 리처드 해밍 메달을 받다