ჰაფმანის შეკუმშვის ალგორითმი

კურსის დაწყებამდე "ალგორითმები დეველოპერებისთვის" მოამზადეთ თქვენთვის კიდევ ერთი სასარგებლო მასალის თარგმანი.

Huffman კოდირება არის მონაცემთა შეკუმშვის ალგორითმი, რომელიც აყალიბებს ფაილის შეკუმშვის ძირითად იდეას. ამ სტატიაში ვისაუბრებთ ფიქსირებული და ცვლადი სიგრძის კოდირებაზე, ცალსახად დეკოდირებად კოდებზე, პრეფიქსის წესებზე და ჰაფმანის ხის აგებაზე.

ჩვენ ვიცით, რომ თითოეული სიმბოლო ინახება 0 და 1-ების თანმიმდევრობით და იღებს 8 ბიტს. ამას ეწოდება ფიქსირებული სიგრძის კოდირება, რადგან თითოეული სიმბოლო იყენებს ბიტების იგივე რაოდენობას შესანახად.

ვთქვათ, მოგვცეს ტექსტი. როგორ შევამციროთ ერთი სიმბოლოს შესანახად საჭირო სივრცის რაოდენობა?

მთავარი იდეა არის ცვლადი სიგრძის კოდირება. ჩვენ შეგვიძლია გამოვიყენოთ ის ფაქტი, რომ ტექსტში ზოგიერთი სიმბოლო უფრო ხშირად გვხვდება, ვიდრე სხვები (სმ. здесь) შეიმუშაოს ალგორითმი, რომელიც წარმოადგენს სიმბოლოების იგივე თანმიმდევრობას ნაკლებ ბიტებში. ცვლადი სიგრძის კოდირებისას ჩვენ სიმბოლოებს ვანიჭებთ ბიტების ცვლად რაოდენობას, იმისდა მიხედვით, თუ რამდენად ხშირად ჩნდებიან ისინი მოცემულ ტექსტში. საბოლოოდ, ზოგიერთ სიმბოლოს შეიძლება დასჭირდეს 1 ბიტი, ხოლო ზოგს შეიძლება დასჭირდეს 2 ბიტი, 3 ან მეტი. ცვლადი სიგრძის კოდირების პრობლემა მხოლოდ თანმიმდევრობის შემდგომი გაშიფვრაა.

როგორ, ბიტების თანმიმდევრობის ცოდნით, ცალსახად გაშიფვრა?

განიხილეთ ხაზი "აბადაბი". მას აქვს 8 სიმბოლო და ფიქსირებული სიგრძის კოდირებისას მის შესანახად დასჭირდება 64 ბიტი. გაითვალისწინეთ, რომ სიმბოლოს სიხშირე "ა", "ბ", "გ" и "დ" უდრის 4, 2, 1, 1 შესაბამისად. შევეცადოთ წარმოვიდგინოთ "აბადაბი" ნაკლები ბიტი, იმ ფაქტის გამოყენებით "to" ხდება უფრო ხშირად ვიდრე "ბ"ხოლო "ბ" ხდება უფრო ხშირად ვიდრე "c" и "დ". დავიწყოთ კოდირებით "to" ერთი ბიტით 0-ის ტოლი, "ბ" ჩვენ მივანიჭებთ ორბიტიან კოდს 11, ხოლო სამი ბიტის გამოყენებით 100 და 011 ჩვენ დავშიფრავთ "c" и "დ".

შედეგად, ჩვენ მივიღებთ:

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 ჩვენ უკვე შევძლებთ ცალსახად გაშიფვრას და ჩვენს თავდაპირველ სტრიქონს დაბრუნებას "აბადაბი".

ჰაფმანის კოდირება

ახლა, როდესაც ჩვენ განვიხილეთ ცვლადი სიგრძის კოდირება და პრეფიქსის წესი, მოდით ვისაუბროთ ჰაფმანის დაშიფვრაზე.

მეთოდი ეფუძნება ბინარული ხეების შექმნას. მასში კვანძი შეიძლება იყოს საბოლოო ან შიდა. თავდაპირველად, ყველა კვანძი განიხილება ფოთლებად (ტერმინალები), რომლებიც წარმოადგენს თავად სიმბოლოს და მის წონას (ანუ გაჩენის სიხშირეს). შიდა კვანძები შეიცავს სიმბოლოს წონას და ეხება ორ შთამომავალ კვანძს. საერთო შეთანხმებით, ცოტა «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++ პროგრამაში, ჩვენ ვიყენებთ სტრიქონების კლასს დაშიფრული სტრიქონის შესანახად, რათა პროგრამა იკითხებოდეს.

იმის გამო, რომ ეფექტური პრიორიტეტული რიგის მონაცემთა სტრუქტურები საჭიროებენ თითო ჩასმას 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