c++

[c++] Huffman Algorithm - 파일 압축 알고리즘

hojung 2022. 4. 28.

728x90

1. Huffman Algorithm이란?

우리가 흔히 파일을 네트워크를 통해 전송할 때 전송되는 파일의 정보 양을 줄이기 위해서 zip파일이라는 형식의 파일로 압축을 하여 보낸다.

현재 zip파일의 알고리즘 Deflate알고리즘이라는 것을 사용해서 파일을 압축하고 있지만 자세히 들여다보면 Deflate알고리즘이란 LZ77알고리즘과 Huffman Algorithm의 혼용이다.

나는 그 중 huffman algorithm을 c++로 구현해보았다.

컴퓨터 상의 정보는 0과 1두가지가 존재한다. 하지만 파일 안에 들어있는 내용들은 'a', 'b'와 같은 문자들이 들어있는데 컴퓨터는 다시 이 문자들을 아스키 코드라는 컴퓨터가 문자를 숫자로 표현하는 방식으로 바꿔서 알아듣는다.

따라서 우리는 문자를 어떠한 숫자로 표현하여 컴퓨터에게 알려주어야하고 이 숫자가 어떤 문자를 의미하는 지에 대해서도 컴퓨터에게 알려주어야한다.

huffman algorithm은 파일 안의 어떠한 문자를 어떤 0과1의 조합으로 표현할 지를 정해주는 알고리즘이다.

하지만 여기에는 크게 두 가지 고려해야할 사항이 존재한다.

많이 등장하는 문자의 경우 적은 비트수로 표현이 되어야한다.
하나의 문자를 표현한 0과 1의 조합은 다른 문자를 표현하는 0과 1의 조합의 접두사가 되면 안된다.

첫 번째의 경우를 보자

만약 하나의 파일 안에 a라는 문자가 10번 등장하고 b라는 문자가 100번등장한다고 하자.

그 때 a를 10(2bit) 으로 표현하기로 하고 b를 00000(5bit)이라고 표현하기로 하면 우리가 필요한 총 비트 수는

a를 표현하는 2bit * 10(a의 빈도수) + b를 표현하는 5bit * 100(b의 빈도수) = 520bit가 필요한 것을 알 수 있다.

하지만 더 많이 등장하는 b를 10으로 표현하고 적게 등장하는 a를 5bit로 표현한다면 우리가 필요한 총 비트 수는

a를 표현하는 5bit * 10(a의 빈도수) + b를 표현하는 2bit * 100(b의 빈도수) = 250bit

로 훨씬 줄어드는 것을 확인할 수 있다.

두 번째의 경우를 보자

컴퓨터는 GPU가 아닌 이상 순차적으로 프로세스를 처리한다. 즉 순서대로 읽는 다는 것이다. 그런데 a를 표현하는 1과 0의 조합이 10이고 b를 표현하는 1과 0의 조합이 100이라면 컴퓨터는 1과 0까지 읽었을 때 이 조합이 의미하는 것이 a인지 b인지 모르게 된다. 따라서 하나의 문자를 표현한 0과 1의 조합은 다른 문자를 표현하는 0과 1의 조합의 접두사가 되면 안되는 것이다.

2. 이론적 배경?

그렇다면 위의 두 가지를 고려하며 우리는 어떻게 문제를 해결할 수 있을 것인가

huffman이라는 사람은 놀라운 아이디어로 이 문제를 해결했다. 그림을 살펴보자

초기에 위 a와 같은 상태가 존재한다면 우리는 가장 빈도수가 적은 두 가지 문자를 꺼내어 빈도수를 합쳐준 후 다시 저장했던 자료구조(일반적으로 priority queue를 사용)로 push해준다. 이 작업을 하나의 노드 즉 root가 나타날 때까지 반복해주면 Tree형태의 자료구조가 생성된다.

위와 같은 Tree가 형성되었을 때 우리는 Tree의 가지의 왼쪽은 0 오른 쪽은 1로 설정해준다.

이런 식으로 말이다. 그럼 위의 Tree에서 A를 나타내는 코드는 00이되고 E를 나타내는 코드는 010 , F를 나타내는 코드는 011 B를 나타내는 코드는 100 D를 나타내는 코드는 1010 C를 나타내는 코드는 1011이 된다. 빈도순서대로 써보면 다음과 같다.

A 15번 00
B 12번 100
F 11번 011
E 10번 010
C 9번 1011
D 5번 1010

결과를 보면 앞서 언급했던 두 가지 조건을 모두 만족하는 것을 확인할 수 있다. 한 코드가 다른 코드의 접두사가 되지도 않고 더 적게 나온 문자가 더 적은 수의 비트로 encoding되지도 않는다.

그렇다면 어떻게 구현할까?

3. 구현

나는 txt파일을 읽은 후 그 txt파일의 문자의 수를 종류별로 센 후 huffman code로 변환해주는 프로그램을 만들것이다.

코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <fstream>
#include <string>
#include <unordered_map>
using namespace std;
struct huffmanNode {
    char a;
    int fre;
    huffmanNode* left;
    huffmanNode* right;
};

struct cmp {
    bool operator()(huffmanNode *a, huffmanNode *b) {
        return a->fre > b->fre;
    }
};


class HuffmanTree {
private: 
    huffmanNode* root = nullptr;
    unordered_map <char, int> ascii;
    unordered_map<char, string> code;
    priority_queue<huffmanNode*, vector<huffmanNode*>, cmp> pq;
    string text;
public:
    ~HuffmanTree() {
        releaseTree(root);
        root = nullptr;
        while (!pq.empty()) pq.pop();
    }

public:
    void Start() {
        ifstream file("test.txt");
        while (getline(file, text)) {
            cout << text << "\n";
            for (char a : text) {
                //ascii[a - 'a'] ++;
                /*ascii[a].fre++;
                ascii[a].a = a;*/
                ++ascii[a];
            }
        }
        //pq에 삽입
        for (const auto iter : ascii) {
            huffmanNode* newhuffman = new huffmanNode;
            newhuffman->left = nullptr;
            newhuffman->right = nullptr;
            newhuffman->a = iter.first;
            newhuffman->fre = iter.second;
            pq.push(newhuffman);
        }
        MakeTree();
        string tmp = "";
        FindTree(root, tmp);
    }
    void showCode() {
        for (auto it = code.begin(); it != code.end(); ++it)
        {
            cout << it->first << " : " << it->second << "\n";
        }
    }
private:
    void MakeTree() {
        int lim = pq.size() - 1;
        for (int i = 0; i < lim; i++) {
            huffmanNode* p = pq.top();
            pq.pop();
            huffmanNode* q = pq.top();
            pq.pop();
            huffmanNode* r = new huffmanNode;
            r->left = p;
            r->right = q;
            r->fre = p->fre + q->fre;
            r->a = 0;
            pq.push(r);
            cout << "Make Tree시작" << r->left->a << r->left->fre << " " << r->right->a << r->right->fre << "\n";
            cout << "r->a : " << r->a << "r=>fre : " << r->fre << "\n";
        }
        root = pq.top();
        cout << "top is" << root->a << " " << root->fre << "\n";
    }

    void FindTree(huffmanNode* p, string str) {
        if (p == nullptr) return;
        FindTree(p->left, str + '0');
        FindTree(p->right, str + '1');
        if (p->a != 0)
        {
            cout << str << "\n";
            //code map에 집어 넣기 
            code[p->a] = str;
        }
    }

    void releaseTree(huffmanNode* p)
    {
        if (p == nullptr) return;
        releaseTree(p->left);
        releaseTree(p->right);
        delete p;
        p = nullptr;
    }

    

};
int main() {

    HuffmanTree T;
    T.Start();
    T.showCode();
    return 0;
}

너무 길기 때문에 하나하나 살펴보겠다.

나는 Huffman code의 Class를 만들어서 진행했고 private 변수는

Tree의 root를 저장할 포인터

문자를 읽어들여 빈도수와 해당 문자를 저장할 unordered_map ascii

Tree를 이동하며 해당 문자에 대한 코드를 저장할 unordered_map code

내림차 순으로 huffmanNode를 정렬해줄 priority queue pq를 사용하였다.

1. Start()

public:
    void Start() {
        ifstream file("test.txt");
        while (getline(file, text)) {
            cout << text << "\n";
            for (char a : text) {
                //ascii[a - 'a'] ++;
                /*ascii[a].fre++;
                ascii[a].a = a;*/
                ++ascii[a];
            }
        }

우선 txt파일을 읽어드리는 부분이다. 나는 ifstream라이브러리를 추가한 후 ifstream 함수를 사용해서 파일을 읽었다.

그 후 for문을 돌며 ascii map에 빈도수와 문자를 저장해주었다.

2. PQ에 삽입

//pq에 삽입
        for (const auto iter : ascii) {
            huffmanNode* newhuffman = new huffmanNode;
            newhuffman->left = nullptr;
            newhuffman->right = nullptr;
            newhuffman->a = iter.first;
            newhuffman->fre = iter.second;
            pq.push(newhuffman);
        }

pq에 huffmanNode를 만들어 삽입하는 과정이다. left와 right는 nullptr인 상태로 두었고 huffmanNode의 문자는 ascii map이 first즉 문자 huffmanNode의 fre는 빈도 수로 ascii 배열의 second를 받아주었다.

3. MakeTree()

private:
    void MakeTree() {
        int lim = pq.size() - 1;
        for (int i = 0; i < lim; i++) {
            huffmanNode* p = pq.top();
            pq.pop();
            huffmanNode* q = pq.top();
            pq.pop();
            huffmanNode* r = new huffmanNode;
            r->left = p;
            r->right = q;
            r->fre = p->fre + q->fre;
            r->a = 0;
            pq.push(r);
            cout << "Make Tree시작" << r->left->a << r->left->fre << " " << r->right->a << r->right->fre << "\n";
            cout << "r->a : " << r->a << "r=>fre : " << r->fre << "\n";
        }
        root = pq.top();
        cout << "top is" << root->a << " " << root->fre << "\n";
    }

트리를 만드는 과정이다. 가장 작은 두 개의 node를 꺼낸 후 합치고 다시 priority queue에 넣어준다. 이렇게 되면 최종적으로는 root만 priority queue에 남게 되지만 이전 노드의 정보는 다 left와 right포인터에 남아있기 때문에 Tree형태의 구조로 탐색할 수 있다.

4. FindTree()

   void FindTree(huffmanNode* p, string str) {
        if (p == nullptr) return;
        FindTree(p->left, str + '0');
        FindTree(p->right, str + '1');
        if (p->a != 0)
        {
            cout << str << "\n";
            //code map에 집어 넣기 
            code[p->a] = str;
        }
    }

Tree를 탐색하는 과정이다. 앞서 빈도수를 합쳐 다시 priority queue에 삽입할 때 새로 만든 huffmanNode의 a는 0으로 설정해주었으므로 만일 포인터 p의 a가 0이 아니라면 이것은 우리가 삽입한 노드가 아니라 초기 상태에 priority queue에 존재하던 문자와 빈도수를 모두 갖는 huffmanNode를 의미한다. 이 노드를 만날 때까지 tree를 탐색하며 left면 0 right면 1을 붙여준다음 leaf노드들을 만나면 code map에 삽입해준다.

5. 소멸자

void releaseTree(huffmanNode* p)
    {
        if (p == nullptr) return;
        releaseTree(p->left);
        releaseTree(p->right);
        delete p;
        p = nullptr;
    }

소멸자에서는 우리가 동적으로 할당받았던 메모리들을 delete해준다.

위의 코드를 실행시키면 다음과 같이 나온다.

4. 결과

정상적으로 결과가 출력된다.