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

В преддверието на старта на курса «Алгоритми за разработчици» подготвили за вас превод на още един полезен материал.

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

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

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

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

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

Нека разгледаме низ «aabacdab». В него има 8 символа, и при кодиране с фиксирана дължина за съхранението му ще са необходими 64 бита. Забележете, че честотата на символите «a», «b», «c» и «d» е съответно 4, 2, 1, 1. Нека опитаме да представим «aabacdab» с по-малко количество битове, използвайки факта, че «a» се среща по-често от «b», а «b» се среща по-често от и и «d»«c» «a» . Започваме с това, че кодираме «b» с един бит, равен на 0, и и «d».

присвояваме двубитов код 11, а с три бита кодиране 100 и 011.

a
0

b
11

c
100

d
011

В крайна сметка получаваме: «aabacdab» така че низът 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» и «d» кодове, отговарящи на префиксното правило.

a
0

b
10

c
110

d
111

С използването на такова кодиране, редицата «aabacdab» ще бъде закодирана като 00100100011010 (0|0|10|0|100|011|0|10). А сега 00100100011010 вече ще можем недвусмислено да декодираме и да се върнем към нашата оригинална редица «aabacdab».

Кодиране на Хафман

Сега, когато разбрахме кодиране с променлива дължина и префиксно правило, нека поговорим за кодиране на Хафман.

Методът се основава на създаване на бинарни дървета. В него възелът може да бъде или крайният, или вътрешен. Поначало всички възли се считат за листа (крайни), които представляват самия символ и неговото тегло (т.е. честотата на появата). Вътрешните възли съдържат теглото на символа и сочат към два наследяващи възли. По общо споразумение битът "0" представлява преминаване по лявото клонче, а "1" — по дясното. В пълното дърво N листата и N-1 вътрешни възли. Препоръчително е, когато се изгражда дърво на Хафман, да се отстранят неизползваните символи за получаване на кодове с оптимална дължина.

Ще използваме опашка с приоритети за изграждане на дърво на Хафман, където на възела с най-ниска честота ще се присвои най-висок приоритет. По-долу са описани стъпките за изграждане:

1. Създайте листов възел за всеки символ и ги добавете в опашката с приоритети.
2. Докато в опашката има повече от един лист, правете следното:
   • Премахнете два възла с най-висок приоритет (с най-ниска честота) от опашката;
   • Създайте нов вътрешен възел, където тези два възла ще бъдат наследници, а честотата на появата ще бъде равна на сумата на честотите на тези два възла.
   • Добавете новия възел в опашката с приоритети.
3. Единственият останал възел ще бъде коренов, на него изграждането на дървото ще приключи.

Да предположим, че имаме някакъв текст, който се състои само от символи «a», «b», «c», «d» и «e», а честотите на тяхното появяване са равни на 15, 7, 6, 6 и 5 съответно. По-долу са представени илюстрации, които отразяват стъпките на алгоритъма.

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

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

По-долу ще намерите реализация на алгоритъма за компресия на Хаффман на езиците 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;

// Възел на дърво
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
{
	// обикаляйте дървото на Хъфман и съхранявайте кодовете на Хъфман
	// в карта.
	public static void encode(Node root, String str,
							  Map huffmanCode)
	{
		if (root == null)
			return;

		// намерен е листов възел
		if (root.left == null && root.right == null) {
			huffmanCode.put(root.ch, str);
		}


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

	// обикаляйте дървото на Хъфман и декодирайте кодираната строка
	public static int decode(Node root, int index, StringBuilder sb)
	{
		if (root == null)
			return index;

		// намерен е листов възел
		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;
	}

	// Създава дървото на Хъфман и кодовете на Хъфман и декодира предоставения текст
	public static void buildHuffmanTree(String text)
	{
		// брои честотата на появата на всеки символ
		// и я съхранява в карта
		Map 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);
		}

		// Създайте приоритетна опашка, за да съхранявате живите възли на дървото на Хъфман
		// Забележете, че елемент с най-висок приоритет има най-ниска честота
		PriorityQueue pq = new PriorityQueue((l, r) -> l.freq - r.freq);

		// Създайте листов възел за всеки символ и го добавете
		// в приоритетната опашка.
		for (Map.Entry entry : freq.entrySet()) {
			pq.add(new Node(entry.getKey(), entry.getValue()));
		}

		// правете до тогава, докато в опашката има повече от един възел
		while (pq.size() != 1)
		{
			// Премахнете двата възела с най-висок приоритет
			// (най-ниска честота) от опашката
			Node left = pq.poll();
			Node right = pq.poll();

			// Създайте нов вътрешен възел с тези два възела като деца
			// и с честота, равна на сумата на честотите на двата възела
			// Добавете новия възел в приоритетната опашка.
			int sum = left.freq + right.freq;
			pq.add(new Node(' ', sum, left, right));
		}

		// root съхранява указателя към корена на дървото на Хъфман
		Node root = pq.peek();

		// обикаляйте дървото на Хъфман и съхранявайте кодовете на Хъфман в карта
		Map huffmanCode = new HashMap();
		encode(root, "", huffmanCode);

		// отпечатайте кодовете на Хъфман
		System.out.println("Кодовете на Хъфман са :n");
		for (Map.Entry entry : huffmanCode.entrySet()) {
			System.out.println(entry.getKey() + " " + entry.getValue());
		}

		System.out.println("nОригиналният низ беше :n" + text);

		// отпечатайте кодираната строка
		StringBuilder sb = new StringBuilder();
		for (int i = 0 ; i < text.length(); i++) {
			sb.append(huffmanCode.get(text.charAt(i)));
		}

		System.out.println("nКодираната строка е :n" + sb);

		// обикаляйте отново дървото на Хъфман и този път
		// декодирайте кодираната строка
		int index = -1;
		System.out.println("nДекодираният низ е: n");
		while (index < sb.length() - 2) {
			index = decode(root, index, sb);
		}
	}

	public static void main(String[] args)
	{
		String text = "Хъфмановото кодиране е алгоритъм за компресия на данни.";

		buildHuffmanTree(text);
	}
}

Забележка: Паметта, използвана от входния низ, е 47 * 8 = 376 бита, а кодиранният низ заема само 194 бита, т.е. данните се компресират с около 48%. В програмата на С++ по-горе използваме класа 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

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

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