허프만 코딩이란?
허프만 코딩(Huffman Coding)은 대표적인 무손실 데이터 압축(lossless data compression) 알고리즘입니다. 이 알고리즘은 입력 문자열의 각 문자에 가변 길이 코드(variable-length code)를 부여하는 방식으로 동작하며, 코드의 길이는 해당 문자가 사용되는 빈도에 따라 결정됩니다.
핵심 원리는 간단합니다. 자주 등장하는 문자에는 짧은 코드를, 드물게 등장하는 문자에는 긴 코드를 할당함으로써 전체 데이터의 크기를 효율적으로 줄일 수 있습니다.
허프만 코딩은 크게 두 단계로 구성됩니다.
- 1단계: 문자 빈도수를 기반으로 허프만 트리(Huffman Tree) 생성
- 2단계: 생성된 트리를 순회(traverse)하며 각 문자의 코드 추출
예시로 이해하기
문자열 "YYYZXXYYX"을 예로 들어 보겠습니다. 문자 Y의 빈도수가 X보다 높고, Z의 빈도수가 가장 낮습니다. 따라서 Y에 부여되는 코드 길이는 X보다 짧고, X의 코드 길이는 Z보다 짧아집니다.
각 문자의 빈도수에 따라 코드를 할당하는 과정의 시간 복잡도는 O(n log n)입니다. 이는 우선순위 큐(priority queue)를 사용해 최소 빈도 노드를 반복적으로 추출하고 병합하기 때문입니다.
알고리즘 동작 방식
입력 및 출력 예제
입력 − 다양한 문자를 포함한 문자열, 예: "ACCEBFFFFAAXXBLKE"
출력 − 각 문자별 할당된 코드:
Data: K, Frequency: 1, Code: 0000
Data: L, Frequency: 1, Code: 0001
Data: E, Frequency: 2, Code: 001
Data: F, Frequency: 4, Code: 01
Data: B, Frequency: 2, Code: 100
Data: C, Frequency: 2, Code: 101
Data: X, Frequency: 2, Code: 110
Data: A, Frequency: 3, Code: 111
결과에서 확인할 수 있듯이, 빈도수가 4로 가장 높은 F는 2비트의 짧은 코드 "01"을 받았고, 빈도수가 1인 K와 L은 4비트의 긴 코드를 받았습니다.
알고리즘 의사코드(Pseudocode)
huffmanCoding(string)
입력 − 다양한 문자를 포함한 문자열
출력 − 각 개별 문자에 할당된 코드
Begin
허프만 트리용 노드를 정의 (문자, 빈도수, 왼쪽 자식, 오른쪽 자식)
각 문자의 빈도수를 저장할 리스트 'freq'를 생성하고 모두 0으로 초기화
문자열의 각 문자 c에 대해:
freq 리스트에서 해당 문자의 빈도수 증가
done
모든 종류의 문자 ch에 대해:
ch의 빈도수가 0이 아니면 ch와 빈도수를 노드로 만들어 우선순위 큐 Q에 삽입
done
Q가 비어있지 않은 동안:
Q에서 항목을 제거하여 노드의 왼쪽 자식으로 지정
Q에서 항목을 제거하여 노드의 오른쪽 자식으로 지정
노드를 순회하며 할당된 코드 탐색
done
End
traverseNode(n: node, code)
입력 − 허프만 트리의 노드 n과 이전 호출에서 전달된 코드
출력 − 각 문자에 할당된 코드
if 노드 n의 왼쪽 자식 ≠ φ then
traverseNode(왼쪽 자식(n), code+'0') // 왼쪽 자식으로 순회
traverseNode(오른쪽 자식(n), code+'1') // 오른쪽 자식으로 순회
else
현재 노드의 문자와 데이터 출력
C++ 구현 예제
아래는 위 알고리즘을 C++로 구현한 전체 코드입니다. STL의 priority_queue를 활용해 효율적으로 구현했습니다.
#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct node{
int freq;
char data;
const node *child0, *child1;
node(char d, int f = -1){ //노드에 값 할당
data = d;
freq = f;
child0 = NULL;
child1 = NULL;
}
node(const node *c0, const node *c1){
data = 0;
freq = c0->freq + c1->freq;
child0=c0;
child1=c1;
}
bool operator<( const node &a ) const { //< 연산자로 큐의 우선순위 결정
return freq >a.freq;
}
void traverse(string code = "")const{
if(child0!=NULL){
child0->traverse(code+'0'); //왼쪽 자식이므로 코드에 0 추가
child1->traverse(code+'1'); //오른쪽 자식이므로 코드에 1 추가
}else{
cout << "Data: " << data<< ", Frequency: "<<freq << ", Code: " << code<<endl;
}
}
};
void huffmanCoding(string str){
priority_queue<node> qu;
int frequency[256];
for(int i = 0; i<256; i++)
frequency[i] = 0; //모든 빈도수 초기화
for(int i = 0; i<str.size(); i++){
frequency[int(str[i])]++; //빈도수 증가
}
for(int i = 0; i<256; i++){
if(frequency[i]){
qu.push(node(i, frequency[i]));
}
}
while(qu.size() >1){
node *c0 = new node(qu.top()); //왼쪽 자식 추출 후 큐에서 제거
qu.pop();
node *c1 = new node(qu.top()); //오른쪽 자식 추출 후 큐에서 제거
qu.pop();
qu.push(node(c0, c1)); //두 자식의 빈도수를 합산해 다시 큐에 삽입
}
cout << "The Huffman Code: "<<endl;
qu.top().traverse(); //트리를 순회하며 코드 획득
}
main(){
string str = "ACCEBFFFFAAXXBLKE"; //빈도수 계산용 임의 문자열
huffmanCoding(str);
}
실행 결과
The Huffman Code:
Data: K, Frequency: 1, Code: 0000
Data: L, Frequency: 1, Code: 0001
Data: E, Frequency: 2, Code: 001
Data: F, Frequency: 4, Code: 01
Data: B, Frequency: 2, Code: 100
Data: C, Frequency: 2, Code: 101
Data: X, Frequency: 2, Code: 110
Data: A, Frequency: 3, Code: 111
정리
허프만 코딩은 그리디(Greedy) 기법에 기반한 최적 접두사 코드(optimal prefix code) 알고리즘으로, ZIP, JPEG, MP3 등 실제 압축 포맷의 핵심 요소로 널리 활용됩니다. 어느 코드도 다른 코드의 접두사가 되지 않기 때문에 디코딩 시 모호함 없이 원본 데이터를 완벽하게 복원할 수 있다는 점이 가장 큰 장점입니다.