হাফম্যান কম্প্রেশন অ্যালগরিদম

কোর্স শুরুর আগে "বিকাশকারীদের জন্য অ্যালগরিদম" আপনার জন্য অন্য একটি দরকারী উপাদানের অনুবাদ প্রস্তুত করা হয়েছে।

হাফম্যান কোডিং হল একটি ডেটা কম্প্রেশন অ্যালগরিদম যা ফাইল কম্প্রেশনের প্রাথমিক ধারণা তৈরি করে। এই নিবন্ধে, আমরা স্থির এবং পরিবর্তনশীল দৈর্ঘ্যের এনকোডিং, অনন্যভাবে ডিকোডেবল কোড, উপসর্গের নিয়ম এবং একটি হাফম্যান ট্রি তৈরির বিষয়ে কথা বলব।

আমরা জানি যে প্রতিটি অক্ষর 0 এবং 1 এর ক্রম হিসাবে সংরক্ষণ করা হয় এবং 8 বিট নেয়। একে নির্দিষ্ট দৈর্ঘ্যের এনকোডিং বলা হয় কারণ প্রতিটি অক্ষর সংরক্ষণের জন্য একই নির্দিষ্ট সংখ্যক বিট ব্যবহার করে।

ধরা যাক আমরা টেক্সট দেওয়া করছি. কিভাবে আমরা একটি একক অক্ষর সংরক্ষণ করার জন্য প্রয়োজনীয় স্থানের পরিমাণ কমাতে পারি?

প্রধান ধারণা পরিবর্তনশীল দৈর্ঘ্য এনকোডিং হয়. আমরা এই সত্যটি ব্যবহার করতে পারি যে পাঠ্যের কিছু অক্ষর অন্যদের চেয়ে বেশি ঘন ঘন ঘটে (এখানে দেখুন) একটি অ্যালগরিদম বিকাশ করতে যা কম বিটে অক্ষরের একই ক্রম উপস্থাপন করবে। পরিবর্তনশীল দৈর্ঘ্যের এনকোডিং-এ, আমরা অক্ষরগুলিকে একটি পরিবর্তনশীল সংখ্যক বিট বরাদ্দ করি, এটি একটি প্রদত্ত পাঠ্যে কত ঘন ঘন প্রদর্শিত হবে তার উপর নির্ভর করে। শেষ পর্যন্ত, কিছু অক্ষর 1 বিটের মতো কম সময় নিতে পারে, অন্যরা 2 বিট, 3 বা তার বেশি সময় নিতে পারে। পরিবর্তনশীল দৈর্ঘ্যের এনকোডিংয়ের সমস্যাটি কেবলমাত্র ক্রমটির পরবর্তী ডিকোডিং।

কিভাবে, বিট ক্রম বুদ্ধিমান, এটা দ্ব্যর্থহীনভাবে ডিকোড?

লাইনটি বিবেচনা করুন "abacdab". এটিতে 8টি অক্ষর রয়েছে এবং একটি নির্দিষ্ট দৈর্ঘ্য এনকোড করার সময় এটি সংরক্ষণ করতে 64 বিট প্রয়োজন হবে। লক্ষণীয় ফ্রিকোয়েন্সি লক্ষ্য করুন "a", "b", "c" и "ডি" যথাক্রমে 4, 2, 1, 1 সমান। এর কল্পনা করার চেষ্টা করা যাক "abacdab" কম বিট, যে ব্যবহার করে "প্রতি" তুলনায় আরো ঘন ঘন ঘটে "খ"এবং "খ" তুলনায় আরো ঘন ঘন ঘটে "গ" и "ডি". কোডিং দিয়ে শুরু করা যাক "প্রতি" 0 এর সমান এক বিট সহ, "খ" আমরা একটি দুই-বিট কোড 11 বরাদ্দ করব, এবং তিনটি বিট 100 এবং 011 ব্যবহার করে আমরা এনকোড করব "গ" и "ডি".

ফলস্বরূপ, আমরা পাব:

a
0

b
11

c
100

d
011

তাই লাইন "abacdab" আমরা হিসাবে এনকোড করব 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" и "ডি" কোড যে উপসর্গ নিয়ম সন্তুষ্ট.

a
0

b
10

c
110

d
111

এই এনকোডিং, স্ট্রিং সঙ্গে "abacdab" হিসাবে এনকোড করা হবে 00100100011010 (0|0|10|0|100|011|0|10)। এবং এখানে 00100100011010 আমরা ইতিমধ্যেই দ্ব্যর্থহীনভাবে ডিকোড করতে এবং আমাদের আসল স্ট্রিংয়ে ফিরে যেতে সক্ষম হব "abacdab".

হাফম্যান কোডিং

এখন যেহেতু আমরা পরিবর্তনশীল দৈর্ঘ্য এনকোডিং এবং প্রিফিক্স নিয়ম নিয়ে কাজ করেছি, আসুন হাফম্যান এনকোডিং সম্পর্কে কথা বলি।

পদ্ধতিটি বাইনারি গাছ তৈরির উপর ভিত্তি করে। এটিতে, নোড চূড়ান্ত বা অভ্যন্তরীণ হতে পারে। প্রাথমিকভাবে, সমস্ত নোডকে পাতা (টার্মিনাল) হিসাবে বিবেচনা করা হয়, যা প্রতীক নিজেই এবং এর ওজন (অর্থাৎ, সংঘটনের ফ্রিকোয়েন্সি) প্রতিনিধিত্ব করে। অভ্যন্তরীণ নোডগুলি চরিত্রের ওজন ধারণ করে এবং দুটি বংশধর নোডকে উল্লেখ করে। সাধারণ চুক্তি দ্বারা, বিট "0" বাম শাখা অনুসরণ করে প্রতিনিধিত্ব করে, এবং "1" - ডানদিকে. সম্পূর্ণ গাছে N পাতা এবং এন-1 অভ্যন্তরীণ নোড। এটি সুপারিশ করা হয় যে একটি হাফম্যান গাছ তৈরি করার সময়, সর্বোত্তম দৈর্ঘ্যের কোডগুলি পেতে অব্যবহৃত চিহ্নগুলি বাতিল করা হবে৷

আমরা একটি হাফম্যান ট্রি তৈরি করতে একটি অগ্রাধিকার সারি ব্যবহার করব, যেখানে সর্বনিম্ন ফ্রিকোয়েন্সি সহ নোডকে সর্বোচ্চ অগ্রাধিকার দেওয়া হবে। নির্মাণের ধাপগুলি নীচে বর্ণনা করা হয়েছে:

1. প্রতিটি অক্ষরের জন্য একটি লিফ নোড তৈরি করুন এবং তাদের অগ্রাধিকার সারিতে যুক্ত করুন।
2. সারিতে একাধিক শীট থাকাকালীন, নিম্নলিখিতগুলি করুন:
   • সারি থেকে সর্বোচ্চ অগ্রাধিকার (সর্বনিম্ন ফ্রিকোয়েন্সি) সহ দুটি নোড সরান;
   • একটি নতুন অভ্যন্তরীণ নোড তৈরি করুন, যেখানে এই দুটি নোড শিশু হবে এবং সংঘটনের ফ্রিকোয়েন্সি এই দুটি নোডের ফ্রিকোয়েন্সির যোগফলের সমান হবে।
   • অগ্রাধিকার সারিতে একটি নতুন নোড যোগ করুন।
3. একমাত্র অবশিষ্ট নোডটি মূল হবে এবং এটি গাছের নির্মাণ সম্পূর্ণ করবে।

কল্পনা করুন যে আমাদের এমন কিছু পাঠ্য রয়েছে যা শুধুমাত্র অক্ষর নিয়ে গঠিত "এ বি সি ডি" и "এবং", এবং তাদের সংঘটন ফ্রিকোয়েন্সি যথাক্রমে 15, 7, 6, 6 এবং 5। নীচের চিত্রগুলি অ্যালগরিদমের ধাপগুলিকে প্রতিফলিত করে৷

রুট থেকে যেকোন এন্ড নোড পর্যন্ত একটি পাথ সেই শেষ নোডের সাথে যুক্ত অক্ষরের সাথে সম্পর্কিত সর্বোত্তম উপসর্গ কোড (হাফম্যান কোড নামেও পরিচিত) সংরক্ষণ করবে।

হাফম্যান গাছ

নীচে আপনি C++ এবং জাভাতে হাফম্যান কম্প্রেশন অ্যালগরিদমের বাস্তবায়ন পাবেন:

#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(লগ(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