ڪورس جي شروعات کان اڳ توهان لاءِ تيار ڪيل هڪ ٻي مفيد مواد جو ترجمو.
Huffman ڪوڊنگ هڪ ڊيٽا ڪمپريشن الگورٿم آهي جيڪو فائل ڪمپريشن جي بنيادي خيال کي ترتيب ڏئي ٿو. هن آرٽيڪل ۾، اسان مقرر ۽ متغير ڊگھي انڪوڊنگ بابت ڳالهائينداسين، منفرد طور تي ڊيڪوڊ ايبل ڪوڊس، پريفڪس ضابطا، ۽ هفمن وڻ جي تعمير.
اسان ڄاڻون ٿا ته هر ڪردار 0 ۽ 1 جي ترتيب جي طور تي ذخيرو ٿيل آهي ۽ 8 بٽ وٺي ٿو. ھن کي فڪسڊ ڊگھي انڪوڊنگ چئبو آھي ڇاڪاڻ ته ھر ڪردار ذخيرو ڪرڻ لاءِ بِٽ جو ساڳيو مقرر تعداد استعمال ڪندو آھي.
اچو ته اسان کي متن ڏنو ويو آهي. اسان هڪ واحد ڪردار کي ذخيرو ڪرڻ لاء گهربل جاء جي مقدار کي ڪيئن گھٽائي سگهون ٿا؟
مکيه خيال متغير لمبائي انڪوڊنگ آهي. اسان هن حقيقت کي استعمال ڪري سگهون ٿا ته متن ۾ ڪجهه اکر ٻين جي ڀيٽ ۾ وڌيڪ اڪثر ٿين ٿا () هڪ الگورٿم کي ترقي ڪرڻ لاء جيڪو گهٽ بٽ ۾ ڪردارن جي ساڳئي ترتيب جي نمائندگي ڪندو. متغير ڊگھائي انڪوڊنگ ۾، اسان اکرن کي تفويض ڪريون ٿا بٽس جو متغير تعداد، ان تي منحصر ڪري ٿو ته اهي ڏنل متن ۾ ڪيترا ڀيرا ظاهر ٿين ٿا. آخرڪار، ڪجهه ڪردارن کي 1 بٽ جيترو وٺي سگھي ٿو، جڏهن ته ٻيا 2 بٽ، 3 يا وڌيڪ وٺي سگھن ٿا. متغير ڊگھي انڪوڊنگ سان مسئلو صرف تسلسل جي بعد ۾ ڊيڪوڊنگ آهي.
ڪيئن، بٽ جي ترتيب کي ڄاڻڻ، ان کي غير واضح طور تي ڊيڪوڊ ڪيو؟
لڪير تي غور ڪريو "ابتداب". ان ۾ 8 اکر آھن، ۽ جڏھن ھڪ مقرر ڊگھائي انڪوڊنگ ڪري، ان کي ذخيرو ڪرڻ لاءِ 64 بِٽ جي ضرورت پوندي. نوٽ ڪريو ته علامت تعدد "a"، "b"، "c" и "ڊي" برابر 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"، "b"، "c" и "ڊي" رموز جيڪي اڳياڙي واري قاعدي کي پورو ڪن ٿا.
a
0
b
10
c
110
d
111
هن انڪوڊنگ سان، تار "ابتداب" جي طور تي انڪوڊ ڪيو ويندو 00100100011010 (0|0|10|0|100|011|0|10). ۽ هتي 00100100011010 اسان اڳ ۾ ئي غير واضح طور تي ڊيڪوڊ ڪرڻ ۽ اسان جي اصل اسٽرنگ ڏانهن موٽڻ جي قابل هوندا "ابتداب".
Huffman ڪوڊنگ
ھاڻي ته اسان متغير ڊگھي انڪوڊنگ ۽ اڳياڙي واري قاعدي سان ڳالھايو آھي، اچو ته ھفمن انڪوڊنگ جي باري ۾ ڳالهايون.
طريقو بائنري وڻن جي پيدائش تي ٻڌل آهي. ان ۾، نوڊ يا ته حتمي يا اندروني ٿي سگهي ٿو. شروعات ۾، سڀني نوڊس کي پنن (ٽرمينلز) سمجهيا وڃن ٿا، جيڪي علامت پاڻ ۽ ان جي وزن جي نمائندگي ڪن ٿا (يعني، واقعن جي تعدد). اندروني نوڊس ڪردار جي وزن تي مشتمل آهي ۽ ٻه نسلي نوڊس ڏانهن اشارو ڪن ٿا. عام اتفاق سان، بٽ "0" نمائندگي ڪري ٿو ھيٺئين کاٻي شاخ، ۽ "1" - ساڄي پاسي. مڪمل وڻ ۾ N پنن ۽ اين ايڪس اينڪس اندروني نوڊس. اها سفارش ڪئي وئي آهي ته جڏهن هڪ هفمن وڻ ٺاهي، غير استعمال ٿيل نشانين کي رد ڪيو وڃي ته بهتر ڊگھائي ڪوڊ حاصل ڪرڻ لاء.
اسان ھفمن وڻ جي تعمير لاء ترجيحي قطار استعمال ڪنداسين، جتي نوڊ تمام گھٽ تعدد سان اعلي ترجيح ڏني ويندي. تعميراتي قدم هيٺ بيان ڪيا ويا آهن:
- ھر ڪردار لاءِ ليف نوڊ ٺاھيو ۽ انھن کي ترجيحي قطار ۾ شامل ڪريو.
- جڏهن ته قطار ۾ هڪ کان وڌيڪ شيٽ آهي، هيٺيان ڪريو:
- ٻن نوڊس کي هٽايو سڀ کان وڌيڪ ترجيح سان (سڀ کان گھٽ تعدد) قطار مان؛
- هڪ نئون اندروني نوڊ ٺاهيو، جتي اهي ٻه نوڊ ٻار هوندا، ۽ واقع ٿيڻ جي تعدد انهن ٻن نوڊس جي تعدد جي رقم جي برابر هوندي.
- اوليت واري قطار ۾ نئون نوڊ شامل ڪريو.
- صرف باقي بچيل نوڊ روٽ ٿيندو، ۽ اھو وڻ جي تعمير مڪمل ڪندو.
تصور ڪريو ته اسان وٽ ڪجھ متن آھي جيڪو صرف اکرن تي مشتمل آھي "اي بي سي ڊي" и "۽"، ۽ انهن جي واقعن جي تعدد 15، 7، 6، 6، ۽ 5 آهن، ترتيب سان. هيٺ ڏنل نمونا آهن جيڪي الورورٿم جي مرحلن کي ظاهر ڪن ٿا.
روٽ کان ڪنهن به آخري نوڊ تائين هڪ رستو بهترين پريفڪس ڪوڊ (جنهن کي Huffman ڪوڊ جي نالي سان پڻ سڃاتو وڃي ٿو) ذخيرو ڪندو جيڪو انهي آخري نوڊ سان لاڳاپيل ڪردار سان لاڳاپيل هوندو.
Huffman وڻ
هيٺ توهان کي 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++ پروگرام ۾، اسان انڪوڊ ٿيل اسٽرنگ کي ذخيرو ڪرڻ لاءِ اسٽرنگ ڪلاس استعمال ڪندا آهيون ته جيئن پروگرام کي پڙهڻ لائق بڻائي سگهجي.
ڇاڪاڻ ته موثر ترجيحي قطار ڊيٽا جي جوڙجڪ جي ضرورت هوندي آهي هر داخل ٿيڻ جي او (لاگ (ن)) وقت، پر هڪ مڪمل بائنري وڻ ۾ N پتا موجود آهن 2N-1 نوڊس، ۽ Huffman وڻ هڪ مڪمل بائنري وڻ آهي، پوء الورورٿم اندر هلندو آهي O(Nlog(N)) وقت، ڪٿي N - ڪردار.
ذريعن:
جو ذريعو: www.habr.com