본문 바로가기
Data Structure & Algorithm/알고리즘

허프만 코딩 (C++ 구현)

by 별준 2021. 8. 5.

References

  • 리얼월드 알고리즘

허프만 코딩

허프만 코드는 (최소)우선순위 큐와 이진 트리로 만들 수 있는 유일 접두어 코드를 의미합니다.

1951년 데이비드 허프만(David A. Huffman)이 25살 때 고안한 방법으로, 허프만 코딩은 기호들의 빈도를 활용하여 정보를 압축하는 무손실 압축 시스템입니다.

 

허프만 코딩은 우선순위 큐로 인코딩을 시작하며, 큐의 원소는 이진 트리입니다. 이 이진 트리의 리프노드들은 문자와 텍스트에서 그 문자의 빈도를 가지고 있습니다.

 

그럼 어떻게 허프만 코드로 변환이 되는지 단어 'effective'를 통해서 살펴보겠습니다.

인코딩 과정

허프만 코딩은 먼저 각 문자의 빈도를 측정하고, 문자와 빈도를 데이터로 갖는 이진 트리를 원소로 갖는 우선순위 큐로 시작합니다. 아래 첫번째 행이 바로 우선순위 큐에서의 원소들을 의미합니다.

인코딩 첫번째 과정

첫번째 과정에서는 우선순위 큐에서 최소 원소를 두 번 취합니다. 이들은 문자 C와 V에 대한 최소 빈도를 갖는 두 개의 단일 노드 트리입니다. 그리고 우선순위 큐에서 꺼내 온 두 개의 트리를 자식으로 하는 새로운 루트 노드의 이진 트리를 생성합니다. 새로운 트리의 루트는 문자 C와 V의 빈도 합을 빈도로 가지며, 문자 값은 가지지 않습니다. 그리고 이렇게 새롭게 생성된 이진 트리를 다시 큐에 삽입합니다.

인코딩 두번째 과정

새롭게 만든 이진 트리를 우선순위 큐에 삽입하고 나면, 다시 최소 원소 두 개를 꺼내고 위 과정을 반복합니다. 따라서, 문자 I와 T를 갖는 두 개의 이진 트리를 꺼내고, 꺼낸 이진 트리들을 자식 노드로 갖는 루트 노드를 새롭게 생성하고 다시 큐에 삽입합니다.

 

나머지 과정도 우선순위 큐에 원소의 개수가 하나가 될 때까지 위의 작업을 반복 수행합니다.

 

세번째 과정

인코딩 세번째 과정

네번째 과정

인코딩 네번째 과정

다섯번째 과정

인코딩 다섯번째 과정

 

우선순위 큐의 원소가 하나가 될 때까지 위 과정을 반복하면, 최종적으로 허프만 코드를 명시하는 하나의 이진트리를 갖게 되고, 큐에서 이 트리를 꺼내 반환하면 됩니다.

 

아래 그림은 우선순위 큐에서 최종 반환되는 이진 트리입니다. 문자를 인코딩하기 위한 각 문자의 허프만 코드를 나타냅니다.

각 문자의 허프만 코드를 나타낸다.

이 이진트리를 가지고 이제 문자의 인코딩을 시작해봅시다. 각 문자의 인코딩을 찾으려면 이진트리의 루트에서 시작하여 문자에 해당하는 리프 노드에 도달할 때까지 트리를 탐색합니다. 왼쪽으로 탐색할 때마다 인코딩에 0을, 오른쪽으로 탐색할 때마다 1을 넣습니다. 결과 비트열은 문자의 허프만 인코딩이 됩니다. 

위 예시에서 F는 00, C는 010, V는 011, I는 100, T는 101, E는 11이 됩니다.

 

위 인코딩 과정을 거치면 effective는 1100001101010110001111 으로 변환됩니다.

허프만 인코딩을 사용하여 문자열을 인코딩하려면 위에서 본 것처럼 문자열을 두 번 전달해야 하므로 2Pass 인코딩이 됩니다. 처음에는 허프만 코드를 구성하기 위해서 문자 빈도를 측정하고, 그다음에 다시 문자열을 전달하여 각 문자를 허프만 코드로 인코딩합니다. 인코딩 결과는 압축된 텍스트가 됩니다.

 

C++ 코드로 인코딩 과정을 살펴보겠습니다. (전체 코드는 아래에 있습니다.)

먼저 이진 트리를 구성하기 위해 만든 Node 클래스와 허프만 코딩을 위한 Huffman 클래스의 정의입니다.

#ifndef HUFFMAN
#define HUFFMAN

#include <string>
#include <queue>
#include <stack>
#include <map>
#include <iostream>

class Node {
public:
	Node() : left(nullptr), right(nullptr), cnt(0), ch(0) {}
	Node(char ch, int cnt) : left(nullptr), right(nullptr), cnt(cnt), ch(ch) {}
	Node(Node* left, Node* right) : left(left), right(right), cnt(left->cnt + right->cnt), ch(0) {}

	bool operator()(const Node* lhs, const Node* rhs) const;

	Node* left;
	Node* right;
	uint32_t cnt;
	char ch;
};

class Huffman {
private:
	Node* binTree;
	std::string code;

	void _getCode(const std::string& input);

public:
	Huffman() : binTree(nullptr), code("") {}
	~Huffman();

	void encoding(const std::string& input);
	std::string getCode() const;
	std::string decoding() const;
};

#endif

단순한 이진트리 역할을 하기 위한 Node 클래스를 정의했고, 허프만 코딩에 필요한 이진 트리에 사용됩니다.

Huffman 클래스에서 인코딩은 encoding 멤버 함수를 통해서 수행됩니다.

이 함수는 입력으로 사용될 문자열을 파라미터로 전달받고, 함수 내부에서 각 문자의 빈도를 측정하고 허프만 코드 변환을 위한 이진 트리를 구성합니다. 그리고, private 멤버 함수인 _getCode 함수를 통해서 문자열을 허프만 코드로 변환할 계획입니다.

 

encoding 함수를 살펴보겠습니다.

void Huffman::encoding(const std::string& input) {
	std::cout << "Input String : " << input << "\n";

	// count
	std::map<char, int> m;
	
	for (auto& c : input) {
		m[c]++;
	}

	// push into pq
	std::priority_queue<Node*, std::vector<Node*>, Node> pq;
	for (auto& e : m) {
		pq.push(new Node(e.first, e.second));
	}

	while (pq.size() > 1) {
		Node* left = pq.top();
		pq.pop();
		Node* right = pq.top();
		pq.pop();

		Node* newNode = new Node(left, right);
		pq.push(newNode);
	}

	binTree = pq.top();
	pq.pop();

	//convert tree to huffman code
	_getCode(input);

	return;
}

encoding 함수는 다음의 과정을 통해서 문자열을 허프만 코드로 변환합니다.

  1. 입력 문자열의 각 문자 빈도 측정 (line 5 ~ 9)
  2. 각 문자와 빈도를 데이터로 갖는 이진 트리를 우선순위 큐에 삽입 (line 11 ~ 15)
  3. 허프만 코드를 나타내는 이진 트리 생성 (line 17 ~ 28)
  4. 문자열을 허프만 코드로 변환 (line 31)

각 문자의 빈도는 문자열을 완전탐색하면서 카운트합니다. map을 사용해서 각 빈도를 저장하게 했습니다.

(순서가 사실 상관은 없으니 unorderd_map을 사용해도 좋을 것 같습니다.)

그리고 1에서 구한 데이터를 이진 트리인 Node 자료형으로 변환하면서 우선순위 큐에 삽입합니다.

우선순위 큐가 준비되었으면, 이제 우선순위 큐의 원소가 1개가 남을 때까지 2개씩 합치는 작업을 반복 수행합니다.

위 작업이 끝나면 우선순위 큐에는 최종 허프만 코드를 나타내는 이진트리 하나만 존재하고, binTree에 이진트리를 저장합니다.

그리고 문자열을 허프만 코드로 변환하는 작업을 수행하는 _getCode 함수를 호출합니다.

void Huffman::_getCode(const std::string& input) {
	std::string code = "";
	std::map<char, std::string> m;

	std::stack<std::pair<Node*, std::string>> st;
	st.push({ binTree, "" });

	while (!st.empty()) {
		Node* cur = st.top().first;
		std::string tmp = st.top().second;
		st.pop();

		if (cur->right != nullptr) {
			st.push({ cur->right, tmp + "1" });
		}
		if (cur->left != nullptr) {
			st.push({ cur->left, tmp + "0" });
		}

		if (cur->left == nullptr && cur->right == nullptr) {
			m[cur->ch] = tmp;
		}
	}

	for (const char& c : input) {
		code += m[c];
	}
	this->code = code;

	return;
}

_getCode 함수에서는 앞서 구한 허프만 코드의 이진트리를 가지고, 각 문자의 코드를 구합니다.

저는 각 문자의 코드를 저장하기 위해서 map 컨테이너를 사용하여 저장했습니다. 각 문자의 코드는 이진트리를 순회하면서 리프노드에 도달했을 때마다 각 문자의 코드를 저장합니다.

이렇게 저장된 코드를 가지고, 입력 문자열을 허프만 코드로 변환하고 그 변환된 문자열을 code 멤버 변수에 저장합니다.

 

이렇게 인코딩 결과는 Huffman 클래스의 getCode 함수를 통해 반환받을 수 있습니다.

디코딩

허프만 코드로 압축된 것을 해제하는 것은 간단합니다. 다만, 압축 과정에서 사용된 허프만 코드 트리가 필요합니다.

따라서, 허프만 코드 트리는 압축 파일의 일부분으로 저장되어야 한다는 특징이 있습니다.

 

이렇게 압축 과정에 사용한 허프만 코드 트리를 가지고, 디코딩은 다음의 과정을 수행합니다.

  1. 압축된 코드(비트열)을 읽으면서 허프만 코드 트리를 탐색
  2. 리프 노드에 도달하면 해당 문자를 출력하고, 허프만 코드 트리의 루트로 돌아간다.
  3. 1로 돌아가서 작업 반복

위 과정을 압축된 코드를 모두 읽을 때까지 반복 수행합니다.

 

허프만 코드인 1100001101010110001111 은 다음의 과정을 통해서 원래의 문자로 변환됩니다.

 

decoding 함수에서 위 과정이 수행됩니다.

std::string Huffman::decoding() const {
	if (binTree == nullptr) {
		std::cout << "Encoding First !\n";

		return "";
	}

	std::string ret = "";

	const Node* cur = binTree;
	for (const char& c : code) {
		if (c == '0') {
			cur = cur->left;
		}
		else {
			cur = cur->right;
		}

		if (cur->left == nullptr && cur->right == nullptr) {
			ret += cur->ch;
			cur = binTree;
		}
	}

	return ret;
}

decoding 함수는 다음의 과정으로 동작합니다.

  1. 인코딩을 먼저 수행했는지 체크(수행하지 않았더라면 빈 문자열 반환) (line 2 ~ 5)
  2. 비트열을 읽으면서 허프만 코드 트리 탐색
  3. 리프 노드에 도달하면 문자 기록
  4. 2번으로 돌아가서 루트 노드부터 다시 탐색
  5. 비트열을 모두 읽을 때까지 2 - 4 과정 반복

코드 자체는 매우 간단합니다. 비트가 0이면 왼쪽 트리로 이동하고, 1이면 오른쪽 트리로 이동합니다. 그리고 리프 노드에 도달했을 때 존재하는 문자를 기록하고, 비트열을 모두 읽을 때가지 이 작업을 반복 수행합니다.

아마 직접 구현했을 때, 다른 코드로 압축되는 경우도 있습니다.

이는 우선순위 큐에서 최소값을 어떻게 구하느냐에 따라서 달라질 수 있습니다.

저는 단순히 이진 트리의 빈도 수를 비교하였지만, 다른 조건들을 추가해주면 결과가 달라질 수 있습니다.

 

이는 Node 클래스의 operator() 함수에서 결정할 수 있습니다.

bool Node::operator()(const Node* lhs, const Node* rhs) const {
	return lhs->cnt > rhs->cnt;
}

 

실행 결과

#include <iostream>
#include "Huffman.h"

int main(void) {
	Huffman h;

	h.encoding("effective");
	std::cout << "Encoding Result : " << h.getCode() << std::endl;;
	std::cout << "Decoding Result : " << h.decoding() << std::endl;
	return 0;
}

 

전체 코드

Huffman.h

#ifndef HUFFMAN
#define HUFFMAN

#include <string>
#include <queue>
#include <stack>
#include <map>
#include <iostream>

class Node {
public:
	Node() : left(nullptr), right(nullptr), cnt(0), ch(0) {}
	Node(char ch, int cnt) : left(nullptr), right(nullptr), cnt(cnt), ch(ch) {}
	Node(Node* left, Node* right) : left(left), right(right), cnt(left->cnt + right->cnt), ch(0) {}

	bool operator()(const Node* lhs, const Node* rhs) const;

	Node* left;
	Node* right;
	uint32_t cnt;
	char ch;
};

class Huffman {
private:
	Node* binTree;
	std::string code;

	void _getCode(const std::string& input);

public:
	Huffman() : binTree(nullptr), code("") {}
	~Huffman();

	void encoding(const std::string& input);
	std::string getCode() const;
	std::string decoding() const;
};

#endif

Huffman.cpp

#include "Huffman.h"

bool Node::operator()(const Node* lhs, const Node* rhs) const {
	return lhs->cnt > rhs->cnt;
}

Huffman::~Huffman() {
	std::stack<Node*> st;
	st.push(binTree);

	while (!st.empty()) {
		Node* cur = st.top();
		st.pop();

		if (cur->left)
			st.push(cur->left);
		if (cur->right)
			st.push(cur->right);

		delete cur;
	}

	binTree = nullptr;
}

void Huffman::_getCode(const std::string& input) {
	std::string code = "";
	std::map<char, std::string> m;

	std::stack<std::pair<Node*, std::string>> st;
	st.push({ binTree, "" });

	while (!st.empty()) {
		Node* cur = st.top().first;
		std::string tmp = st.top().second;
		st.pop();

		if (cur->right != nullptr) {
			st.push({ cur->right, tmp + "1" });
		}
		if (cur->left != nullptr) {
			st.push({ cur->left, tmp + "0" });
		}

		if (cur->left == nullptr && cur->right == nullptr) {
			m[cur->ch] = tmp;
		}
	}

	for (const char& c : input) {
		code += m[c];
	}
	this->code = code;

	return;
}

std::string Huffman::getCode() const {
	if (code == "") {
		std::cout << "Encoding First !\n";
	}

	return code;
}

void Huffman::encoding(const std::string& input) {
	std::cout << "Input String : " << input << "\n";

	// count
	std::map<char, int> m;
	
	for (auto& c : input) {
		m[c]++;
	}

	// push into pq
	std::priority_queue<Node*, std::vector<Node*>, Node> pq;
	for (auto& e : m) {
		pq.push(new Node(e.first, e.second));
	}

	while (pq.size() > 1) {
		Node* left = pq.top();
		pq.pop();
		Node* right = pq.top();
		pq.pop();

		Node* newNode = new Node(left, right);
		pq.push(newNode);
	}

	binTree = pq.top();
	pq.pop();

	//convert tree to huffman code
	_getCode(input);

	return;
}

std::string Huffman::decoding() const {
	if (binTree == nullptr) {
		std::cout << "Encoding First !\n";

		return "";
	}

	std::string ret = "";

	const Node* cur = binTree;
	for (const char& c : code) {
		if (c == '0') {
			cur = cur->left;
		}
		else {
			cur = cur->right;
		}

		if (cur->left == nullptr && cur->right == nullptr) {
			ret += cur->ch;
			cur = binTree;
		}
	}

	return ret;
}

 

'Data Structure & Algorithm > 알고리즘' 카테고리의 다른 글

[암호] AES (Advanced Encryption Standard) - 1  (0) 2021.09.23
LZW 압축 (C++ 구현)  (1) 2021.08.29
Rabin-karp(라빈 카프) 알고리즘  (0) 2020.12.17
KMP 알고리즘  (0) 2020.11.25
투 포인터(Two Pointer), 슬라이딩 윈도우(Sliding Window)  (0) 2020.09.20

관련글

댓글

​

티스토리툴바