11. 허프만 코딩 (Huffman Coding, c++) - Greedy, Compression
허프만 코딩 (Huffman Coding)?
Huffman Coding은 무손실 데이터 압축 알고리즘으로, 주어진 string을 압축하기 위한 최적의 codeword를 그리디 알고리즘을 이용해서 만들어 냅니다.
자주 사용되는 문자가 더 짧은 codeword를 갖도록 구현됩니다.
이렇게 생성된 binary codeword는 다음 특징을 갖습니다.
1) 문자에 대한 binary codeword는 다른 문자의 prefix가 될 수 없습니다. 이를 통해 구분자(seperator)없이도 encoding, decoding을 수행할 수 있습니다.
2) 주어진 string에서의 문자 등장빈도 기반으로 구성하기 때문에 encoding 문자열의 길이가 최적화 됩니다. 자주 등장하는 문자가 짧은 codeword를 갖습니다.
Implementation
각 문자의 등장빈도를 기반으로 이진 트리를 구성하고, 각 문자의 codeword는 root에서부터 왼쪽으로 내려가면 0, 오른쪽으로 가면 1을 부여하면서 리프노드로 가는 경로가 그 문자의 codeword가 되는 형태입니다.
BANANA 라는 string에서 A는 3번, N은 2번, B는 1번 등장합니다.
이 문자열의 최종적인 트리의 형태는 다음과 같습니다.
문자의 codeword는 아래와 같습니다.
A : 0
B : 10
N : 11
BANANA -> 100110110 와 같이 encoding 하게 되면 9bit로 string을 표현할 수 있게 됩니다.
다음은 c++에서의 구현 방법입니다.
string을 입력 받아서 codeword 를 구하고 encoding/decoding 작업을 수행합니다.
1) unordered_map<char, int> 을 생성하고 string에서 각 문자열이 얼마나 등장하는지(frequency)를 세어줍니다.
2) Huffman Tree에서 각 노드를 나타낼 struct를 정의합니다. 문자열과 빈도수 그리고 left, right 노드에 대한 pointer를 갖습니다.
3) 우선순위 큐(frequency 오름차순)에 초기 값으로 string을 구성하는 모든 문자열을 추가합니다.
이후, 가장 빈도수가 작은 노드 두개를 뽑아 각각을 left와 right로 가지는 새로운 내부노드를 생성합니다.
이 작업은 우선순위 큐에 root 노드만 남을 때 까지 반복합니다.
4) generate() 재귀 함수로 Huffman codeword map을 생성합니다. unordered_map<char, string> 으로 해당 문자열에 대한 codeword를 저장합니다.
이 작업은 root로부터 시작해서 재귀적으로 리프노드까지 탐색을 합니다.
left로 가는 경우 codeword에 0을 추가하고, right로 가는경우 1을 추가합니다.
리프노드는 left와 right에 대한 포인터가 없는 경우입니다.
5) print() 함수로 codeword map을 출력합니다.
6) encode() 함수로 주어진 string을 encoding 합니다.
encoding은 각 문자열에 대해 map에서 일치하는 코드로 변경합니다.
7) decode() 함수로 encoding 된 문자열을 decodiing 합니다.
decoding은 문자열의 맨 앞부터 탐색합니다. root 부터 시작해서 0이 나오면 left로 1이 나오면 right로 이동합니다.
이동하였을 때 리프노드인 경우 해당 문자열로 변경하고 다음 문자열은 다시 root부터 동일한 작업을 수행합니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
char c;
int freq;
Node* left;
Node* right;
Node(char c, int freq)
: c(c)
, freq(freq)
, left(nullptr)
, right(nullptr)
{}
Node(char c, int freq, Node* left, Node* right)
: c(c)
, freq(freq)
, left(left)
, right(right)
{}
};
struct compare {
bool operator() (Node* a, Node* b) {
return a->freq > b->freq;
}
};
int print(unordered_map<char, string> &huffmanCode) {
for (auto x: huffmanCode) {
cout << x.first << " " << x.second << "\n";
}
return 0;
}
string encode(string s, unordered_map<char, string> &huffmanCode) {
string encoded = "";
for (auto c: s) {
encoded += huffmanCode[c];
}
cout << "Encoded string : " << encoded << "\n";
return encoded;
}
int decode(string e, Node* root) {
string decoded = "";
Node* cur = root;
for (auto b: e) {
if (b == '0') cur = cur->left;
else cur = cur->right;
if (!cur->left && !cur->right) {
decoded += cur->c;
cur = root;
}
}
cout << "Decoded string : " << decoded << "\n";
return 0;
}
int generate(Node* node, unordered_map<char, string> &huffmanCode, string codeword) {
if (node == nullptr) return 0;
if (!node->left && !node->right) {
huffmanCode[node->c] = codeword;
return 0;
}
generate(node->left, huffmanCode, codeword+"0");
generate(node->right, huffmanCode, codeword+"1");
return 0;
}
int solve(string s) {
unordered_map<char, int> freq;
for (auto c: s) {
freq[c]++;
}
priority_queue<Node*, vector<Node*>, compare> pq;
for (auto x: freq) {
pq.push(new Node(x.first, x.second));
}
while (pq.size() != 1) {
Node* left = pq.top();
pq.pop();
Node* right = pq.top();
pq.pop();
pq.push(new Node('\0', left->freq+right->freq, left, right));
}
Node* root = pq.top();
unordered_map<char, string> huffmanCode;
generate(root, huffmanCode, "");
print(huffmanCode);
string encoded = encode(s, huffmanCode);
decode(encoded, root);
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
solve(s);
return 0;
}
// output
N 11
A 0
B 10
Encoded string : 100110110
Decoded string : BANANA