허프만 트리란 무엇인가?
허프만 코딩(Huffman Coding)은 문자마다 코드를 부여하는 기법으로, 코드의 길이가 해당 문자의 상대적 빈도나 가중치에 따라 결정됩니다. 즉, 자주 사용되는 문자에는 짧은 코드를, 드물게 사용되는 문자에는 긴 코드를 할당하여 전체 데이터를 효율적으로 압축할 수 있습니다.
허프만 코드는 가변 길이(variable-length) 방식이며, 접두어가 없는(prefix-free) 특징을 가집니다. 여기서 '접두어 없음'이란 어떤 코드도 다른 코드의 접두어가 되지 않는다는 의미입니다. 덕분에 디코딩 시 코드 사이의 경계를 혼동하지 않고 고유하게 해석할 수 있습니다.
모든 접두어 자유 이진 코드는 인코딩된 문자가 리프(leaf) 노드에 저장된 이진 트리 형태로 표현할 수 있습니다.
허프만 트리의 정의
허프만 트리(Huffman Tree) 또는 허프만 코딩 트리는 다음과 같이 정의됩니다.
- 주어진 알파벳의 각 문자가 트리의 리프 노드에 대응되는 완전 이진 트리(full binary tree)
- 최소 외부 경로 가중치(minimum external path weight)를 갖는 이진 트리
여기서 '외부 경로 가중치'란 각 리프의 가중치(빈도)와 루트에서 해당 리프까지의 경로 길이를 곱한 값들의 합을 의미합니다. 따라서 허프만 트리의 목표는 주어진 리프 집합에 대해 가중 경로 길이의 합이 최소가 되는 트리를 구성하는 것입니다.
예제: 문자 빈도표
다음은 8개 문자에 대한 빈도(frequency) 정보입니다.
| 문자(Letter) | z | k | m | c | u | d | l | e |
| 빈도(Frequency) | 2 | 7 | 24 | 32 | 37 | 42 | 42 | 120 |
예제: 허프만 코드 결과
위 빈도표를 바탕으로 허프만 트리를 구성하면 다음과 같은 코드가 생성됩니다. 빈도가 가장 높은 'e'는 단 1비트로, 빈도가 가장 낮은 'z'는 6비트로 인코딩되는 것을 확인할 수 있습니다.
| 문자(Letter) | 빈도(Freq) | 코드(Code) | 비트 수(Bits) |
|---|---|---|---|
| e | 120 | 0 | 1 |
| d | 42 | 101 | 3 |
| l | 42 | 110 | 3 |
| u | 37 | 100 | 3 |
| c | 32 | 1110 | 4 |
| m | 24 | 11111 | 5 |
| k | 7 | 111101 | 6 |
| z | 2 | 111100 | 6 |
위 예제에 대한 허프만 트리 구조는 아래 그림과 같습니다.
허프만 트리의 핵심 요약
- 탐욕 알고리즘(Greedy Algorithm) 기반: 매 단계에서 빈도가 가장 작은 두 노드를 선택해 병합합니다.
- 최적성(Optimality): 허프만 코드는 주어진 문자 빈도에 대해 가장 짧은 평균 코드 길이를 보장하는 최적의 접두어 코드입니다.
- 활용 분야: ZIP, JPEG, MP3 등 다양한 데이터 압축 기술의 기반 원리로 활용됩니다.