📌 허프만 코딩

허프만 코딩 (허프만 부호화) 은 입력 파일의 출현 빈도 (확률) 에 따라 코드 길이를 다르게 대응하는 가변 길이 부호화 방식 (VLC) 중 하나이다.
자주 나타나는 심볼은 짧은 코드를 대응하고 드물게 나타나는 심볼은 긴 코드를 대응시킴으로써 필요한 전체 데이터 길이가 짧아지므로 데이터 압축에 사용되는 기법이다.

접두부 (prefix code) 코드 구조 와 최적 코드 를 사용하는 알고리즘이다.

접두부 (prefix code) 코드 구조

각 문자에 부여된 이진 코드가 다른 문자에 부여된 이진 코드의 접두부가 되지 않는 코드
ex)
a 에 101 이라는 이진 코드가 부여됐다면, 다른 문자에는 1 , 10 , 101 과 같은 이진 코드는 부여될 수 없다.

최적 코드

인코딩된 메시지의 길이가 가장 짧은 코드를 의미한다.

Unix 에서 파일 압축 명렁어에 사용되고, JPEG, MP3 파일을 압축하기 위한 서브 루틴으로도 활용된다.

📌 구현 방법

1. 입력

압축할 데이터를 입력 받는다.
예시로 입력 받을 문자열 데이터는 "AAAAAAABBCCCDEEEEFFFFFFG"

2. 문자 빈도 분석

입력받은 문자열을 문자 단위로 끊어 등장 빈도를 분석한다.

• A : 8
• B : 2
• C : 3
• D : 1
• E : 4
• F : 5
• G : 1

3. 허프만 트리 생성

빈도 수를 우선순위로 하는 우선 순위 큐 (최소 힙) 을 구성한다.
해당 힙에서 빈도가 가장 낮은 두 문자를 선택하여 하나의 부모 노드를 가진 이진 트리를 생성한다.
부모 노드의 빈도 수는 두 자식 노드들의 빈도 수의 합이다.
만들어진 이진 트리는 다시 우선 순위 큐에 넣어지며, 우선 순위 큐의 요소가 하나만 남을 때까지 (모든 요소가 하나의 이진 트리로 구성될 때까지) 진행된다.

4. 이진 코드 생성

부모 노드의 왼쪽 자식 노드는 0, 오른쪽 자식 노드는 1로 표현한다.
루트 노드부터 끝까지 경로를 따라가면서 이진 코드를 생성한다.

생성된 이진 코드를 봤을 때, C : 110 과 E : 111 의 접두어가 될 수 있는 11 은 할당되지 않았음을 확인할 수 있다.

5. 압축

4번에서 생성된 이진 코드를 바탕으로 입력받은 문자열을 변경하여 압축한다.
"AAAAAAABBCCCDEEEEFFFFFFG" 문자열이 압축된 결과는 1010101010101000000011011011000101111111111110101010101010011

📌 코드 구현

#include <vector>
#include <unordered_map>
#include <queue>
#include <iostream>

using namespace std;

struct Node
{
	char character;	//문자
	int frequency;	//문자의 빈도수
	Node* left;		//해당 노드의 좌측 노드
	Node* right;	//해당 노드의 우측 노드

	Node()
	{
		this->character = 0;
		this->frequency = 0;
	}

	Node(char character, int frequency, Node* left = nullptr, Node* right = nullptr)
	{
		this->character = character;
		this->frequency = frequency;
		this->left = left;
		this->right = right;
	}
};

struct Compare
{
	bool operator()(Node* a, Node* b)
	{
		return a->frequency > b->frequency;
	}
};

class HuffmanTree
{
private:
	Node* root = nullptr;
	unordered_map<char, int> frequencyMap;
	unordered_map<char, string> info;
	priority_queue<Node*, vector<Node*>, Compare> pq;

public:
	//입력받은 문자열을 통해 허프만 트리 생성
	void Create(string& str)
	{
    	//문자 빈도수 체크
		for (char c : str)
		{
			frequencyMap[c]++;
		}
	
    	//우선 순위 큐에 빈도수를 저장한 node 삽입
		for (auto it : frequencyMap)
		{
			pq.push(new Node(it.first, it.second));
		}

		MakeTree();
		ZipCharacter(root, "");
	}

	unordered_map<char, string> GetInfo()
	{
		return info;
	}

private:
	//허프만 트리를 실질적으로 생성
	void MakeTree()
	{
		while (pq.size() > 1)
		{
			Node* newNode = new Node;

			newNode->left = pq.top();
			pq.pop();

			newNode->right = pq.top();
			pq.pop();

			newNode->frequency = newNode->left->frequency + newNode->right->frequency;
			pq.push(newNode);
		}

		root = pq.top();
	}

	//만들어진 허프만 트리를 통해 이진 코드를 생성
	void ZipCharacter(Node* node, string code)
	{
		if (node == nullptr)
			return;

		ZipCharacter(node->left, code + "0");
		ZipCharacter(node->right, code + "1");

		if (node->character != 0)
		{
			info[node->character] = code;
		}
	}
};

int main()
{
	//문자열 입력
	string str = "AAAAAAABBCCCDEEEEFFFFFFG";
    
	HuffmanTree t;
	t.Create(str);

	unordered_map<char, string> info = t.GetInfo();
	string s = "";
   	
    //만들어진 이진 코드들을 출력
	for (auto it : info)
	{
		cout << it.first << " : " << it.second << endl;
	}

	//해당 이진 코드들로 입력받은 문자열을 압축하여 출력
	for (char c : str)
	{
		s += info[c];
	}

	cout << s << endl;
}

코드 실행 결과