تم اقتراح خوارزمية هوفمان للترميز بواسطة ديفيد أ. هوفمان في عام 1950. وهو ضغط البيانات بدون فقدان آلية. ومن المعروف أيضا باسم ترميز ضغط البيانات. يستخدم على نطاق واسع في ضغط الصور (JPEG أو JPG). في هذا القسم سنناقش ترميز هوفمان و فك التشفير, وأيضًا تنفيذ الخوارزمية الخاصة به في برنامج Java.

نحن نعلم أن كل حرف عبارة عن سلسلة من 0 و1 ويتم تخزينه باستخدام 8 بت. تسمى الآلية ترميز ذو طول ثابت لأن كل حرف يستخدم نفس عدد وحدات تخزين البت الثابتة.

باوانديب راجان

وهنا يبرز سؤال هل من الممكن تقليل مقدار المساحة المطلوبة لتخزين الشخصية؟

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

ترميز هوفمان

يقوم ترميز هوفمان بتنفيذ الخطوات التالية.

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

يتبع ترميز هوفمان أ قاعدة البادئة مما يمنع الغموض أثناء فك التشفير. تضمن القاعدة أيضًا عدم التعامل مع الرمز المخصص للحرف كبادئة للتعليمات البرمجية المخصصة لأي حرف آخر.

هناك الخطوتان الرئيسيتان التاليتان في ترميز هوفمان:

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

دعونا نلخص الخطوتين أعلاه.

شجرة هوفمان

الخطوة 1: لكل حرف من العقدة، قم بإنشاء عقدة طرفية. تحتوي العقدة الطرفية للشخصية على تكرار تلك الشخصية.

الخطوة 2: اضبط جميع العقد بالترتيب المصنف وفقًا لتكرارها.

الخطوه 3: قد تكون هناك حالة يكون فيها للعقدتين نفس التردد. في مثل هذه الحالة، قم بما يلي:

1. إنشاء عقدة داخلية جديدة.
2. سيكون تردد العقدة هو مجموع تردد هاتين العقدتين اللتين لهما نفس التردد.
3. قم بتمييز العقدة الأولى باعتبارها العقدة الفرعية اليسرى والعقدة الأخرى باعتبارها العقدة الفرعية اليمنى للعقدة الداخلية المنشأة حديثًا.

الخطوة 4: كرر الخطوتين 2 و3 حتى تشكل العقدة بأكملها شجرة واحدة. وهكذا نحصل على شجرة هوفمان.

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

لنفترض أنه يتعين علينا تشفير السلسلة ابرا كادابرا. تحديد ما يلي:

مسح ذاكرة التخزين المؤقت npm

1. كود هوفمان لجميع الشخصيات
2. متوسط ​​طول الكود للسلسلة المحددة
3. طول السلسلة المشفرة

(ط) كود هوفمان لجميع الشخصيات

من أجل تحديد الكود الخاص بكل حرف، نقوم أولاً بإنشاء ملف شجرة هوفمان.

الخطوة 1: جعل أزواج من الشخصيات وتردداتها.

(أ، 5)، (ب، 2)، (ج، 1)، (د، 1)، (ص، 2)

الخطوة 2: وفرز الأزواج بالنسبة للتردد نحصل على:

(ج، 1)، (د، 1)، (ب، 2) (ص، 2)، (أ، 5)

الخطوه 3: اختر أول حرفين وانضم إليهما ضمن العقدة الأصلية.

نلاحظ أن العقدة الأم ليس لها تردد، لذا يجب علينا تخصيص تردد لها. سيكون تردد العقدة الأصلية هو مجموع العقد الفرعية (اليسار واليمين) أي 1+1= 2.

الخطوة 4: كرر الخطوتين 2 و 3 حتى نحصل على شجرة واحدة.

نلاحظ أن الأزواج مرتبة بالفعل (بالخطوة 2). مرة أخرى، اختر أول زوجين وانضم إليهما.

نلاحظ أن العقدة الأم ليس لها تردد، لذا يجب علينا تخصيص تردد لها. سيكون تردد العقدة الأصلية هو مجموع العقد الفرعية (اليسار واليمين) أي 2+2= 4.

تعلم السيلينيوم

مرة أخرى، نتحقق مما إذا كانت الأزواج مرتبة أم لا. في هذه الخطوة، نحن بحاجة إلى فرز الأزواج.

وفقًا للخطوة 3، اختر أول زوجين وضمهما، نحصل على:

نلاحظ أن العقدة الأم ليس لها تردد، لذا يجب علينا تخصيص تردد لها. سيكون تردد العقدة الأصلية هو مجموع العقد الفرعية (اليسار واليمين) أي 2+4= 6.

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

وفقًا للخطوة 3، اختر أول زوجين وضمهما، نحصل على:

نلاحظ أن العقدة الأم ليس لها تردد، لذا يجب علينا تخصيص تردد لها. سيكون تردد العقدة الأصلية هو مجموع العقد الفرعية (اليسار واليمين) أي 5+6= أحد عشر.

لذلك نحصل على شجرة واحدة.

وأخيراً سوف نجد الكود الخاص بكل شخصية بمساعدة الشجرة أعلاه. تعيين وزن لكل حافة. لاحظ أن كل الحافة اليسرى المرجحة هي 0 و ال الحافة اليمنى المرجحة هي 1.

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

نلاحظ أن الحرف الأكثر تكرارًا يحصل على أقصر طول للرمز والحرف الأقل تكرارًا يحصل على أكبر طول للرمز.

الآن يمكننا تشفير السلسلة (أبرا كادابرا) التي اتخذناها أعلاه.

 0 111 10 0 1100 0 1101 0 111 10 0 

(2) متوسط ​​طول الكود للسلسلة

يمكن تحديد متوسط ​​طول الكود لشجرة هوفمان باستخدام الصيغة الواردة أدناه:

اتصالات في جافا

 Average Code Length = ∑ ( frequency × code length ) / ∑ ( frequency ) 

= { (5 × 1) + (2 × 3) + (1 × 4) + (1 × 4) + (2 × 2) } / (5+2+1+1+2)

= 2.09090909

(3) طول السلسلة المشفرة

يمكن تحديد طول الرسالة المشفرة باستخدام الصيغة التالية:

 length= Total number of characters in the text x Average code length per character 

= 11 × 2.09090909

= 23 بت

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

 Huffman (C) n=|C| Q=C for i=1 to n-1 do z=allocate_Node() x=left[z]=Extract_Min(Q) y=right[z]=Extract_Min(Q) f[z]=f[x]+f[y] Insert(Q,z) return Extract_Min(Q) 

خوارزمية هوفمان هي خوارزمية جشعة. نظرًا لأن الخوارزمية تبحث في كل مرحلة عن أفضل الخيارات المتاحة.

التعقيد الزمني لترميز هوفمان هو يا (تسجيل الدخول). حيث n هو عدد الأحرف في النص المحدد.

فك هوفمان

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

منشئ في جافا

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

العقدة الفرعية تحمل حرف الإدخال. يتم تعيين الكود الذي يتكون من 0 و 1 لاحقة. التعقيد الزمني لفك تشفير السلسلة هو على)، حيث n هو طول السلسلة.

هوفمان ترميز وفك برنامج جافا

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

HuffmanCode.java

 import java.util.Comparator; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; //defining a class that creates nodes of the tree class Node { //storing character in ch variable of type character Character ch; //storing frequency in freq variable of type int Integer freq; //initially both child (left and right) are null Node left = null; Node right = null; //creating a constructor of the Node class Node(Character ch, Integer freq) { this.ch = ch; this.freq = freq; } //creating a constructor of the Node class public Node(Character ch, Integer freq, Node left, Node right) { this.ch = ch; this.freq = freq; this.left = left; this.right = right; } } //main class public class HuffmanCode { //function to build Huffman tree public static void createHuffmanTree(String text) { //base case: if user does not provides string if (text == null || text.length() == 0) { return; } //count the frequency of appearance of each character and store it in a map //creating an instance of the Map Map freq = new HashMap(); //loop iterates over the string and converts the text into character array for (char c: text.toCharArray()) { //storing character and their frequency into Map by invoking the put() method freq.put(c, freq.getOrDefault(c, 0) + 1); } //create a priority queue that stores current nodes of the Huffman tree. //here a point to note that the highest priority means the lowest frequency PriorityQueue pq = new PriorityQueue(Comparator.comparingInt(l -&gt; l.freq)); //loop iterate over the Map and returns a Set view of the mappings contained in this Map for (var entry: freq.entrySet()) { //creates a leaf node and add it to the queue pq.add(new Node(entry.getKey(), entry.getValue())); } //while loop runs until there is more than one node in the queue while (pq.size() != 1) { //removing the nodes having the highest priority (the 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 a frequency equal to the sum of both nodes&apos; frequencies. Add the new node to the priority queue. //sum up the frequency of the nodes (left and right) that we have deleted int sum = left.freq + right.freq; //adding a new internal node (deleted nodes i.e. right and left) to the queue with a frequency that is equal to the sum of both nodes pq.add(new Node(null, sum, left, right)); } //root stores pointer to the root of Huffman Tree Node root = pq.peek(); //trace over the Huffman tree and store the Huffman codes in a map Map huffmanCode = new HashMap(); encodeData(root, &apos;&apos;, huffmanCode); //print the Huffman codes for the characters System.out.println(&apos;Huffman Codes of the characters are: &apos; + huffmanCode); //prints the initial data System.out.println(&apos;The initial string is: &apos; + text); //creating an instance of the StringBuilder class StringBuilder sb = new StringBuilder(); //loop iterate over the character array for (char c: text.toCharArray()) { //prints encoded string by getting characters sb.append(huffmanCode.get(c)); } System.out.println(&apos;The encoded string is: &apos; + sb); System.out.print(&apos;The decoded string is: &apos;); if (isLeaf(root)) { //special case: For input like a, aa, aaa, etc. while (root.freq-- &gt; 0) { System.out.print(root.ch); } } else { //traverse over the Huffman tree again and this time, decode the encoded string int index = -1; while (index <sb.length() - 1) { index="decodeData(root," index, sb); } traverse the huffman tree and store codes in a map function that encodes data public static void encodedata(node root, string str, huffmancode) if (root="=" null) return; checks node is leaf or not (isleaf(root)) huffmancode.put(root.ch, str.length()> 0 ? str : &apos;1&apos;); } encodeData(root.left, str + &apos;0&apos;, huffmanCode); encodeData(root.right, str + &apos;1&apos;, huffmanCode); } //traverse the Huffman Tree and decode the encoded string function that decodes the encoded data public static int decodeData(Node root, int index, StringBuilder sb) { //checks if the root node is null or not if (root == null) { return index; } //checks if the node is a leaf node or not if (isLeaf(root)) { System.out.print(root.ch); return index; } index++; root = (sb.charAt(index) == &apos;0&apos;) ? root.left : root.right; index = decodeData(root, index, sb); return index; } //function to check if the Huffman Tree contains a single node public static boolean isLeaf(Node root) { //returns true if both conditions return ture return root.left == null &amp;&amp; root.right == null; } //driver code public static void main(String args[]) { String text = &apos;javatpoint&apos;; //function calling createHuffmanTree(text); } } </sb.length()>

انتاج:

 Huffman Codes of the characters are: {p=000, a=110, t=111, v=001, i=010, j=011, n=100, o=101} The initial string is: javatpoint The encoded string is: 011110001110111000101010100111 The decoded string is: javatpoint