TechCodeview

قد يتم ضغط البيانات باستخدام تقنية هوفمان للترميز لتصبح أصغر حجمًا دون فقدان أي من معلوماتها. بعد ديفيد هوفمان، من الذي أنشأها في البداية؟ عادةً ما يتم ضغط البيانات التي تحتوي على أحرف متكررة باستخدام ترميز هوفمان.

إحدى خوارزميات الجشع المعروفة هي ترميز هوفمان. يعتمد حجم الكود المخصص للحرف على تكرار الحرف، ولهذا السبب يشار إليه على أنه خوارزمية جشعة. يتم تعيين رمز متغير قصير الطول للحرف ذو التردد الأعلى، والعكس صحيح للحروف ذات الترددات الأقل. ويستخدم تشفيرًا متغير الطول، مما يعني أنه يمنح كل حرف في تدفق البيانات المقدم رمزًا مختلفًا متغير الطول.

قاعدة البادئة

بشكل أساسي، تنص هذه القاعدة على أن الكود المخصص للحرف لا يجب أن يكون بادئة لرمز آخر. إذا تم كسر هذه القاعدة، فقد تظهر العديد من الغموض عند فك تشفير شجرة هوفمان التي تم إنشاؤها.

دعونا نلقي نظرة على رسم توضيحي لهذه القاعدة لفهمها بشكل أفضل: يتم توفير رمز لكل حرف، مثل:

 a - 0 b - 1 c - 01 

بافتراض أن تدفق البتات المنتج هو 001، يمكن التعبير عن الشفرة على النحو التالي عند فك التشفير:

 0 0 1 = aab 0 01 = ac 

ما هي عملية ترميز هوفمان؟

numpy linspace

يتم الحصول على كود هوفمان لكل شخصية مميزة في خطوتين أساسيتين:

• أنشئ شجرة هوفمان أولاً باستخدام الأحرف الفريدة الموجودة في دفق البيانات المقدم فقط.
• ثانيًا، يجب علينا المتابعة عبر شجرة هوفمان التي تم إنشاؤها، وتعيين رموز للشخصيات، ثم استخدام تلك الرموز لفك تشفير النص المقدم.

خطوات يجب اتباعها في ترميز هوفمان

الخطوات المستخدمة لبناء شجرة هوفمان باستخدام الأحرف المتوفرة

 Input: string str = 'abbcdbccdaabbeeebeab' 

إذا تم استخدام تشفير هوفمان في هذه الحالة لضغط البيانات، فيجب تحديد المعلومات التالية لفك التشفير:

• لكل شخصية، كود هوفمان
• طول الرسالة المشفرة بواسطة هوفمان (بالبت)، متوسط ​​طول الكود
• باستخدام الصيغ الموضحة أدناه، يتم اكتشاف الصيغتين الأخيرتين.

كيف يمكن بناء شجرة هوفمان من أحرف الإدخال؟

يجب أولاً تحديد تكرار كل حرف في السلسلة المتوفرة.

1. فرز الأحرف حسب التردد، تصاعديا. يتم الاحتفاظ بها في قائمة انتظار أولوية Q/min-heap.
2. لكل حرف مميز وتكراره في دفق البيانات، قم بإنشاء عقدة طرفية.
3. قم بإزالة العقدتين اللتين تحتويان على أقل ترددين من العقد، ويتم إنشاء الجذر الجديد للشجرة باستخدام مجموع هذه الترددات.
   • اجعل العقدة المستخرجة الأولى طفلها الأيسر والعقدة المستخرجة الثانية طفلها الأيمن أثناء استخراج العقد ذات التردد الأقل من الكومة الصغيرة.
   • إلى الكومة الصغيرة، أضف هذه العقدة.
   • نظرًا لأن الجانب الأيسر من الجذر يجب أن يحتوي دائمًا على الحد الأدنى من التردد.
4. كرر الخطوتين 3 و4 حتى تبقى عقدة واحدة فقط في الكومة، أو يتم تمثيل كافة الأحرف بواسطة العقد في الشجرة. تنتهي الشجرة عندما تبقى العقدة الجذرية فقط.

أمثلة على ترميز هوفمان

دعونا نستخدم الرسم التوضيحي لشرح الخوارزمية:

خوارزمية لترميز هوفمان

الخطوة 1: أنشئ كومة صغيرة تمثل فيها كل عقدة جذر شجرة ذات عقدة واحدة وتحمل 5 (عدد الأحرف الفريدة من دفق البيانات المقدم).

الخطوة 2: احصل على عقدتي تردد أدنى من الكومة الدقيقة في الخطوة الثانية. أضف عقدة داخلية ثالثة، التردد 2 + 3 = 5، والتي يتم إنشاؤها عن طريق ضم العقدتين المستخرجتين.

• الآن، هناك 4 عقد في الكومة الصغيرة، 3 منها هي جذور الأشجار التي تحتوي كل منها على عنصر واحد، وواحدة منها هي جذر شجرة تحتوي على عنصرين.

الخطوه 3: احصل على عقدتي التردد الأدنى من الكومة بطريقة مماثلة في الخطوة الثالثة. بالإضافة إلى ذلك، قم بإضافة عقدة داخلية جديدة يتم تشكيلها من خلال ضم العقدتين المستخرجتين؛ يجب أن يكون تردده في الشجرة 4 + 4 = 8.

• الآن بعد أن أصبح الحد الأدنى من الكومة يحتوي على ثلاث عقد، تعمل عقدة واحدة كجذر للأشجار ذات عنصر واحد وعقدتين من الكومة تعملان كجذر للأشجار ذات عقد متعددة.

الخطوة 4: احصل على عقدتي التردد الأدنى في الخطوة الرابعة. بالإضافة إلى ذلك، قم بإضافة عقدة داخلية جديدة تم تشكيلها من خلال ضم العقدتين المستخرجتين؛ يجب أن يكون تردده في الشجرة 5 + 7 = 12.

• عند إنشاء شجرة هوفمان، يجب علينا التأكد من أن القيمة الدنيا تكون دائمًا على الجانب الأيسر وأن القيمة الثانية تكون دائمًا على الجانب الأيمن. حاليًا، الصورة أدناه توضح الشجرة التي تشكلت:

الخطوة 5: احصل على عقدتي التردد الأدنى التاليتين في الخطوة 5. بالإضافة إلى ذلك، قم بإضافة عقدة داخلية جديدة تم تشكيلها من خلال ضم العقدتين المستخرجتين؛ يجب أن يكون تردده في الشجرة 12 + 8 = 20.

استمر حتى تتم إضافة كافة الأحرف المميزة إلى الشجرة. تظهر شجرة هوفمان التي تم إنشاؤها لمجموعة الشخصيات المحددة في الصورة أعلاه.

الآن، لكل عقدة غير ورقية، قم بتعيين 0 للحافة اليسرى و1 للحافة اليمنى لإنشاء الكود لكل حرف.

القواعد الواجب اتباعها لتحديد أوزان الحواف:

• يجب أن نعطي وزن الحواف اليمنى 1 إذا أعطيت وزن الحواف اليسرى 0.
• إذا أعطيت الحواف اليسرى وزنًا 1، فيجب إعطاء وزن الحواف اليمنى 0.
• ويجوز استخدام أي من الاتفاقيتين المذكورتين.
• ومع ذلك، اتبع نفس البروتوكول عند فك تشفير الشجرة أيضًا.

بعد الترجيح تظهر الشجرة المعدلة كما يلي:

فهم الكود

• يجب أن نمر عبر شجرة هوفمان حتى نصل إلى العقدة الورقية، حيث يتواجد العنصر، وذلك لفك شفرة هوفمان لكل حرف من شجرة هوفمان الناتجة.
• يجب تسجيل الأوزان عبر العقد أثناء الاجتياز وتخصيصها للعناصر الموجودة في العقدة الطرفية المحددة.
• سيساعد المثال التالي في توضيح ما نعنيه بشكل أكبر:
• للحصول على الكود الخاص بكل حرف في الصورة أعلاه، يجب علينا السير على الشجرة بأكملها (حتى يتم تغطية جميع العقد الورقية).
• ونتيجة لذلك، يتم استخدام الشجرة التي تم إنشاؤها لفك رموز كل عقدة. فيما يلي قائمة بالرموز الخاصة بكل حرف:

فيما يلي التنفيذ في برمجة C:

 // C program for Huffman Coding #include #include // This constant can be avoided by explicitly // calculating height of Huffman Tree #define MAX_TREE_HT 100 // A Huffman tree node struct MinHeapNode { // One of the input characters char data; // Frequency of the character unsigned freq; // Left and right child of this node struct MinHeapNode *left, *right; }; // A Min Heap: Collection of // min-heap (or Huffman tree) nodes struct MinHeap { // Current size of min heap unsigned size; // capacity of min heap unsigned capacity; // Array of minheap node pointers struct MinHeapNode** array; }; // A utility function allocate a new // min heap node with given character // and frequency of the character struct MinHeapNode* newNode(char data, unsigned freq) { struct MinHeapNode* temp = (struct MinHeapNode*)malloc( sizeof(struct MinHeapNode)); temp->left = temp->right = NULL; temp->data = data; temp->freq = freq; return temp; } // A utility function to create // a min heap of given capacity struct MinHeap* createMinHeap(unsigned capacity) { struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap)); // current size is 0 minHeap->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHeapNode**)malloc( minHeap->capacity * sizeof(struct MinHeapNode*)); return minHeap; } // A utility function to // swap two min heap nodes void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) { struct MinHeapNode* t = *a; *a = *b; *b = t; } // The standard minHeapify function. void minHeapify(struct MinHeap* minHeap, int idx) { int smallest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2; if (left size && minHeap->array[left]->freq array[smallest]->freq) smallest = left; if (right size && minHeap->array[right]->freq array[smallest]->freq) smallest = right; if (smallest != idx) { swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); minHeapify(minHeap, smallest); } } // A utility function to check // if size of heap is 1 or not int isSizeOne(struct MinHeap* minHeap) { return (minHeap->size == 1); } // A standard function to extract // minimum value node from heap struct MinHeapNode* extractMin(struct MinHeap* minHeap) { struct MinHeapNode* temp = minHeap->array[0]; minHeap->array[0] = minHeap->array[minHeap->size - 1]; --minHeap->size; minHeapify(minHeap, 0); return temp; } // A utility function to insert // a new node to Min Heap void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) { ++minHeap->size; int i = minHeap->size - 1; while (i && minHeapNode->freq array[(i - 1) / 2]->freq) { minHeap->array[i] = minHeap->array[(i - 1) / 2]; i = (i - 1) / 2; } minHeap->array[i] = minHeapNode; } // A standard function to build min heap void buildMinHeap(struct MinHeap* minHeap) { int n = minHeap->size - 1; int i; for (i = (n - 1) / 2; i >= 0; --i) minHeapify(minHeap, i); } // A utility function to print an array of size n void printArr(int arr[], int n) { int i; for (i = 0; i left) && !(root->right); } // Creates a min heap of capacity // equal to size and inserts all character of // data[] in min heap. Initially size of // min heap is equal to capacity struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // The main function that builds Huffman tree struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Step 1: Create a min heap of capacity // equal to size. Initially, there are // modes equal to size. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Iterate while size of heap doesn't become 1 while (!isSizeOne(minHeap)) { // Step 2: Extract the two minimum // freq items from min heap left = extractMin(minHeap); right = extractMin(minHeap); // Step 3: Create a new internal // node with frequency equal to the // sum of the two nodes frequencies. // Make the two extracted node as // left and right children of this new node. // Add this node to the min heap // '$' is a special value for internal nodes, not // used top = newNode('$', left->freq + right->freq); top->left = left; top->right = right; insertMinHeap(minHeap, top); } // Step 4: The remaining node is the // root node and the tree is complete. return extractMin(minHeap); } // Prints huffman codes from the root of Huffman Tree. // It uses arr[] to store codes void printCodes(struct MinHeapNode* root, int arr[], int top) { // Assign 0 to left edge and recur if (root->left) { arr[top] = 0; printCodes(root->left, arr, top + 1); } // Assign 1 to right edge and recur if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // If this is a leaf node, then // it contains one of the input // characters, print the character // and its code from arr[] if (isLeaf(root)) { printf('%c: ', root->data); printArr(arr, top); } } // The main function that builds a // Huffman Tree and print codes by traversing // the built Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree(data, freq, size); // Print Huffman codes using // the Huffman tree built above int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Driver code int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16, 45 }; int size = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, freq, size); return 0; } 

انتاج |

 f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 …………… Process executed in 1.11 seconds Press any key to continue. 

تنفيذ جافا للكود أعلاه:

 import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; class Huffman { // recursive function to print the // huffman-code through the tree traversal. // Here s is the huffman - code generated. public static void printCode(HuffmanNode root, String s) { // base case; if the left and right are null // then its a leaf node and we print // the code s generated by traversing the tree. if (root.left == null &amp;&amp; root.right == null &amp;&amp; Character.isLetter(root.c)) { // c is the character in the node System.out.println(root.c + &apos;:&apos; + s); return; } // if we go to left then add &apos;0&apos; to the code. // if we go to the right add&apos;1&apos; to the code. // recursive calls for left and // right sub-tree of the generated tree. printCode(root.left, s + &apos;0&apos;); printCode(root.right, s + &apos;1&apos;); } // main function public static void main(String[] args) { Scanner s = new Scanner(System.in); // number of characters. int n = 6; char[] charArray = { &apos;a&apos;, &apos;b&apos;, &apos;c&apos;, &apos;d&apos;, &apos;e&apos;, &apos;f&apos; }; int[] charfreq = { 5, 9, 12, 13, 16, 45 }; // creating a priority queue q. // makes a min-priority queue(min-heap). PriorityQueue q = new PriorityQueue( n, new MyComparator()); for (int i = 0; i <n; i++) { creating a huffman node object and add it to the priority queue. huffmannode hn="new" huffmannode(); hn.c="charArray[i];" hn.data="charfreq[i];" hn.left="null;" hn.right="null;" functions adds q.add(hn); } create root here we will extract two minimum value from heap each time until its size reduces 1, all nodes are extracted. while (q.size()> 1) { // first min extract. HuffmanNode x = q.peek(); q.poll(); // second min extract. HuffmanNode y = q.peek(); q.poll(); // new node f which is equal HuffmanNode f = new HuffmanNode(); // to the sum of the frequency of the two nodes // assigning values to the f node. f.data = x.data + y.data; f.c = &apos;-&apos;; // first extracted node as left child. f.left = x; // second extracted node as the right child. f.right = y; // marking the f node as the root node. root = f; // add this node to the priority-queue. q.add(f); } // print the codes by traversing the tree printCode(root, &apos;&apos;); } } // node class is the basic structure // of each node present in the Huffman - tree. class HuffmanNode { int data; char c; HuffmanNode left; HuffmanNode right; } // comparator class helps to compare the node // on the basis of one of its attribute. // Here we will be compared // on the basis of data values of the nodes. class MyComparator implements Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } </n;>

انتاج |

 f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 ………………. Process executed in 1.11 seconds Press any key to continue. 

توضيح:

من خلال العبور، يتم إنشاء شجرة هوفمان وفك تشفيرها. سيتم بعد ذلك تطبيق القيم التي تم جمعها أثناء الاجتياز على الحرف الموجود في العقدة الطرفية. يمكن تحديد كل حرف فريد في تدفق البيانات المقدم باستخدام كود هوفمان بهذه الطريقة. O (nlogn)، حيث n هو العدد الإجمالي للأحرف، وهو التعقيد الزمني. يتم استدعاء ExtractMin() 2*(n - 1) مرات إذا كان هناك n عقد. نظرًا لأن extractMin() يستدعي minHeapify()، فإن وقت التنفيذ هو O (تسجيل الدخول). وبالتالي فإن التعقيد الكلي هو O (nlogn). توجد خوارزمية زمنية خطية إذا تم فرز مصفوفة الإدخال. سيتم تغطية هذا بمزيد من التفصيل في مقالتنا القادمة.

مشاكل مع ترميز هوفمان

دعونا نتحدث عن عيوب ترميز هوفمان في هذا الجزء ولماذا لا يكون الخيار الأفضل دائمًا:

• إذا لم تكن كل احتمالات الشخصيات أو تردداتها هي قوى سالبة للعدد 2، فلا تعتبر مثالية.
• على الرغم من أن المرء قد يقترب من المثالية من خلال تجميع الرموز وتوسيع الأبجدية، إلا أن طريقة الحجب تتطلب التعامل مع أبجدية أكبر. لذلك، قد لا يكون ترميز هوفمان فعالاً دائمًا.
• على الرغم من وجود العديد من الطرق الفعالة لحساب تكرار كل رمز أو حرف، إلا أن إعادة بناء الشجرة بأكملها لكل رمز يمكن أن تستغرق وقتًا طويلاً. عندما تكون الأبجدية كبيرة وتتغير التوزيعات الاحتمالية بسرعة مع كل رمز، فهذا هو الحال عادةً.

خوارزمية بناء كود هوفمان الجشع

• طور هوفمان تقنية جشعة تولد رمز هوفمان، وهو رمز بادئة مثالي، لكل حرف مميز في تدفق بيانات الإدخال.
• يستخدم هذا النهج أقل عدد من العقد في كل مرة لإنشاء شجرة هوفمان من الأسفل إلى الأعلى.
• نظرًا لأن كل حرف يتلقى طولًا من التعليمات البرمجية بناءً على عدد مرات ظهوره في دفق البيانات المحدد، تُعرف هذه الطريقة بالنهج الجشع. وهو عنصر شائع الحدوث في البيانات إذا كان حجم الكود المسترد أقل.

استخدام ترميز هوفمان

• سنتحدث هنا عن بعض الاستخدامات العملية لبرمجة هوفمان:
• عادةً ما تستخدم تنسيقات الضغط التقليدية مثل PKZIP وGZIP وما إلى ذلك ترميز Huffman.
• يتم استخدام ترميز هوفمان لنقل البيانات عن طريق الفاكس والنص لأنه يقلل من حجم الملف ويزيد من سرعة الإرسال.
• يتم استخدام ترميز هوفمان (خاصة رموز البادئة) بواسطة العديد من تنسيقات تخزين الوسائط المتعددة، بما في ذلك JPEG وPNG وMP3، لضغط الملفات.
• يستخدم ترميز هوفمان في الغالب لضغط الصور.
• عندما يلزم إرسال سلسلة من الأحرف المتكررة، فقد يكون ذلك أكثر فائدة.

خاتمة

• بشكل عام، يعد Huffman Coding مفيدًا لضغط البيانات التي تحتوي على أحرف متكررة.
• يمكننا أن نرى أن الحرف الذي يتكرر بشكل متكرر لديه الرمز الأقصر، في حين أن الحرف الذي يتكرر بشكل أقل لديه الرمز الأكبر.
• يتم استخدام تقنية ضغط كود هوفمان لإنشاء ترميز متغير الطول، والذي يستخدم كمية متنوعة من البتات لكل حرف أو رمز. تتفوق هذه الطريقة على التشفير ذو الطول الثابت لأنها تستخدم ذاكرة أقل وتنقل البيانات بسرعة أكبر.
• انتقل إلى هذه المقالة للحصول على معرفة أفضل بالخوارزمية الجشعة.