Хафманов алгоритам компресије

Пре почетка курса „Алгоритми за програмере“ припремио за вас превод још једног корисног материјала.

Хафманово кодирање је алгоритам компресије података који формулише основну идеју компресије датотека. У овом чланку ћемо говорити о кодирању фиксне и променљиве дужине, јединствено декодирајућим кодовима, правилима префикса и изградњи Хафмановог дрвета.

Знамо да се сваки знак чува као низ од 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 већ ћемо моћи недвосмислено декодирати и вратити се на наш оригинални низ "абацдаб".

Хуффман кодирање

Сада када смо се позабавили кодирањем променљиве дужине и правилом префикса, хајде да причамо о Хафмановом кодирању.

Метода се заснива на креирању бинарних стабала. У њему чвор може бити коначан или унутрашњи. У почетку се сви чворови сматрају листовима (терминалима), који представљају сам симбол и његову тежину (односно учесталост појављивања). Унутрашњи чворови садрже тежину карактера и односе се на два чвора потомка. По општем договору, бит «КСНУМКС» представља праћење леве гране, и «КСНУМКС» - на десној. у пуном стаблу N листови и Н-КСНУМКС унутрашњи чворови. Препоручује се да се приликом конструисања Хафмановог дрвета неискоришћени симболи одбаце како би се добили оптимални кодови дужине.

Користићемо приоритетни ред да направимо Хафманово стабло, где ће чвор са најнижом фреквенцијом добити највећи приоритет. Кораци изградње су описани у наставку:

1. Креирајте лисни чвор за сваки знак и додајте их у приоритетни ред.
2. Док постоји више од једног листа у реду, урадите следеће:
   • Уклоните два чвора са највишим приоритетом (најнижом фреквенцијом) из реда;
   • Направите нови унутрашњи чвор, где ће ова два чвора бити деца, а учесталост појављивања ће бити једнака збиру фреквенција ова два чвора.
   • Додајте нови чвор у приоритетни ред.
3. Једини преостали чвор биће корен и тиме ће се завршити конструкција дрвета.

Замислите да имамо неки текст који се састоји само од знакова "а б ц д" и "и", а фреквенције њиховог појављивања су 15, 7, 6, 6 и 5, респективно. Испод су илустрације које одражавају кораке алгоритма.

Путања од корена до било ког крајњег чвора ће ускладиштити оптимални код префикса (такође познат као Хафманов код) који одговара карактеру повезаном са тим крајњим чвором.

Хафманово дрво

Испод ћете наћи имплементацију Хафмановог алгоритма компресије у Ц++ и Јави:

#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%. У Ц++ програму изнад, користимо стринг класу за чување кодираног стринга како бисмо програм учинили читљивим.

Зато што ефикасне структуре података реда приоритета захтевају по уметању О(лог(Н)) време, али у потпуном бинарном стаблу са N оставља присутне КСНУМКСН-КСНУМКС чворова, а Хафманово стабло је комплетно бинарно стабло, тада се алгоритам укључује О(Нлог(Н)) време, где N - Ликови.

Извори:

ен.википедиа.орг/вики/Хуффман_цодинг
ен.википедиа.орг/вики/Вариабле-ленгтх_цоде
ввв.иоутубе.цом/ватцх?в=5вРПин4окЦо

Сазнајте више о курсу.

Извор: ввв.хабр.цом