Algoritmul de codificare Huffman a fost propus de David A. Huffman în 1950. Este o compresie fără pierderi de date mecanism. Este cunoscut și ca codificarea prin compresie a datelor. Este utilizat pe scară largă în compresia imaginilor (JPEG sau JPG). În această secțiune, vom discuta despre Codificare Huffman și decodare, și, de asemenea, implementează algoritmul său într-un program Java.
Știm că fiecare caracter este o secvență de 0 și 1 și se stochează folosind 8 biți. Mecanismul este numit codificare cu lungime fixă deoarece fiecare personaj folosește același număr de stocare pe biți fix.
govinda
Aici, o întrebare urcă, este posibil să se reducă spațiul necesar pentru stocarea unui caracter?
Da, este posibil prin folosire codificare cu lungime variabilă. În acest mecanism, exploatăm unele personaje care apar mai frecvent în comparație cu alte personaje. În această tehnică de codificare, putem reprezenta aceeași bucată de text sau șir prin reducerea numărului de biți.
Codificare Huffman
Codarea Huffman implementează următorii pași.
- El atribuie un cod de lungime variabilă tuturor caracterelor date.
- Lungimea codului unui caracter depinde de cât de frecvent apare în textul sau șirul dat.
- Un caracter primește cel mai mic cod dacă apare frecvent.
- Un caracter primește cel mai mare cod dacă apare cel mai puțin.
Codarea Huffman urmează a regula prefixului care previne ambiguitatea în timpul decodării. Regula asigură, de asemenea, că codul atribuit caracterului nu este tratat ca prefix al codului atribuit oricărui alt caracter.
Există următorii doi pași majori implicați în codarea Huffman:
- Mai întâi, construiți a Arborele Huffman din șirul de intrare dat sau caractere sau text.
- Atribuiți un cod Huffman fiecărui personaj prin parcurgerea arborelui.
Să prezentăm pe scurt cei doi pași de mai sus.
Arborele Huffman
Pasul 1: Pentru fiecare caracter al nodului, creați un nod frunză. Nodul frunză al unui caracter conține frecvența acelui caracter.
Pasul 2: Setați toate nodurile în ordine sortată în funcție de frecvența lor.
Pasul 3: Poate exista o condiție în care două noduri pot avea aceeași frecvență. Într-un astfel de caz, procedați în felul următor:
- Creați un nou nod intern.
- Frecvența nodului va fi suma frecvenței acelor două noduri care au aceeași frecvență.
- Marcați primul nod drept copil stâng și un alt nod drept copil drept al nodului intern nou creat.
Pasul 4: Repetați pașii 2 și 3 până când toate nodurile formează un singur arbore. Astfel, obținem un copac Huffman.
Exemplu de codificare Huffman
Să presupunem că trebuie să codificăm șir Abra Cadabra. Determinați următoarele:
- Codul Huffman pentru Toate personajele
- Lungimea medie a codului pentru șirul dat
- Lungimea șirului codificat
(i) Codul Huffman pentru toate personajele
Pentru a determina codul pentru fiecare caracter, mai întâi construim a Arborele Huffman.
Pasul 1: Faceți perechi de personaje și frecvențele acestora.
(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)
Pasul 2: Sortați perechile în funcție de frecvență, obținem:
(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)
caseta de alertă javascript
Pasul 3: Alegeți primele două caractere și uniți-le sub un nod părinte.
Observăm că un nod părinte nu are o frecvență, așa că trebuie să îi atribuim o frecvență. Frecvența nodului părinte va fi suma nodurilor sale secundare (stânga și dreapta), adică 1+1= 2.
Pasul 4: Repetați pașii 2 și 3 până când obținem un singur copac.
Observăm că perechile sunt deja sortate (prin pasul 2). Din nou, alegeți primele două perechi și uniți-le.
Observăm că un nod părinte nu are o frecvență, așa că trebuie să îi atribuim o frecvență. Frecvența nodului părinte va fi suma nodurilor sale secundare (stânga și dreapta), adică 2+2= 4.
Din nou, verificăm dacă perechile sunt sortate sau nu. La acest pas, trebuie să sortăm perechile.
Conform pasului 3, alegeți primele două perechi și uniți-le, obținem:
Observăm că un nod părinte nu are o frecvență, așa că trebuie să îi atribuim o frecvență. Frecvența nodului părinte va fi suma nodurilor sale secundare (stânga și dreapta), adică 2+4= 6.
comanda zip în linux
Din nou, verificăm dacă perechile sunt sortate sau nu. La acest pas, trebuie să sortăm perechile. După sortare, arborele arată astfel:
Conform pasului 3, alegeți primele două perechi și uniți-le, obținem:
Observăm că un nod părinte nu are o frecvență, așa că trebuie să îi atribuim o frecvență. Frecvența nodului părinte va fi suma nodurilor sale secundare (stânga și dreapta), adică 5+6= unsprezece.
Prin urmare, obținem un singur copac.
În cele din urmă, vom găsi codul pentru fiecare personaj cu ajutorul arborelui de mai sus. Atribuiți o greutate fiecărei margini. Rețineți că fiecare ponderea la marginea stângă este 0 si ponderea la marginea dreaptă este 1.
conversie tip java și casting
Observăm că caracterele de intrare sunt prezentate doar în nodurile de plecare, iar nodurile interne au valori nule. Pentru a găsi codul Huffman pentru fiecare personaj, parcurgeți arborele Huffman de la nodul rădăcină la nodul frunză al caracterului particular pentru care dorim să găsim cod. Tabelul descrie codul și lungimea codului pentru fiecare caracter.
| Caracter | Frecvență | Cod | Lungimea codului |
|---|---|---|---|
| A | 5 | 0 | 1 |
| B | 2 | 111 | 3 |
| C | 1 | 1100 | 4 |
| D | 1 | 1101 | 4 |
| R | 2 | 10 | 2 |
Observăm că caracterul cel mai frecvent primește cea mai scurtă lungime de cod, iar caracterul mai puțin frecvent obține cea mai mare lungime de cod.
Acum putem codifica șirul (Abra Cadabra) pe care le-am luat mai sus.
0 111 10 0 1100 0 1101 0 111 10 0
(ii) Lungimea medie a codului pentru șir
Lungimea medie a codului arborelui Huffman poate fi determinată folosind formula de mai jos:
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) Lungimea șirului codificat
Lungimea mesajului codificat poate fi determinată folosind următoarea formulă:
length= Total number of characters in the text x Average code length per character
= 11 x 2,09090909
= 23 de biți
Algoritmul de codificare Huffman
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)
Algoritmul Huffman este un algoritm lacom. Deoarece în fiecare etapă algoritmul caută cele mai bune opțiuni disponibile.
Complexitatea temporală a codificării Huffman este O(nlogn). Unde n este numărul de caractere din textul dat.
Decodare Huffman
Decodarea Huffman este o tehnică care convertește datele codificate în date inițiale. După cum am văzut în codificare, arborele Huffman este făcut pentru un șir de intrare, iar caracterele sunt decodificate în funcție de poziția lor în arbore. Procesul de decodare este următorul:
matematică aleatoare java
- Începeți să traversați peste copac din rădăcină nod și căutați personajul.
- Dacă ne deplasăm la stânga în arborele binar, adăugați 0 la cod.
- Dacă ne deplasăm direct în arborele binar, adăugați 1 la cod.
Nodul copil deține caracterul de intrare. I se atribuie codul format din 0 și 1 ulterioare. Complexitatea de timp a decodării unui șir este Pe), unde n este lungimea șirului.
Programul Java de codificare și decodare Huffman
În programul următor, am folosit structuri de date precum cozi de prioritate, stive și arbori pentru a proiecta o logică de compresie și decompresie. Ne vom baza utilitățile pe tehnica algoritmică utilizată pe scară largă de codare 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()> Ieșire:
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