کورس کے آغاز سے پہلے آپ کے لیے ایک اور مفید مواد کا ترجمہ تیار ہے۔
ہف مین کوڈنگ ایک ڈیٹا کمپریشن الگورتھم ہے جو فائل کمپریشن کا بنیادی خیال تیار کرتا ہے۔ اس مضمون میں، ہم فکسڈ اور متغیر لمبائی کی انکوڈنگ، منفرد طور پر ڈیکوڈ ایبل کوڈز، سابقہ اصول، اور ہف مین ٹری بنانے کے بارے میں بات کریں گے۔
ہم جانتے ہیں کہ ہر کریکٹر 0 اور 1 کی ترتیب کے طور پر محفوظ ہوتا ہے اور 8 بٹس لیتا ہے۔ اسے فکسڈ لینتھ انکوڈنگ کہا جاتا ہے کیونکہ ہر کریکٹر ذخیرہ کرنے کے لیے بٹس کی ایک ہی مقررہ تعداد کا استعمال کرتا ہے۔
ہم کہتے ہیں کہ ہمارے پاس ایک متن ہے۔ ہم ایک ہی کردار کو ذخیرہ کرنے کے لیے درکار جگہ کی مقدار کو کیسے کم کر سکتے ہیں؟
اہم خیال متغیر لمبائی کی انکوڈنگ ہے۔ ہم اس حقیقت کو استعمال کرسکتے ہیں کہ متن میں کچھ حروف دوسروں کے مقابلے میں زیادہ کثرت سے پائے جاتے ہیں () ایک الگورتھم تیار کرنے کے لئے جو کم بٹس میں حروف کی ایک ہی ترتیب کی نمائندگی کرے گا۔ متغیر لمبائی کی انکوڈنگ میں، ہم حروف کو بٹس کی متغیر تعداد تفویض کرتے ہیں، اس بات پر منحصر ہے کہ وہ دیئے گئے متن میں کتنی بار ظاہر ہوتے ہیں۔ آخر کار، کچھ حروف صرف 1 بٹ لے سکتے ہیں، جبکہ دیگر 2 بٹس، 3 یا اس سے زیادہ لے سکتے ہیں۔ متغیر لمبائی کی انکوڈنگ کے ساتھ مسئلہ صرف ترتیب کے بعد کی ضابطہ کشائی ہے۔
بٹس کی ترتیب کو جانتے ہوئے، اسے غیر واضح طور پر ڈی کوڈ کیسے کریں؟
لائن پر غور کریں۔ "ابقداب". اس میں 8 حروف ہیں، اور ایک مقررہ لمبائی کو انکوڈنگ کرتے وقت، اسے ذخیرہ کرنے کے لیے 64 بٹس کی ضرورت ہوگی۔ نوٹ کریں کہ علامت تعدد "a"، "b"، "c" и "ڈی" بالترتیب 4، 2، 1، 1 کے برابر ہے۔ آئیے تصور کرنے کی کوشش کریں۔ "ابقداب" کم بٹس، اس حقیقت کا استعمال کرتے ہوئے "سے" سے زیادہ کثرت سے ہوتا ہے۔ "بی"اور "بی" سے زیادہ کثرت سے ہوتا ہے۔ "c" и "ڈی". آئیے کوڈنگ سے شروع کریں۔ "سے" 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"، "b"، "c" и "ڈی" کوڈز جو سابقہ اصول کو پورا کرتے ہیں۔
a
0
b
10
c
110
d
111
اس انکوڈنگ کے ساتھ، تار "ابقداب" کے طور پر انکوڈ کیا جائے گا۔ 00100100011010 (0|0|10|0|100|011|0|10). اور یہاں۔ 00100100011010 ہم پہلے ہی غیر واضح طور پر ڈی کوڈ کرنے اور اپنی اصل سٹرنگ پر واپس آنے کے قابل ہو جائیں گے۔ "ابقداب".
ہف مین کوڈنگ
اب جب کہ ہم نے متغیر لمبائی کی انکوڈنگ اور سابقہ اصول سے نمٹا ہے، آئیے ہف مین انکوڈنگ کے بارے میں بات کرتے ہیں۔
طریقہ بائنری درختوں کی تخلیق پر مبنی ہے۔ اس میں، نوڈ یا تو حتمی یا اندرونی ہو سکتا ہے. ابتدائی طور پر، تمام نوڈس کو پتے (ٹرمینلز) تصور کیا جاتا ہے، جو خود علامت اور اس کے وزن (یعنی وقوع پذیر ہونے کی تعدد) کی نمائندگی کرتے ہیں۔ اندرونی نوڈس میں کردار کا وزن ہوتا ہے اور دو نسلی نوڈس کا حوالہ دیتے ہیں۔ عام معاہدے کی طرف سے، بٹ «0» بائیں شاخ کے بعد کی نمائندگی کرتا ہے، اور «1» - حق پر. پورے درخت میں N پتے اور N 1 اندرونی نوڈس. یہ سفارش کی جاتی ہے کہ ہف مین ٹری بناتے وقت، زیادہ سے زیادہ لمبائی والے کوڈ حاصل کرنے کے لیے غیر استعمال شدہ علامتوں کو ضائع کر دیا جائے۔
ہم ہف مین ٹری بنانے کے لیے ترجیحی قطار استعمال کریں گے، جہاں سب سے کم فریکوئنسی والے نوڈ کو سب سے زیادہ ترجیح دی جائے گی۔ تعمیراتی مراحل ذیل میں بیان کیے گئے ہیں:
- ہر کردار کے لیے ایک لیف نوڈ بنائیں اور انہیں ترجیحی قطار میں شامل کریں۔
- جب کہ قطار میں ایک سے زیادہ شیٹ ہیں، درج ذیل کام کریں:
- قطار سے سب سے زیادہ ترجیح (سب سے کم تعدد) والے دو نوڈس کو ہٹا دیں۔
- ایک نیا اندرونی نوڈ بنائیں، جہاں یہ دونوں نوڈس چائلڈ ہوں گے، اور وقوع پذیر ہونے کی فریکوئنسی ان دو نوڈس کی فریکوئنسی کے مجموعے کے برابر ہوگی۔
- ترجیحی قطار میں ایک نیا نوڈ شامل کریں۔
- صرف باقی نوڈ جڑ ہو گا، اور یہ درخت کی تعمیر کو مکمل کرے گا.
تصور کریں کہ ہمارے پاس کچھ متن ہے جو صرف حروف پر مشتمل ہے۔ "اے، بی، سی، ڈی" и "اور"، اور ان کی موجودگی کی تعدد بالترتیب 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(log(N)) وقت، لیکن کے ساتھ ایک مکمل بائنری درخت میں N پتے موجود ہیں 2N-1 نوڈس، اور Huffman درخت ایک مکمل بائنری درخت ہے، پھر الگورتھم چلتا ہے۔ O(Nlog(N)) وقت، کہاں N - کردار
ذرائع کے مطابق:
ماخذ: www.habr.com