אלגוריתם הקידוד של האפמן הוצע על ידי דיוויד א. האפמן בשנת 1950. זה א דחיסת נתונים ללא אובדן מַנגָנוֹן. זה ידוע גם בשם קידוד דחיסת נתונים. הוא נמצא בשימוש נרחב בדחיסת תמונה (JPEG או JPG). בחלק זה, נדון ב קידוד האפמן ו פִּעַנוּחַ, וגם ליישם את האלגוריתם שלו בתוכנית Java.

אנו יודעים שכל תו הוא רצף של 0 ו-1 ומאחסן באמצעות 8 סיביות. המנגנון נקרא קידוד באורך קבוע מכיוון שכל תו משתמש באותו מספר של אחסון סיביות קבועות.

פיצול מחרוזת c++

כאן עולה שאלה, האם ניתן לצמצם את כמות השטח הנדרש לאחסון דמות?

כן, זה אפשרי על ידי שימוש קידוד באורך משתנה. במנגנון זה, אנו מנצלים כמה דמויות המופיעות בתדירות גבוהה יותר בהשוואה לדמויות אחרות. בטכניקת קידוד זו, אנו יכולים לייצג את אותה פיסת טקסט או מחרוזת על ידי הפחתת מספר הביטים.

קידוד האפמן

קידוד האפמן מיישם את השלבים הבאים.

• הוא מקצה קוד באורך משתנה לכל התווים הנתונים.
• אורך הקוד של תו תלוי בתדירות שבה הוא מופיע בטקסט או במחרוזת הנתונים.
• תו מקבל את הקוד הקטן ביותר אם הוא מופיע לעתים קרובות.
• תו מקבל את הקוד הגדול ביותר אם הוא מתרחש לפחות.

קידוד האפמן עוקב אחר א כלל קידומת שמונע עמימות בזמן פענוח. הכלל גם מבטיח שהקוד המוקצה לתו לא יטופל כאל קידומת של הקוד המוקצה לאף תו אחר.

ישנם שני השלבים העיקריים הבאים המעורבים בקידוד האפמן:

• ראשית, בנה א עץ האפמן ממחרוזת הקלט הנתונה או תווים או טקסט.
• הקצה, קוד האפמן לכל דמות על ידי מעבר על העץ.

בואו נסכם את שני השלבים לעיל.

האפמן עץ

שלב 1: עבור כל תו של הצומת, צור צומת עלה. צומת העלה של תו מכיל את התדירות של אותו תו.

שלב 2: הגדר את כל הצמתים בסדר ממוין לפי התדירות שלהם.

שלב 3: יתכן וקיים מצב שבו שני צמתים עשויים להיות בעלי אותה תדירות. במקרה כזה, בצע את הפעולות הבאות:

1. צור צומת פנימי חדש.
2. תדירות הצומת תהיה סכום התדירות של אותם שני צמתים בעלי אותו תדר.
3. סמן את הצומת הראשון בתור הבן השמאלי וצומת נוסף בתור הבן הימני של הצומת הפנימי החדש שנוצר.

שלב 4: חזור על שלב 2 ו-3 עד שכל הצומת יוצר עץ בודד. כך, אנו מקבלים עץ האפמן.

דוגמה לקידוד האפמן

נניח שעלינו לקודד מחרוזת אברה קדברה. קבע את הדברים הבאים:

1. קוד האפמן עבור כל הדמויות
2. אורך קוד ממוצע עבור המחרוזת הנתונה
3. אורך המחרוזת המקודדת

(i) קוד האפמן לכל הדמויות

על מנת לקבוע את הקוד עבור כל תו, ראשית, אנו בונים את a עץ האפמן.

סוגי נתונים פרימיטיביים ב-java

שלב 1: צור זוגות של דמויות והתדרים שלהן.

(א, 5), (ב, 2), (ג, 1), (ד, 1), (ר, 2)

שלב 2: מיון זוגות ביחס לתדירות, נקבל:

(ג, 1), (ד, 1), (ב, 2) (ר, ​​2), (א, 5)

שלב 3: בחר את שתי הדמויות הראשונות והצטרף אליהן מתחת לצומת אב.

אנו רואים שלצומת אב אין תדר ולכן עלינו להקצות לו תדר. תדר צומת האב יהיה סכום הצמתים הצאצאים שלו (משמאל וימין), כלומר 1+1= 2.

שלב 4: חזור על שלבים 2 ו-3 עד שנקבל עץ בודד.

אנו רואים שהזוגות כבר ממוינים (לפי שלב 2). שוב, בחר את שני הזוגות הראשונים והצטרף אליהם.

אנו רואים שלצומת אב אין תדר ולכן עלינו להקצות לו תדר. תדר צומת האב יהיה סכום הצמתים הצאצאים שלו (משמאל וימין) כלומר 2+2= 4.

גבול באמצעות css

שוב, אנו בודקים אם הזוגות ממוינים או לא. בשלב זה, עלינו למיין את הזוגות.

לפי שלב 3, בחר את שני הזוגות הראשונים והצטרף אליהם, נקבל:

אנו רואים שלצומת אב אין תדר ולכן עלינו להקצות לו תדר. תדר צומת האב יהיה סכום הצמתים הצאצאים שלו (משמאל וימין), כלומר 2+4= 6.

שוב, אנו בודקים אם הזוגות ממוינים או לא. בשלב זה, עלינו למיין את הזוגות. לאחר מיון העץ נראה כך:

לפי שלב 3, בחר את שני הזוגות הראשונים והצטרף אליהם, נקבל:

אנו רואים שלצומת אב אין תדר ולכן עלינו להקצות לו תדר. תדירות צומת האב יהיה סכום הצמתים הצאצאים שלו (משמאל וימין), כלומר 5+6= אחד עשר.

לכן, אנו מקבלים עץ בודד.

לבסוף, נמצא את הקוד לכל תו בעזרת העץ שלמעלה. הקצה משקל לכל קצה. שימו לב שכל אחד משקל קצה שמאל הוא 0 וה משקל קצה ימין הוא 1.

אנו רואים שתווי קלט מוצגים רק בצמתי העזיבה ולצמתים הפנימיים יש ערכי Null. על מנת למצוא את קוד ההופמן עבור כל תו, חצו על עץ ההפמן מצומת השורש לצומת העלה של אותו תו מסוים שעבורו אנו רוצים למצוא קוד. הטבלה מתארת ​​את הקוד ואורך הקוד עבור כל תו.

הם דוגמאות לדוגמא

אנו רואים שהתו השכיח ביותר מקבל את אורך הקוד הקצר ביותר והתו הפחות תכוף מקבל את אורך הקוד הגדול ביותר.

כעת נוכל לקודד את המחרוזת (אברה קדברה) שלקחנו למעלה.

 0 111 10 0 1100 0 1101 0 111 10 0 

(ii) אורך קוד ממוצע עבור המחרוזת

ניתן לקבוע את אורך הקוד הממוצע של עץ האפמן באמצעות הנוסחה המופיעה להלן:

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

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

= 2.09090909

(iii) אורך המחרוזת המקודדת

ניתן לקבוע את אורך ההודעה המקודדת באמצעות הנוסחה הבאה:

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

= 11 x 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) 

אלגוריתם האפמן הוא אלגוריתם חמדני. מכיוון שבכל שלב האלגוריתם מחפש את האפשרויות הטובות ביותר הזמינות.

מורכבות הזמן של קידוד האפמן היא O(nlogn). כאשר n הוא מספר התווים בטקסט הנתון.

פענוח האפמן

פענוח האפמן הוא טכניקה הממירה את הנתונים המקודדים לנתונים ראשוניים. כפי שראינו בקידוד, עץ האפמן נוצר עבור מחרוזת קלט והתווים מפוענחים על סמך מיקומם בעץ. תהליך הפענוח הוא כדלקמן:

מערך java ממוין

• התחל לחצות את העץ מה- שורש צומת וחפש את הדמות.
• אם נעבור שמאלה בעץ הבינארי, הוסף 0 לקוד.
• אם נעבור ימינה בעץ הבינארי, הוסף 1 לקוד.

צומת הילד מחזיק בתו הקלט. הוא מוקצה לקוד שנוצר על ידי 0 ו-1 שלאחר מכן. מורכבות הזמן של פענוח מחרוזת היא עַל), כאשר n הוא אורך המחרוזת.

האפמן קידוד ופענוח Java תוכנית

בתוכנית הבאה, השתמשנו במבני נתונים כמו תורי עדיפות, ערימות ועצים כדי לעצב לוגיקת דחיסה ופירוק. אנו נבסס את כלי השירות שלנו על הטכניקה האלגוריתמית הנפוצה של קידוד האפמן.

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