12. 정규 허프만 코딩 (Canonical Huffman Coding, c++) - Greedy Algorithms

정규 허프만 코딩 (Canonical Huffman Coding)?

허프만 코딩은 그리디 알고리즘을 이용해 자주 이용되는 문자는 짧은 코드를 가지고, 덜 이용되는 문자는 긴 코드를 가지는 효율적인 압축 알고리즘입니다.

 

2025.02.21 - [Competitive Programming] - 11. 허프만 코딩 (Huffman Coding, c++) - Greedy Algorithms

11. 허프만 코딩 (Huffman Coding, c++) - Greedy, Compression

 

이 것을 이용한 encoding은 매우 쉽고 효율적인데, decoding은 효율적이지만은 않습니다.

 

왜냐하면 decoding을 할 때에 encoding 문자열을 원본 문자열로 되돌리기 위해 encoding 정보에 대한 이해가 필요합니다.

 

그러므로 전송 시에 encoding 정보가 문자와 코드에 대한 table 형태로 전달되어야 합니다.

 

따라서 용량이 커질 수록 더 많은 메모리 공간을 차지하게 되며, decoding 과정을 효율적으로 개선하기 위해 Canonical Huffman Code가 소개되었습니다.

---

Canonical Huffman Code는 각 문자열에 대해 일반적인 Huffman Code에서 생성된 Bit 문자열의 길이를 사용합니다.

 

아래 과정에 따라 Canonical Huffman Code가 생성됩니다.

 

생성된 Huffman Code는 Decoder가 Encoding 문자, 코드에 대한 모든 정보 없이, 문자열과 길이 정보만으로 Huffman Tree를 재구성 할 수 있게 합니다. 데이터 전송, decoding에 드는 비용이 감소합니다. 

 

1. 일반적인 Huffman Code bit 길이 오름차순으로 정렬합니다.

 

2. 첫번째 문자열은 bit 길이 만큼의 0 으로 이루어집니다.

 

3. 그 다음 문자열 부터는 이전 문자열의 길이와 같다면 정수 1을 증가 시킵니다.

 

4. 이전 문자열의 길이와 다르다면 정수 1을 증가시킨 문자열에 bit 길이차이만큼의 0을 추가합니다.

 

다음은 APPLEBANANA 문자열을 예시로 사용합니다.

 

일반 Huffman Code

문자열	코드	길이
P	01	2
A	11	2
L	000	3
E	001	3
B	100	3
N	101	3

 

Canonical Huffman Code

문자열	코드	길이
P	00	2
A	01	2
L	100	3
E	101	3
B	110	3
N	111	3

 

다음은 c++에서의 구현 방법입니다.

 

1) 일반적인 Huffman Code와 동일하게 Huffman Tree Node를 구성합니다.

 

2) map<int, set<char>>에 bit 길이에 해당하는 문자열들을 저장합니다.

 

3) 짧은 문자열부터 새로운 code를 생성합니다.

 

4) 첫 문자열은 bit 길이만큼 0으로 채운 문자열입니다.

 

5) 문자열의 길이가 같다면 정수 1씩 증가 시킵니다.

 

6) 문자열의 길이가 변경되면 정수 1 증가 후 길이 차이만큼을 0으로 채웁니다. 

 

#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 calculate(Node* node, map<int, set<char>>& data, int length) {
    if (node == nullptr) return 0;
    if (!node->left && !node->right) {
        data[length].insert(node->c);
        return 0;
    }
    calculate(node->left, data, length+1);
    calculate(node->right, data, length+1);
    return 0;
}

int generate(map<int, set<char>>& data, unordered_map<char, pair<int, int>>& canonicalHuffmanCode) {
    int prevLen = 0, curLen = 0, code = 0;
    for (auto it = data.begin(); it != data.end(); it++) {
        set<char> s = it->second;
        curLen += (it->first - prevLen);
        code = (code) << (it->first - prevLen);
        for (auto c = s.begin(); c != s.end(); c++) {
            cout << *c << " : " << bitset<32>(code).to_string().substr(32 - curLen, 32) << "\n";
            canonicalHuffmanCode[*c] = {curLen, code};
            code += 1;
        }
        prevLen = it->first;
    }
    for (auto x: canonicalHuffmanCode) {
        cout << x.first << ". length : " << x.second.first << ", code : " << x.second.second << "\n";
    }
    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();
    map<int, set<char>> data;
    calculate(root, data, 0);
    unordered_map<char, pair<int, int>> canonicalHuffmanCode;
    generate(data, canonicalHuffmanCode);
    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    solve(s);
    return 0;
}
// output
A : 00
P : 01
B : 100
E : 101
L : 110
N : 111
N. length : 3, code : 7
B. length : 3, code : 4
A. length : 2, code : 0
L. length : 3, code : 6
P. length : 2, code : 1
E. length : 3, code : 5