허프만 코딩(Huffman Coding)이란?
허프만 코딩은 대표적인 비손실(lossless) 데이터 압축 알고리즘입니다. 이 알고리즘은 입력되는 각 문자에 서로 다른 길이의 가변 길이 코드(variable-length code)를 부여하며, 코드의 길이는 해당 문자가 사용되는 빈도에 따라 결정됩니다.
핵심 원리는 간단합니다. 자주 등장하는 문자에는 짧은 코드를, 드물게 등장하는 문자에는 긴 코드를 할당함으로써 전체 데이터의 크기를 줄이는 것입니다.
허프만 코딩은 크게 두 단계로 나눌 수 있습니다.
- 1단계: 허프만 트리(Huffman Tree)를 생성하는 단계
- 2단계: 생성된 트리를 순회(traverse)하며 각 문자의 코드를 찾아내는 단계
예를 들어 문자열 "YYYZXXYYX"를 살펴보겠습니다. 문자 Y의 등장 빈도가 X보다 높고, Z는 가장 낮은 빈도를 가집니다. 따라서 Y에 할당되는 코드의 길이가 X보다 짧고, X의 코드 길이는 Z보다 짧아집니다.
각 문자의 빈도에 따라 코드를 할당하는 과정의 시간 복잡도는 O(n log n)입니다.
입력 및 출력 예시
입력:
서로 다른 문자로 구성된 문자열, 예: "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
위 결과를 보면 빈도가 가장 높은 F(4회)는 2비트의 짧은 코드를, 빈도가 가장 낮은 K와 L(각 1회)은 4비트의 긴 코드를 받는 것을 확인할 수 있습니다.
알고리즘
1. huffmanCoding(string)
입력: 서로 다른 문자들로 구성된 문자열
출력: 각 문자에 할당된 코드
Begin
허프만 트리를 위한 노드를 정의한다.
(노드는 문자, 빈도, 왼쪽 자식, 오른쪽 자식을 가진다)
각 문자의 빈도를 저장할 리스트 'freq'를 생성하고,
모든 값을 0으로 초기화한다.
문자열의 각 문자 c에 대해:
freq 리스트에서 해당 문자의 빈도를 1 증가시킨다.
done
모든 종류의 문자 ch에 대해:
ch의 빈도가 0이 아니라면,
ch와 그 빈도를 하나의 노드로 만들어 우선순위 큐 Q에 삽입한다.
done
Q가 빌 때까지 반복:
Q에서 항목을 제거하여 노드의 왼쪽 자식으로 지정한다.
Q에서 항목을 제거하여 노드의 오른쪽 자식으로 지정한다.
노드를 순회하며 할당된 코드를 찾는다.
done
End
2. traverseNode(n: 노드, code)
입력: 허프만 트리의 노드 n과, 이전 호출에서 전달받은 코드
출력: 각 문자에 할당된 최종 코드
if 노드 n의 왼쪽 자식 ≠ φ then
traverseNode(leftChild(n), code+'0') // 왼쪽 자식을 따라 순회
traverseNode(rightChild(n), code+'1') // 오른쪽 자식을 따라 순회
else
현재 노드의 문자와 데이터를 출력한다.
즉, 트리를 순회할 때 왼쪽으로 내려가면 코드에 '0'을 추가하고, 오른쪽으로 내려가면 '1'을 추가합니다. 리프 노드(자식이 없는 노드)에 도달하면 그 문자의 코드가 완성됩니다.
C++ 구현 예제
#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; // 모든 빈도를 0으로 초기화
for(int i = 0; i < str.size(); i++)
frequency[(unsigned char)str[i]]++; // 문자별 빈도 계산
for(int i = 0; i < 256; i++) {
if(frequency[i] > 0)
qu.push(node(i, frequency[i])); // 빈도가 0이 아닌 문자를 큐에 삽입
}
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(); // 완성된 트리를 순회하며 코드 출력
}
int main() {
string str = "ACCEBFFFFAAXXBLKE";
huffmanCoding(str);
return 0;
}
실행 결과
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
마무리
허프만 코딩은 우선순위 큐(최소 힙)를 활용해 빈도가 낮은 노드부터 차례대로 병합하여 트리를 만드는 것이 핵심입니다. 이렇게 만들어진 트리에서 왼쪽 간선은 0, 오른쪽 간선은 1에 대응되므로, 어떤 문자든 다른 문자의 코드 접두사가 되지 않는 접두사 코드(prefix code) 특성을 가지게 됩니다. 덕분에 디코딩 시 모호함 없이 원본 데이터를 정확히 복원할 수 있으며, ZIP, JPEG, MP3 등 실제 압축 기술의 기반으로 널리 사용됩니다.