قبل بدء الدورة أعدت لك ترجمة لمواد أخرى مفيدة.
ترميز هوفمان هو خوارزمية لضغط البيانات تصوغ الفكرة الأساسية لضغط الملفات. في هذه المقالة ، سنتحدث عن ترميز الطول الثابت والمتغير ، والأكواد القابلة للفك بشكل فريد ، وقواعد البادئة ، وبناء شجرة هوفمان.
نحن نعلم أن كل حرف يتم تخزينه على شكل تسلسل من 0 و 1 ويستهلك 8 بتات. يسمى هذا ترميز الطول الثابت لأن كل حرف يستخدم نفس العدد الثابت من البتات لتخزينه.
لنفترض أن لدينا نصًا. كيف يمكننا تقليل مقدار المساحة المطلوبة لتخزين حرف واحد؟
الفكرة الرئيسية هي ترميز متغير الطول. يمكننا استخدام حقيقة أن بعض الأحرف في النص تتكرر أكثر من غيرها () لتطوير خوارزمية تمثل نفس تسلسل الأحرف في وحدات بت أقل. في الترميز المتغير الطول ، نقوم بتعيين الأحرف عددًا متغيرًا من البتات ، اعتمادًا على عدد مرات ظهورها في نص معين. في النهاية ، قد تستغرق بعض الأحرف أقل من 1 بت ، بينما قد يستغرق البعض الآخر 2 بت أو 3 أو أكثر. مشكلة التشفير المتغير الطول هي فقط فك التشفير اللاحق للتسلسل.
كيف ، بمعرفة تسلسل البتات ، فك تشفيرها بشكل لا لبس فيه؟
ضع في اعتبارك الخط "اباكداب". يتكون من 8 أحرف ، وعند ترميز طول ثابت ، ستحتاج إلى 64 بت لتخزينه. لاحظ أن تردد الرمز "أ" ، "ب" ، "ج" и "د" يساوي 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
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 على التوالي. فيما يلي الرسوم التوضيحية التي تعكس خطوات الخوارزمية.
سيخزن المسار من الجذر إلى أي عقدة نهائية رمز البادئة الأمثل (المعروف أيضًا باسم كود هوفمان) المقابل للحرف المرتبط بعقدة النهاية هذه.
شجرة هوفمان
ستجد أدناه تطبيق خوارزمية ضغط Huffman في 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 (تسجيل (N)) الوقت ، ولكن في شجرة ثنائية كاملة مع N يترك موجودة 2N-1 العقد ، وشجرة هوفمان عبارة عن شجرة ثنائية كاملة ، ثم تعمل الخوارزمية O (Nlog (N)) الوقت وأين N - الشخصيات.
مصادر:
المصدر: www.habr.com