허프만 부호화 해설

컴퓨터는 보통 모든 글자를 같은 비트 수로 저장합니다. 일반 ASCII에서는 8비트입니다. 단순하지만 낭비가 있습니다. 어떤 글자는 다른 글자보다 훨씬 흔하기 때문입니다. 1951년, 한 학생이 각 기호에 저마다 길이가 다른 부호를 주는 가장 좋은 방법을 찾아냈습니다. 자주 나오는 기호는 짧게, 드문 기호는 길게 하는 방법으로, 그 구성은 몇 줄에 들어갈 만큼 단순합니다. 오늘날 허프만 부호화는 여러분이 여는 거의 모든 압축 파일, 이미지, 소리에 들어 있습니다.

ABRACADABRA의 글자들을 잎으로 하고, 가지에 0과 1이 표시되어 있으며, A의 짧은 부호가 강조된 허프만 트리
ABRACADABRA의 글자들을 잎으로 하고, 가지에 0과 1이 표시되어 있으며, A의 짧은 부호가 강조된 허프만 트리

흔한 기호에는 짧은 부호를

모스 부호는 이미 1830년대에 이 아이디어를 썼습니다. 영어에서 가장 흔한 글자인 E는 점 하나이고, Q는 선 선 점 선입니다. 이런 부호는 어떤 기호가 다른 기호보다 자주 나올 때면 언제나 시간과 공간을 아껴 줍니다. 하지만 길이가 제각각이면 문제가 생깁니다. 모스 부호는 쉼으로 이를 해결했지만, 한 부호가 어디서 끝나고 다음 부호가 어디서 시작하는지 어떻게 알 수 있을까요? 그리고 합계를 가장 작게 하려면 각 기호에 어떤 길이를 주어야 할까요?

접두 부호

어떤 부호도 다른 부호의 앞부분이 아니라면 첫 번째 문제는 사라집니다. A = 0, B = 10, C = 110, D = 111이라는 부호에서 비트 0101100은 A B C A로만 읽을 수 있습니다. 지금까지 읽은 비트가 하나의 부호를 이루는 순간, 그 부호는 완성되기 때문입니다. 이런 접두 부호는 기호를 잎에 둔 이진 트리와 정확히 대응하며, 각 왼쪽 가지는 0을, 각 오른쪽 가지는 1을 나타냅니다. 부호를 고르는 것은 곧 트리를 고르는 것입니다.

허프만의 구성법

기호마다 잎 하나로 시작하고, 각 잎에 그 기호가 나오는 횟수를 가중치로 줍니다. 가장 가벼운 두 트리를 골라 둘의 합을 가중치로 하는 새 노드 아래에 묶고, 트리가 하나만 남을 때까지 되풀이합니다. 이것이 알고리즘의 전부입니다. 드문 기호는 먼저 묶여 트리 깊은 곳에 자리하고 긴 부호를 얻습니다. 흔한 기호는 마지막에 묶여 맨 위 가까이에 머물고 짧은 부호를 얻습니다. 우선순위 큐를 쓰면 기호가 n개일 때 n log n에 비례하는 시간이 걸립니다.

최적인 이유

가장 좋은 트리에서는 가장 드문 두 기호를 언제나 가장 깊은 층에 형제로 둘 수 있습니다. 그 자리에 있던 것과 맞바꾸면 합계는 줄어들 뿐이기 때문입니다. 두 기호를 가중치를 합친 하나의 기호로 묶으면, 나머지는 기호가 하나 적은 같은 문제가 됩니다. 그래서 이 탐욕적인 단계는 결코 최선의 답으로 가는 길을 막지 않습니다. 사용되는 전체 비트 수는 모든 내부 노드의 가중치를 더한 값과 같고, 묶는 과정은 이 값을 가능한 한 작게 유지합니다.

시험 대신 과제 논문

1951년, MIT 대학원생 데이비드 허프만은 로버트 파노의 정보 이론 수업을 들었습니다. 파노는 학생들에게 기말시험을 보거나, 가장 효율적인 이진 부호를 찾는 문제에 관한 과제 논문을 쓰거나 둘 중 하나를 고르게 했습니다. 허프만은 논문을 거의 포기하려던 참에, 섀넌-파노 방법처럼 위에서 아래로 나누는 대신 아래에서 위로 트리를 쌓아 올리면 언제나 최선의 결과가 나온다는 것을 깨달았습니다. 그는 1952년에 이를 발표했습니다. 학생의 방법이 교수가 클로드 섀넌과 함께 만든 방법을 이긴 것입니다.

UC 산타크루즈 교수 시절에 촬영된 데이비드 허프먼. 1951년 MIT 대학원생이던 그는 로버트 파노의 강의 학기말 보고서에서 최적 부호를 찾아냈다.
UC 산타크루즈 교수 시절에 촬영된 데이비드 허프먼. 1951년 MIT 대학원생이던 그는 로버트 파노의 강의 학기말 보고서에서 최적 부호를 찾아냈다.
클로드 섀넌. 1948년 벨 연구소에서 메시지가 담는 정보량을 정밀히 정의하고 비트로 측정했다.
클로드 섀넌. 1948년 벨 연구소에서 메시지가 담는 정보량을 정밀히 정의하고 비트로 측정했다.

엔트로피에 가깝게

클로드 섀넌은 어떤 부호도 평균적으로 기호당 정보원의 엔트로피보다 적은 비트를 쓸 수 없음을 보였습니다. 허프만 부호는 모든 확률이 2분의 1의 거듭제곱일 때 정확히 엔트로피에 이르며, 기호당 엔트로피보다 꼬박 1비트 많아지는 일은 결코 없습니다. 이 차이는 한 기호가 아주 흔할 때 중요해집니다. 비율이 99%인 기호는 약 0.015비트의 정보만 담는데도 적어도 1비트를 통째로 써야 합니다. 산술 부호화와 최신 압축기의 비대칭 숫자 체계(ANS)는 이 한계를 피합니다.

어디에나 있는 허프만 부호

허프만 부호화는 단독으로 쓰이는 일은 드물지만, 많은 형식의 마지막 단계를 이룹니다. ZIP, gzip, PNG 안에 있는 Deflate는 먼저 반복을 참조로 바꾼 다음, 그 결과를 허프만 부호로 씁니다. JPEG는 이미지를 변환하고 남은 숫자에, MP3는 오디오 데이터에, 팩스는 검은색과 흰색 런의 길이에 허프만 부호를 씁니다. 형식들은 보통 정규 허프만 부호를 보냅니다. 부호 자체는 부호 길이로부터 다시 만들 수 있으므로 부호 길이만 저장하면 되기 때문입니다.

직접 해 보기

허프만 부호 빌더를 열어 ABRACADABRA, MISSISSIPPI RIVER, 직접 쓴 문장이나 다른 어떤 텍스트든 그 트리를 한 단계씩 만들어 보세요. 단계마다 가장 가벼운 두 트리가 묶이는 모습을 지켜보고, 잎을 클릭해 부호를 확인하고, 부호화된 비트 속에서 기호를 따라가며, 합계를 고정 길이 부호, UTF-8, 엔트로피와 비교해 보세요.

자주 묻는 질문

허프만 부호화와 섀넌-파노 부호화의 차이는 무엇인가요?

섀넌-파노 부호화는 기호들을 가중치가 거의 같은 두 그룹으로 나누는 일을 되풀이하며 위에서부터 트리를 만듭니다. 대개 좋은 결과를 내지만 항상 최적인 것은 아닙니다. 허프만 부호화는 가장 가벼운 두 트리를 묶어 아래에서부터 트리를 만들며, 언제나 가능한 가장 짧은 접두 부호를 줍니다.

복호기에 트리가 필요한가요?

네, 같은 부호가 필요합니다. 그래서 압축 파일은 이를 저장하는데, 보통 정규 부호의 부호 길이 목록으로 저장하므로 수십 바이트밖에 들지 않습니다. 짧은 텍스트에서는 이 부담이 절약분보다 클 수 있습니다. 이 빌더는 부호화된 비트만 셉니다.

허프만 부호화로 파일이 더 커질 수 있나요?

부호화된 기호는 같은 기호에 대한 고정 길이 부호보다 더 많은 비트를 쓰는 일이 없습니다. 하지만 부호표도 저장해야 하므로, 아주 짧거나 거의 무작위인 데이터에서는 결과가 원본보다 조금 커질 수 있습니다.

크래프트 부등식은 무엇을 말하나요?

부호 길이가 l₁, l₂, …인 접두 부호는, 모든 기호에 대해 2의 −l제곱을 더한 합이 1 이하일 때, 그리고 그때에만 존재한다는 것입니다. 기호가 두 개 이상인 모든 허프만 트리처럼 모든 내부 노드가 자식을 둘씩 가진 트리에서는 그 합이 정확히 1입니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

허프만 부호 빌더 열기