알고리즘 : 허프만 인코딩

텍스트 혹은 여러가지 파일에는 중복된 데이터가 있기 마련입니다.

이러한 중복된 데이터를 압축하여 공간을 절약하는 것이 화일 압축 알고리즘이라고 하는데,

여러분이 자주 사용하시는 알집 혹은 반디집과 같은 압축 프로그램에 쓰이는 알고리즘입니다.

이번 시간에는 이런 화일 압축 알고리즘에 쓰이는 허프만 인코딩에 대해 소개하려 합니다.

---

트라이(trie)

---

 

"AAAAABBCDE"

다음과 같이 다섯개의 문자가 등장하는 텍스트 파일이 있습니다.

A를 0, B를 1, C를 10, D를 11, E를 101로 변환하고 표로 나타내면 아래와 같습니다.

변환된 코드로 텍스트 파일을 변경(디코드, decode)하면 다음과 같죠.

"00000111011101"

이렇게 빈도수에 따라 적고 많은 비트를 사용하여 인코딩하는 기법을 가변 길이 인코딩이라고 합니다.

그런데, 이 코드를 텍스트로 변경하는 과정에서 0000011까지는 AAAAABB로 변환이 되지만, 다음 10을 맞닥뜨릴 때 1과 0을 따로 읽어서 C가 아닌 BA로 변환될 위험이 존재합니다.

이러한 현상을 막기 위해 다음과 같이 코드를 부여해 보도록 하겠습니다.

이렇게 코드를 부여하게 되면, 디코드 하는 과정에서 110이 나타나도 1 혹은 11을 부여받은 문자가 없기 때문에 정상적으로 C를 얻을 수 있습니다.

이렇게 하나의 문자 코드가 다른 문자 코드의 접두부가 되지 않는 자료구조를 트라이 라고 합니다.

그런데 이렇게 트라이를 구성하게 되면, 그렇게 좋지 않은 구조를 갖게 됩니다.

이와 달리 다음 코드를 부여하고 트라이를 그려보겠습니다.

아까의 트라이보다 훨씬 층계가 줄어든 모습을 볼 수 있습니다.

이렇게 보다 효율적인 트라이를 결정하는 기법이 허프만 인코딩입니다.

---

허프만 인코딩

---

허프만 인코딩은 우선순위 큐(Priority Queue)를 사용합니다. 빈도수로 트라이의 형태를 결정하기 위해 데이터와 빈도수 두 정보를 모두 담아야 하기 때문이죠.

 

다음과 같은 정보가 주어졌다고 합시다.

일단 이 데이터를 모두 우선순위 큐(PQ)에 대충 담습니다.

여기서 제일 적은 빈도수를 가진 값 두 개를 빼오고(p, q를 선정) 루트 노드로 쓸 새 노드(new node r)를 만듭니다.

p, q를 r의 자식 노드가 되도록 위치를 잡아줍니다. (r->left = p; r->right = q;)

이 때, 새 노드 r의 값은 방금 빼낸 두 노드의 값을 합친 만큼입니다. (r->freq = p->freq + q->freq;)

이제 p, q를 뺀 자리에 새 노드인 r을 집어넣어 주면 다음과 같은 형식의 데이터가 만들어집니다.

상기한 과정을 계속 반복 해보겠습니다.

PQ의 특성 상 우선순위를 두어 정렬하게 되므로, A 노드가 r의 왼쪽으로 가게 됩니다.

이전 단계를 그릴 땐 미처 생각을 못했던 점입니다..ㅜ

최종적으로 다음의 형태가 됩니다.

빈도수가 높을 수록 루트 노드와 가깝고, 낮을 수록 루트 노드와 먼 밑쪽에 위치하게 됩니다.

 

허프만 인코딩의 코드는 다음과 같습니다.

다만 본 코드는 제가 작성한 것이 아닌 수업시간에 사용한 것이기에 추후에 제 식대로 수정해보도록 하겠습니다.

#include <iostream>
#include <queue>
#include <string>

using namespace std;

// 최대 크기 지정
#define MAX_SIZE 100

class HuffmanTreeNode {
public:
    string data;
    int freq;
    HuffmanTreeNode* left;
    HuffmanTreeNode* right;

    // 현재 노드 초기화
    HuffmanTreeNode(string character, int frequency) {
        data = character;
        freq = frequency;
        left = right = NULL;
    }
};

// 우선순위 큐는 우선순위가 높은 값이 먼저 나오기 때문에
// 빈도수 비교를 위한 클래스 생성
class Compare {
public:
    bool operator()(HuffmanTreeNode* a, HuffmanTreeNode* b) {
        // 빈도수 비교해서 우선순위 결과 반환
        return a->freq > b->freq;
    }
};

HuffmanTreeNode* generateTree(priority_queue<HuffmanTreeNode*, vector<HuffmanTreeNode*>, Compare> pq) {
    // 우선순위 큐 내부에 마지막 노드만 남을 때까지 반복
    while (pq.size() != 1) {
        // 왼쪽에서 빈도수가 가장 작은 노드
        HuffmanTreeNode* left = pq.top();

        // 큐에서 제거
        pq.pop();

        // 오른쪽에서 빈도수가 가장 작은 노드
        HuffmanTreeNode* right = pq.top();

        // 큐에서 제거
        pq.pop();

        // 왼쪽 노드 빈도수와 오른쪽 노드 빈도수를 합하여 
        // 특정 문자열의 빈도수로 저장
        HuffmanTreeNode* node = new HuffmanTreeNode("$", left->freq + right->freq);
        node->left = left;
        node->right = right;

        // 기존의 우선순위 큐에 새로 생성한 노드 삽입
        pq.push(node);
    }

    return pq.top();
}

// 허프만 트리 출력
void printCodes(HuffmanTreeNode* root, int arr[], int top) {
    // 왼쪽 노드에는 0을 할당
    if (root->left) {
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }

    // 오른쪽 노드에는 1을 할당
    if (root->right) {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }

    // leaf 노드까지 값이 할당되었으면 출력 시작
    if (!root->left && !root->right) {
        cout << root->data << " ";
        for (int i = 0; i < top; i++) {
            cout << arr[i];
        }
        cout << endl;
    }
}

void HuffmanCodes(string data[], int freq[], int size) {
    // 우선순위 큐 객체 선언
    priority_queue<HuffmanTreeNode*, vector<HuffmanTreeNode*>, Compare> pq;

    // 데이터 삽입
    // 빈도수가 높은 순으로 정렬되어서 들어가짐
    for (int i = 0; i < size; i++) {
        HuffmanTreeNode* newNode = new HuffmanTreeNode(data[i], freq[i]);
        pq.push(newNode);
    }

    // 허프만 트리 생성
    HuffmanTreeNode* root = generateTree(pq);

    // 출력
    int arr[MAX_SIZE], top = 0;
    printCodes(root, arr, top);
}

int main() {
    string data[] = { " ", "A", "B", "C", "D", "E", "F" };
    int freq[] = { 27, 15, 12, 9, 5, 10, 11 };
    int size = sizeof(data) / sizeof(data[0]);

    HuffmanCodes(data, freq, size);

    return 0;
}