Алгоритъмът за кодиране на Хъфман е предложен от Дейвид А. Хъфман през 1950 г. Това е a компресиране на данни без загуба механизъм. Известен е още като кодиране на компресия на данни. Той се използва широко при компресиране на изображения (JPEG или JPG). В този раздел ще обсъдим Кодиране на Хъфман и декодиране, и също така имплементира своя алгоритъм в Java програма.
Знаем, че всеки знак е поредица от 0 и 1 и съхранява с помощта на 8 бита. Механизмът се нарича кодиране с фиксирана дължина тъй като всеки символ използва същия брой памет с фиксирани битове.
модем срещу рутер
Тук се издига въпрос, възможно ли е да се намали количеството пространство, необходимо за съхраняване на знак?
да възможно е чрез използване кодиране с променлива дължина. В този механизъм ние използваме някои знаци, които се срещат по-често в сравнение с други знаци. При тази техника на кодиране можем да представим една и съща част от текст или низ чрез намаляване на броя на битовете.
Кодиране на Хъфман
Кодирането на Huffman изпълнява следните стъпки.
- Той присвоява код с променлива дължина на всички дадени знаци.
- Дължината на кода на знак зависи от това колко често се среща в даден текст или низ.
- Символ получава най-малкия код, ако се среща често.
- Символ получава най-големия код, ако се среща най-малко.
Кодирането на Huffman следва a правило за префикс което предотвратява двусмислието при декодиране. Правилото също така гарантира, че кодът, присвоен на знака, не се третира като префикс на кода, присвоен на друг знак.
Има следните две основни стъпки, включени в кодирането на Huffman:
- Първо, конструирайте a Дърво на Хъфман от дадения входен низ или знаци или текст.
- Присвоете код на Хъфман към всеки символ, като преминете през дървото.
Нека да опишем накратко горните две стъпки.
Дървото на Хъфман
Етап 1: За всеки символ на възела създайте листов възел. Листовият възел на символ съдържа честотата на този знак.
Стъпка 2: Задайте всички възли в сортиран ред според тяхната честота.
git add --all
Стъпка 3: Може да съществува състояние, при което два възела могат да имат еднаква честота. В такъв случай направете следното:
- Създайте нов вътрешен възел.
- Честотата на възела ще бъде сумата от честотите на тези два възела, които имат еднаква честота.
- Маркирайте първия възел като ляво дете и друг възел като дясно дете на новосъздадения вътрешен възел.
Стъпка 4: Повторете стъпки 2 и 3, докато всички възли образуват едно дърво. Така получаваме дърво на Хъфман.
Пример за кодиране на Huffman
Да предположим, че трябва да кодираме низ Абра Кадабра. Определете следното:
- Код на Хъфман за всички герои
- Средна дължина на кода за дадения низ
- Дължина на кодирания низ
(i) Код на Хъфман за всички знаци
За да определим кода за всеки символ, първо конструираме a Дърво на Хъфман.
Етап 1: Направете двойки знаци и техните честоти.
(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)
Стъпка 2: Сортирайки двойки по отношение на честотата, получаваме:
(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)
Стъпка 3: Изберете първите два знака и ги присъединете към родителски възел.
Наблюдаваме, че родителският възел няма честота, така че трябва да му присвоим честота. Честотата на родителския възел ще бъде сумата от неговите дъщерни възли (ляв и десен), т.е. 1+1= 2.
скрипт за зареждане на javascript
Стъпка 4: Повторете стъпки 2 и 3, докато не получим едно дърво.
Наблюдаваме, че двойките вече са сортирани (по стъпка 2) по начин. Отново изберете първите две двойки и се присъединете към тях.
Наблюдаваме, че родителският възел няма честота, така че трябва да му присвоим честота. Честотата на родителския възел ще бъде сумата от неговите дъщерни възли (ляв и десен), т.е. 2+2= 4.
Отново проверяваме дали двойките са подредени или не. На тази стъпка трябва да сортираме двойките.
Според стъпка 3, изберете първите две двойки и ги съединете, получаваме:
Наблюдаваме, че родителският възел няма честота, така че трябва да му присвоим честота. Честотата на родителския възел ще бъде сумата от неговите дъщерни възли (ляв и десен), т.е. 2+4= 6.
Отново проверяваме дали двойките са подредени или не. На тази стъпка трябва да сортираме двойките. След сортиране дървото изглежда така:
Според стъпка 3, изберете първите две двойки и ги съединете, получаваме:
Наблюдаваме, че родителският възел няма честота, така че трябва да му присвоим честота. Честотата на родителския възел ще бъде сумата от неговите дъщерни възли (ляв и десен), т.е. 5+6= единадесет.
Следователно получаваме едно дърво.
Най-накрая ще намерим кода за всеки символ с помощта на горното дърво. Задайте тегло на всеки ръб. Имайте предвид, че всеки левият ръб претеглен е 0 и на претегленият десен край е 1.
Наблюдаваме, че входните знаци се представят само в крайните възли, а вътрешните възли имат нулеви стойности. За да намерите кода на Хъфман за всеки знак, преминете през дървото на Хъфман от основния възел до листовия възел на този конкретен знак, за който искаме да намерим код. Таблицата описва кода и дължината на кода за всеки знак.
| Характер | Честота | Код | Дължина на кода |
|---|---|---|---|
| А | 5 | 0 | 1 |
| Б | 2 | 111 | 3 |
| ° С | 1 | 1100 | 4 |
| д | 1 | 1101 | 4 |
| Р | 2 | 10 | 2 |
Наблюдаваме, че най-често срещаният знак получава най-късата дължина на кода, а по-рядко срещаният знак получава най-голямата дължина на кода.
конвертиране на низ в цяло число в java
Сега можем да кодираме низа (Абра Кадабра) които взехме по-горе.
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 х 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)
Алгоритъмът на Хъфман е алчен алгоритъм. Тъй като на всеки етап алгоритъмът търси най-добрите налични опции.
Времевата сложност на кодирането на Huffman е O(nlogn). Където n е броят знаци в дадения текст.
Декодиране на Хъфман
Декодирането на Huffman е техника, която преобразува кодираните данни в първоначални данни. Както видяхме при кодирането, дървото на Хъфман е създадено за входен низ и символите се декодират въз основа на тяхната позиция в дървото. Процесът на декодиране е както следва:
модели за програмиране java
- Започнете да преминавате над дървото от корен възел и потърсете героя.
- Ако се преместим наляво в двоичното дърво, добавете 0 към кода.
- Ако се преместим надясно в двоичното дърво, добавете 1 към кода.
Дъщерният възел съдържа входния знак. На него се присвоява кодът, образуван от последващи 0 и 1. Времевата сложност на декодирането на низ е На), където n е дължината на низа.
Java програма за кодиране и декодиране на Huffman
В следващата програма използвахме структури от данни като приоритетни опашки, стекове и дървета, за да проектираме логика за компресиране и декомпресиране. Ние ще базираме нашите помощни програми на широко използваната алгоритмична техника на кодирането на Хъфман.
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 -> 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' 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, '', huffmanCode); //print the Huffman codes for the characters System.out.println('Huffman Codes of the characters are: ' + huffmanCode); //prints the initial data System.out.println('The initial string is: ' + 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('The encoded string is: ' + sb); System.out.print('The decoded string is: '); if (isLeaf(root)) { //special case: For input like a, aa, aaa, etc. while (root.freq-- > 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 : '1'); } encodeData(root.left, str + '0', huffmanCode); encodeData(root.right, str + '1', 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) == '0') ? 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 && root.right == null; } //driver code public static void main(String args[]) { String text = 'javatpoint'; //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