허프먼 부호화(Huffman coding)는 전산학과 정보이론에서 사용되는 무손실 데이터 압축 기법의 하나로, 엔트로피 부호화(entropy encoding)의 대표적인 방식이다. 문자 또는 기호의 등장 빈도에 따라 서로 다른 길이의 이진 코드를 할당하여, 전체 데이터의 크기를 줄이는 알고리즘이다. 1952년 미국의 컴퓨터 과학자 데이비드 허프먼(David A. Huffman)이 박사과정 학생 시절 발표한 논문 《A Method for the Construction of Minimum-Redundancy Codes》에서 처음 제안되었다.
기본 원리
허프먼 부호화는 각 기호의 출현 빈도수를 통계적으로 분석하여, 빈도가 높은 기호에는 짧은 코드를, 빈도가 낮은 기호에는 긴 코드를 부여한다. 예를 들어 ASCII 인코딩과 같은 고정 길이 인코딩은 모든 문자에 동일한 비트 수(예: 8비트)를 할당하지만, 허프먼 부호화는 가변 길이 비트(variable-length code)를 사용한다. 이 때문에 데이터 내 특정 기호들의 출현 빈도가 불균등할수록 압축 효율이 높아진다.
알고리즘 동작 과정
허프먼 부호화 알고리즘은 다음과 같은 단계로 동작한다.
- 입력 데이터를 탐색하여 각 기호의 등장 빈도수를 계산한다.
- 각 기호와 그 빈도수를 담은 노드들을 우선순위 큐(priority queue)에 삽입한다. 이때 최소 힙(min-heap) 구조가 사용된다.
- 빈도수가 가장 작은 두 노드를 선택하여 하나의 부모 노드로 합친다. 부모 노드의 빈도수는 두 자식 노드의 빈도수의 합이다.
- 합쳐진 부모 노드를 다시 우선순위 큐에 삽입한다.
- 큐에 노드가 하나만 남을 때까지 3~4 과정을 반복하여 허프만 트리(Huffman tree)를 완성한다.
- 완성된 트리의 루트에서부터 재귀적으로 탐색하며, 왼쪽 가지에는 0, 오른쪽 가지에는 1을 부여하여 각 기호의 이진 코드를 생성한다.
이 방식은 그리디 알고리즘(greedy algorithm)의 일종으로 분류되며, 생성된 코드는 접두사 코드(prefix code)의 성질을 지닌다. 즉, 어떤 기호의 코드도 다른 기호의 코드의 앞부분(prefix)이 되지 않으므로, 복호화 과정에서 모호성이 발생하지 않는다.
특성 및 시간 복잡도
- 생성된 코드는 접두사 코드로서 디코딩 시 구분자 없이 연속된 비트열에서 각 기호를 식별할 수 있다.
- 허프만 트리 구축과 탐색 과정의 시간 복잡도는 기호의 개수를 n이라 할 때 O(n log n)이다.
- 허프만 부호화는 특정 확률 분포 하에서 평균 코드 길이를 최소화하는 최적의 접두사 코드를 생성하는 것으로 알려져 있다.
활용 분야
허프먼 부호화는 다양한 데이터 압축 시스템에서 널리 사용된다. ZIP, GZIP과 같은 파일 압축 알고리즘, JPEG 이미지 압축, MP3 오디오 압축의 엔트로피 부호화 단계, 그리고 일부 통신 프로토콜에서의 데이터 전송량 최적화 등에 적용된다. 또한 허프만 트리 구현은 많은 컴퓨터 과학 교과과정에서 자료 구조와 알고리즘 학습을 위한 표준적인 예제로 다루어진다.
한계
허프먼 부호화는 여러 가지 한계점도 지닌다. 가변 길이 코드로 인해 디코딩 과정이 고정 길이 코드에 비해 복잡할 수 있으며, 기호의 빈도 분포가 데이터에 따라 실시간으로 변하는 경우에는 동적으로 대응하기 어렵다. 또한 기호별 평균 코드 길이를 최소화하지만, 특정 상황에서는 다른 압축 기법(예: 산술 부호화)보다 압축률이 낮을 수 있다는 점도 지적된다.
참고 문헌
- Huffman, David A., "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the IRE, 1952.
- Cormen, Thomas H., et al., 《Introduction to Algorithms》, MIT Press, 2009.
