허프만 압축 알고리즘

코스 시작 전 "개발자를 위한 알고리즘" 다른 유용한 자료의 번역을 준비했습니다.

허프만 코딩은 파일 압축의 기본 아이디어를 공식화하는 데이터 압축 알고리즘입니다. 이 기사에서는 고정 및 가변 길이 인코딩, 고유하게 디코딩 가능한 코드, 접두사 규칙 및 Huffman 트리 구축에 대해 설명합니다.

우리는 각 문자가 0과 1의 시퀀스로 저장되고 8비트를 차지한다는 것을 알고 있습니다. 각 문자가 동일한 고정 비트 수를 사용하여 저장하기 때문에 이를 고정 길이 인코딩이라고 합니다.

텍스트가 주어졌다고 가정해 봅시다. 단일 문자를 저장하는 데 필요한 공간을 어떻게 줄일 수 있습니까?

주요 아이디어는 가변 길이 인코딩입니다. 텍스트의 일부 문자가 다른 문자보다 더 자주 발생한다는 사실을 사용할 수 있습니다(여기를 보아라.) 더 적은 비트로 동일한 문자 시퀀스를 나타내는 알고리즘을 개발합니다. 가변 길이 인코딩에서는 주어진 텍스트에 얼마나 자주 나타나는지에 따라 문자에 가변 비트 수를 할당합니다. 결국 일부 문자는 1비트만 걸릴 수도 있고 다른 문자는 2비트, 3비트 이상 걸릴 수도 있습니다. 가변 길이 인코딩의 문제는 시퀀스의 후속 디코딩에만 있습니다.

어떻게 비트 시퀀스를 알면 명확하게 디코딩할 수 있습니까?

선을 고려하십시오 "아박답". 8자이며 고정 길이를 인코딩할 때 저장하려면 64비트가 필요합니다. 기호 주파수 "a", "b", "c" и "NS" 각각 4, 2, 1, 1과 같습니다. 상상해 봅시다 "아박답" 더 적은 비트, 사실을 사용하여 "에" 보다 자주 발생 "NS"과 "NS" 보다 자주 발생 "씨" и "NS". 코딩부터 시작하자 "에" 0과 같은 XNUMX비트, "NS" 11비트 코드 100을 할당하고 011비트 XNUMX과 XNUMX을 사용하여 인코딩합니다. "씨" и "NS".

결과적으로 다음을 얻을 수 있습니다.

a
0

b
11

c
100

d
011

그래서 라인 "아박답" 우리는 다음과 같이 인코딩합니다 00110100011011 (0|0|11|0|100|011|0|11)위의 코드를 사용하여. 그러나 주요 문제는 디코딩에 있습니다. 문자열을 해독하려고 할 때 00110100011011, 다음과 같이 나타낼 수 있으므로 모호한 결과를 얻습니다.

0|011|0|100|011|0|11    adacdab
0|0|11|0|100|0|11|011   aabacabd
0|011|0|100|0|11|0|11   adacabab 

...
기타

이러한 모호성을 피하기 위해 인코딩이 다음과 같은 개념을 충족하는지 확인해야 합니다. 접두사 규칙, 이는 코드가 하나의 고유한 방식으로만 디코딩될 수 있음을 의미합니다. 접두사 규칙은 어떤 코드도 다른 코드의 접두사가 되지 않도록 합니다. 코드란 특정 문자를 나타내는 데 사용되는 비트를 의미합니다. 위의 예에서 0 접두사입니다 011, 접두사 규칙을 위반합니다. 따라서 코드가 접두사 규칙을 충족하면 고유하게 디코딩할 수 있습니다(반대의 경우도 마찬가지).

위의 예를 다시 살펴보겠습니다. 이번에는 기호에 할당합니다. "a", "b", "c" и "NS" 접두사 규칙을 만족하는 코드.

a
0

b
10

c
110

d
111

이 인코딩을 사용하면 문자열 "아박답" 다음과 같이 인코딩됩니다. 00100100011010 (0|0|10|0|100|011|0|10). 하지만, 00100100011010 이미 명확하게 디코딩하고 원래 문자열로 돌아갈 수 있습니다. "아박답".

허프만 코딩

가변 길이 인코딩 및 접두사 규칙을 다루었으므로 이제 Huffman 인코딩에 대해 이야기하겠습니다.

이 방법은 이진 트리 생성을 기반으로 합니다. 여기에서 노드는 최종 또는 내부일 수 있습니다. 처음에 모든 노드는 기호 자체와 해당 가중치(즉, 발생 빈도)를 나타내는 리프(터미널)로 간주됩니다. 내부 노드는 캐릭터의 가중치를 포함하며 두 개의 하위 노드를 참조합니다. 일반 합의에 의해 비트 «0» 왼쪽 분기 다음을 나타냅니다. «1» - 오른쪽으로. 전체 트리에서 N 나뭇잎과 N-1 내부 노드. 허프만 트리를 구성할 때 최적의 길이 코드를 얻기 위해 사용하지 않는 기호를 버리는 것이 좋습니다.

우선 순위 대기열을 사용하여 주파수가 가장 낮은 노드에 가장 높은 우선 순위가 부여되는 Huffman 트리를 구축합니다. 구성 단계는 다음과 같습니다.

1. 각 캐릭터에 대한 리프 노드를 생성하고 우선순위 대기열에 추가합니다.
2. 대기열에 시트가 두 개 이상 있는 경우 다음을 수행합니다.
   • 대기열에서 우선 순위가 가장 높은(가장 낮은 빈도) 두 노드를 제거합니다.
   • 이 두 노드가 자식이 될 새 내부 노드를 만들고 발생 빈도는 이 두 노드의 빈도의 합과 같습니다.
   • 우선 순위 대기열에 새 노드를 추가합니다.
3. 남은 유일한 노드는 루트가 될 것이며 이것으로 트리 구성이 완료됩니다.

문자로만 구성된 텍스트가 있다고 상상해보십시오. "a", "b", "c", "d" и "과", 발생 빈도는 각각 15, 7, 6, 6 및 5입니다. 아래는 알고리즘의 단계를 반영하는 그림입니다.

루트에서 끝 노드까지의 경로는 해당 끝 노드와 관련된 문자에 해당하는 최적의 접두사 코드(허프만 코드라고도 함)를 저장합니다.

허프만 트리

아래에서 C++ 및 Java로 Huffman 압축 알고리즘을 구현한 것을 볼 수 있습니다.

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

// A Tree node
struct Node
{
	char ch;
	int freq;
	Node *left, *right;
};

// Function to allocate a new tree node
Node* getNode(char ch, int freq, Node* left, Node* right)
{
	Node* node = new Node();

	node->ch = ch;
	node->freq = freq;
	node->left = left;
	node->right = right;

	return node;
}

// Comparison object to be used to order the heap
struct comp
{
	bool operator()(Node* l, Node* r)
	{
		// highest priority item has lowest frequency
		return l->freq > r->freq;
	}
};

// traverse the Huffman Tree and store Huffman Codes
// in a map.
void encode(Node* root, string str,
			unordered_map<char, string> &huffmanCode)
{
	if (root == nullptr)
		return;

	// found a leaf node
	if (!root->left && !root->right) {
		huffmanCode[root->ch] = str;
	}

	encode(root->left, str + "0", huffmanCode);
	encode(root->right, str + "1", huffmanCode);
}

// traverse the Huffman Tree and decode the encoded string
void decode(Node* root, int &index, string str)
{
	if (root == nullptr) {
		return;
	}

	// found a leaf node
	if (!root->left && !root->right)
	{
		cout << root->ch;
		return;
	}

	index++;

	if (str[index] =='0')
		decode(root->left, index, str);
	else
		decode(root->right, index, str);
}

// Builds Huffman Tree and decode given input text
void buildHuffmanTree(string text)
{
	// count frequency of appearance of each character
	// and store it in a map
	unordered_map<char, int> freq;
	for (char ch: text) {
		freq[ch]++;
	}

	// Create a priority queue to store live nodes of
	// Huffman tree;
	priority_queue<Node*, vector<Node*>, comp> pq;

	// Create a leaf node for each character and add it
	// to the priority queue.
	for (auto pair: freq) {
		pq.push(getNode(pair.first, pair.second, nullptr, nullptr));
	}

	// do till there is more than one node in the queue
	while (pq.size() != 1)
	{
		// Remove the two nodes of highest priority
		// (lowest frequency) from the queue
		Node *left = pq.top(); pq.pop();
		Node *right = pq.top();	pq.pop();

		// Create a new internal node with these two nodes
		// as children and with frequency equal to the sum
		// of the two nodes' frequencies. Add the new node
		// to the priority queue.
		int sum = left->freq + right->freq;
		pq.push(getNode('', sum, left, right));
	}

	// root stores pointer to root of Huffman Tree
	Node* root = pq.top();

	// traverse the Huffman Tree and store Huffman Codes
	// in a map. Also prints them
	unordered_map<char, string> huffmanCode;
	encode(root, "", huffmanCode);

	cout << "Huffman Codes are :n" << 'n';
	for (auto pair: huffmanCode) {
		cout << pair.first << " " << pair.second << 'n';
	}

	cout << "nOriginal string was :n" << text << 'n';

	// print encoded string
	string str = "";
	for (char ch: text) {
		str += huffmanCode[ch];
	}

	cout << "nEncoded string is :n" << str << 'n';

	// traverse the Huffman Tree again and this time
	// decode the encoded string
	int index = -1;
	cout << "nDecoded string is: n";
	while (index < (int)str.size() - 2) {
		decode(root, index, str);
	}
}

// Huffman coding algorithm
int main()
{
	string text = "Huffman coding is a data compression algorithm.";

	buildHuffmanTree(text);

	return 0;
}

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

// A Tree node
class Node
{
	char ch;
	int freq;
	Node left = null, right = null;

	Node(char ch, int freq)
	{
		this.ch = ch;
		this.freq = freq;
	}

	public Node(char ch, int freq, Node left, Node right) {
		this.ch = ch;
		this.freq = freq;
		this.left = left;
		this.right = right;
	}
};

class Huffman
{
	// traverse the Huffman Tree and store Huffman Codes
	// in a map.
	public static void encode(Node root, String str,
							  Map<Character, String> huffmanCode)
	{
		if (root == null)
			return;

		// found a leaf node
		if (root.left == null && root.right == null) {
			huffmanCode.put(root.ch, str);
		}


		encode(root.left, str + "0", huffmanCode);
		encode(root.right, str + "1", huffmanCode);
	}

	// traverse the Huffman Tree and decode the encoded string
	public static int decode(Node root, int index, StringBuilder sb)
	{
		if (root == null)
			return index;

		// found a leaf node
		if (root.left == null && root.right == null)
		{
			System.out.print(root.ch);
			return index;
		}

		index++;

		if (sb.charAt(index) == '0')
			index = decode(root.left, index, sb);
		else
			index = decode(root.right, index, sb);

		return index;
	}

	// Builds Huffman Tree and huffmanCode and decode given input text
	public static void buildHuffmanTree(String text)
	{
		// count frequency of appearance of each character
		// and store it in a map
		Map<Character, Integer> freq = new HashMap<>();
		for (int i = 0 ; i < text.length(); i++) {
			if (!freq.containsKey(text.charAt(i))) {
				freq.put(text.charAt(i), 0);
			}
			freq.put(text.charAt(i), freq.get(text.charAt(i)) + 1);
		}

		// Create a priority queue to store live nodes of Huffman tree
		// Notice that highest priority item has lowest frequency
		PriorityQueue<Node> pq = new PriorityQueue<>(
										(l, r) -> l.freq - r.freq);

		// Create a leaf node for each character and add it
		// to the priority queue.
		for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
			pq.add(new Node(entry.getKey(), entry.getValue()));
		}

		// do till there is more than one node in the queue
		while (pq.size() != 1)
		{
			// Remove the two nodes of highest priority
			// (lowest frequency) from the queue
			Node left = pq.poll();
			Node right = pq.poll();

			// Create a new internal node with these two nodes as children 
			// and with frequency equal to the sum of the two nodes
			// frequencies. Add the new node to the priority queue.
			int sum = left.freq + right.freq;
			pq.add(new Node('', sum, left, right));
		}

		// root stores pointer to root of Huffman Tree
		Node root = pq.peek();

		// traverse the Huffman tree and store the Huffman codes in a map
		Map<Character, String> huffmanCode = new HashMap<>();
		encode(root, "", huffmanCode);

		// print the Huffman codes
		System.out.println("Huffman Codes are :n");
		for (Map.Entry<Character, String> entry : huffmanCode.entrySet()) {
			System.out.println(entry.getKey() + " " + entry.getValue());
		}

		System.out.println("nOriginal string was :n" + text);

		// print encoded string
		StringBuilder sb = new StringBuilder();
		for (int i = 0 ; i < text.length(); i++) {
			sb.append(huffmanCode.get(text.charAt(i)));
		}

		System.out.println("nEncoded string is :n" + sb);

		// traverse the Huffman Tree again and this time
		// decode the encoded string
		int index = -1;
		System.out.println("nDecoded string is: n");
		while (index < sb.length() - 2) {
			index = decode(root, index, sb);
		}
	}

	public static void main(String[] args)
	{
		String text = "Huffman coding is a data compression algorithm.";

		buildHuffmanTree(text);
	}
}

참고 : 입력 문자열이 사용하는 메모리는 47 * 8 = 376비트이고 인코딩된 문자열은 194비트입니다. 데이터는 약 48% 압축됩니다. 위의 C++ 프로그램에서 문자열 클래스를 사용하여 프로그램을 읽을 수 있도록 인코딩된 문자열을 저장합니다.

효율적인 우선 순위 큐 데이터 구조는 삽입마다 필요하기 때문에 O(로그(N)) 하지만 완전한 이진 트리에서 N 잎사귀 2N-1 노드이고 Huffman 트리는 완전한 이진 트리이며 알고리즘은 다음에서 실행됩니다. O(Nlog(N)) 시간, 어디서 N - 캐릭터.

출처 :

en.wikipedia.org/wiki/Huffman_coding
en.wikipedia.org/wiki/Variable-length_code
www.youtube.com/watch?v=5wRPin4oxCo

과정에 대해 자세히 알아보세요.

출처 : habr.com