Алгоритъм за компресиране на Huffman

Преди началото на курса "Алгоритми за разработчици" подготви за вас превод на друг полезен материал.

Кодирането на Huffman е алгоритъм за компресиране на данни, който формулира основната идея за компресиране на файлове. В тази статия ще говорим за кодиране с фиксирана и променлива дължина, уникално декодируеми кодове, префиксни правила и изграждане на дърво на Хъфман.

Знаем, че всеки знак се съхранява като последователност от 0 и 1 и заема 8 бита. Това се нарича кодиране с фиксирана дължина, защото всеки знак използва един и същ фиксиран брой битове за съхранение.

Да кажем, че ни е даден текст. Как можем да намалим количеството пространство, необходимо за съхраняване на един знак?

Основната идея е кодиране с променлива дължина. Можем да използваме факта, че някои знаци в текста се срещат по-често от други (см. тук), за да се разработи алгоритъм, който ще представи същата последователност от знаци в по-малко битове. При кодирането с променлива дължина ние присвояваме на знаците променлив брой битове в зависимост от това колко често се появяват в даден текст. В крайна сметка някои знаци могат да заемат само 1 бит, докато други могат да заемат 2 бита, 3 или повече. Проблемът с кодирането с променлива дължина е само последващото декодиране на последователността.

Как, знаейки последователността от битове, да го декодирам недвусмислено?

Помислете за линията "абакдаб". Той има 8 знака и при кодиране с фиксирана дължина ще са му необходими 64 бита, за да го съхрани. Имайте предвид, че честотата на символа "а", "б", "в" и "Д" е равно на 4, 2, 1, 1 съответно. Нека се опитаме да си представим "абакдаб" по-малко битове, използвайки факта, че "да се" се среща по-често от "В"И "В" се среща по-често от "° С" и "Д". Да започнем с кодирането "да се" с един бит равен на 0, "В" ще зададем двубитов код 11 и използвайки три бита 100 и 011 ще кодираме "° С" и "Д".

В резултат на това ще получим:

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
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. По-долу има илюстрации, които отразяват стъпките на алгоритъма.

Пътят от корена до който и да е краен възел ще съхранява оптималния код на префикса (известен също като код на Хъфман), съответстващ на знака, свързан с този краен възел.

Дърво на Хъфман

По-долу ще намерите изпълнението на алгоритъма за компресиране на Huffman в C++ и Java:

#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++ програмата по-горе ние използваме класа string, за да съхраним кодирания низ, за ​​да направим програмата четима.

Тъй като ефективните приоритетни структури от данни на опашка изискват всяко вмъкване O(log(N)) време, но в пълно двоично дърво с N присъстват листа 2N-1 възли и дървото на Хъфман е пълно двоично дърво, тогава алгоритъмът се изпълнява O(Nlog(N)) време, къде N - Герои.

Източници:

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

Научете повече за курса.

Източник: www.habr.com