Huffman code

허프만 코드

허프만 코드는 데이터 압축을 위한 최적의 접두사 코드(prefixed code) 중 하나입니다. 허프만 코드는 빈도수를 기반으로 문자를 인코딩하여 가장 빈도가 높은 문자에는 짧은 코드를 할당하고, 낮은 빈도의 문자에는 긴 코드를 할당하는 방식으로 동작합니다.

허프만 코드 과정

1. 문자 빈도수 계산

• 입력 데이터에서 각 문자 또는 기호의 등장 빈도 수를 계산합니다.
• 빈도수 기반으로 허프만 트리 생성합니다.

2. 허프만 트리 구성

• 우선순위 큐를 통해 빈도수가 가장 낮은 두 문자를 선택해서 새로운 노드를 만들고 다시 우선 순위 큐에 넣습니다.
• 이 과정을 우선순위 큐에 1개의 tree만 남을 때까지 진행합니다.

3. 허프만 코드 할당

• 허프만 트리 기반으로 각 문자에 대한 허프만 코드를 할당합니다.
• 허프만 트리의 왼쪽 가지는 0, 오른쪽 가지는 1로 할당합니다.
• 트리의 루트부터 리프 노드까지 따라가며 인코딩을 진행합니다.

예제

등장 빈도수

"A" | 3
"B" | 2
"C" | 1
"D" | 1

C(1) D(1) B(2) A(3)

...

A: 0
B: 10
C: 110
D: 111

압축 전 & 후

압축 전: ACADABCA
압축 후: 01100010111100010

Pseudo code

HuffmanCoding(frequencies):
    queue = CreateQueue()
    for each symbol in frequencies:
        node = CreateNode(symbol, frequencies[symbol])
        Enqueue(queue, node)
    
    while Size(queue) > 1:
        node1 = Dequeue(queue)
        node2 = Dequeue(queue)
        mergedNode = MergeNodes(node1, node2)
        Enqueue(queue, mergedNode)
    
    root = Dequeue(queue)
    huffmanTree = CreateTree(root)
    codes = GenerateCodes(huffmanTree)
    return codes

GenerateCodes(tree):
    codes = empty dictionary
    traverse(tree.root, "", codes)
    return codes

traverse(node, currentCode, codes):
    if node is leaf node:
        codes[node.symbol] = currentCode
    else:
        traverse(node.left, currentCode + "0", codes)
        traverse(node.right, currentCode + "1", codes)

C++ 코드로 구현

#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

// Huffman 노드 정의
struct HuffmanNode {
    char symbol;
    int frequency;
    HuffmanNode* left;
    HuffmanNode* right;

    HuffmanNode(char symbol, int frequency) {
        this->symbol = symbol;
        this->frequency = frequency;
        left = nullptr;
        right = nullptr;
    }
};

// 노드 비교를 위한 비교자 클래스
struct CompareNodes {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->frequency > b->frequency;
    }
};

// 허프만 코드 생성 함수
unordered_map<char, string> GenerateHuffmanCodes(unordered_map<char, int>& frequencies) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareNodes> minHeap;

    // 빈도수를 기반으로 허프만 노드 생성 및 우선순위 큐에 삽입
    for (auto& pair : frequencies) {
        HuffmanNode* node = new HuffmanNode(pair.first, pair.second);
        minHeap.push(node);
    }

    // 우선순위 큐에서 노드를 꺼내면서 허프만 트리 생성
    while (minHeap.size() > 1) {
        HuffmanNode* left = minHeap.top();
        minHeap.pop();
        HuffmanNode* right = minHeap.top();
        minHeap.pop();

        // 새로운 노드 생성 및 연결
        HuffmanNode* mergedNode = new HuffmanNode('\0', left->frequency + right->frequency);
        mergedNode->left = left;
        mergedNode->right = right;

        minHeap.push(mergedNode);
    }

    // 허프만 트리의 루트 노드
    HuffmanNode* root = minHeap.top();

    // 허프만 코드 생성
    unordered_map<char, string> huffmanCodes;
    GenerateCodes(root, "", huffmanCodes);

    // 메모리 해제
    DeleteTree(root);

    return huffmanCodes;
}

// 허프만 트리를 기반으로 허프만 코드 생성
void GenerateCodes(HuffmanNode* node, string code, unordered_map<char, string>& huffmanCodes) {
    if (node == nullptr)
        return;

    // 리프 노드인 경우 코드 할당
    if (node->left == nullptr && node->right == nullptr)
        huffmanCodes[node->symbol] = code;

    GenerateCodes(node->left, code + "0", huffmanCodes);
    GenerateCodes(node->right, code + "1", huffmanCodes);
}

// 허프만 트리 메모리 해제 함수
void DeleteTree(HuffmanNode* node) {
    if (node == nullptr)
        return;

    DeleteTree(node->left);
    DeleteTree(node->right);
    delete node;
}

int main() {
    // 문자 빈도수
    unordered_map<char, int> frequencies = {
        {'A', 3},
        {'B', 2},
        {'C', 1},
        {'D', 1}
    };

    // 허프만 코드 생성
    unordered_map<char, string> huffmanCodes = GenerateHuffmanCodes(frequencies);

    // 결과 출력
    for (auto& pair : huffmanCodes) {
        cout << "Symbol: " << pair.first << ", Code: " << pair.second << endl;
    }

    return 0;
}