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

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

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

Знаеме дека секој знак е зачуван како низа од 0 и 1 и зафаќа 8 бита. Ова се нарекува кодирање со фиксна должина бидејќи секој знак користи ист фиксен број на битови за складирање.

Да речеме дека текстот е даден. Како можеме да го намалиме просторот потребен за складирање на еден знак?

Основната идеја е кодирање со променлива должина. Можеме да го искористиме фактот дека некои знаци се појавуваат почесто во текстот од другите (види овде) да се развие алгоритам кој ќе ја претставува истата низа на знаци во помалку битови. Во кодирањето со променлива должина, ние доделуваме променлив број на битови на знаци во зависност од зачестеноста на нивното појавување во даден текст. На крајот на краиштата, некои знаци може да заземат само 1 бит, додека други може да заземат 2 бита, 3 или повеќе. Проблемот со кодирањето со променлива должина е само последователното декодирање на низата.

Како, знаејќи низа од битови, можете недвосмислено да ја декодирате?

Размислете за линијата "aabacdab". Има 8 знаци, а со кодирање со фиксна должина ќе бидат потребни 64 бита за да се складира. Забележете дека фреквенцијата на симболот „а“, „б“, „в“ и "Г" е еднакво на 4, 2, 1, 1 соодветно. Ајде да се обидеме да замислиме "aabacdab" во помалку битови, искористувајќи го фактот дека "до" се јавува почесто од "Б"И "Б" се јавува почесто од "в" и "Г". Ќе започнеме со кодирање "до" користејќи еден бит еднаков на 0, "Б" ќе доделиме двобитен код на 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
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. Единствениот преостанат јазол ќе биде коренскиот јазол и ова ќе ја заврши изградбата на дрвото.

Да замислиме дека имаме некој текст кој се состои само од знаци "а бе це де" и „и“, а нивните фреквенции на појавување се 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;

// 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++, ја користиме класата стринг за складирање на кодирана низа за да ја направиме програмата читлива.

Бидејќи ефикасните структури на податоци за приоритетна редица бараат по вметнување О (лог (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