TechCodeview

L'algoritme de codificació de Huffman va ser proposat per David A. Huffman l'any 1950. És un compressió de dades sense pèrdua mecanisme. També es coneix com codificació de compressió de dades. S'utilitza àmpliament en compressió d'imatges (JPEG o JPG). En aquesta secció, parlarem de Codificació Huffman i descodificació, i també implementar el seu algorisme en un programa Java.

Sabem que cada caràcter és una seqüència de 0 i 1 i s'emmagatzema amb 8 bits. El mecanisme s'anomena codificació de longitud fixa perquè cada caràcter utilitza el mateix nombre d'emmagatzematge de bits fixos.

hola món java

Aquí, una pregunta ascendeix, és possible reduir la quantitat d'espai necessari per emmagatzemar un personatge?

Sí, és possible mitjançant l'ús codificació de longitud variable. En aquest mecanisme, explotem alguns personatges que apareixen amb més freqüència en comparació amb altres personatges. En aquesta tècnica de codificació, podem representar la mateixa peça de text o cadena reduint el nombre de bits.

Codificació Huffman

La codificació Huffman implementa els passos següents.

• Assigna un codi de longitud variable a tots els caràcters donats.
• La longitud del codi d'un caràcter depèn de la freqüència amb què es produeix al text o cadena donats.
• Un caràcter obté el codi més petit si es produeix amb freqüència.
• Un caràcter obté el codi més gran si es produeix menys.

La codificació de Huffman segueix a regla del prefix que evita ambigüitats durant la descodificació. La regla també assegura que el codi assignat al caràcter no es tracti com un prefix del codi assignat a cap altre caràcter.

Hi ha els dos passos principals següents a la codificació de Huffman:

• Primer, construïu a Arbre de Huffman de la cadena d'entrada o caràcters o text donats.
• Assigneu un codi Huffman a cada personatge passant per l'arbre.

Resumim els dos passos anteriors.

Arbre de Huffman

Pas 1: Per a cada caràcter del node, creeu un node fulla. El node fulla d'un caràcter conté la freqüència d'aquest caràcter.

Pas 2: Estableix tots els nodes ordenats segons la seva freqüència.

Pas 3: Pot existir una condició en la qual dos nodes poden tenir la mateixa freqüència. En aquest cas, feu el següent:

botó al centre css

1. Creeu un nou node intern.
2. La freqüència del node serà la suma de la freqüència d'aquells dos nodes que tenen la mateixa freqüència.
3. Marqueu el primer node com a fill esquerre i un altre node com a fill dret del node intern acabat de crear.

Pas 4: Repetiu els passos 2 i 3 fins que tot el node formi un sol arbre. Així, obtenim un arbre Huffman.

Exemple de codificació Huffman

Suposem que hem de codificar una cadena abracadabra. Determineu el següent:

1. Codi Huffman per a Tots els personatges
2. Longitud mitjana del codi per a la cadena donada
3. Longitud de la cadena codificada

(i) Codi Huffman per a tots els personatges

Per tal de determinar el codi de cada caràcter, primer, construïm a Arbre de Huffman.

Pas 1: Fer parelles de personatges i les seves freqüències.

(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)

Pas 2: Ordena els parells segons la freqüència, obtenim:

(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)

Pas 3: Trieu els dos primers caràcters i uniu-los sota un node pare.

Observem que un node pare no té una freqüència, per tant, hem d'assignar-li una freqüència. La freqüència del node pare serà la suma dels seus nodes fills (esquerra i dreta), és a dir, 1+1= 2.

Pas 4: Repetiu els passos 2 i 3 fins que aconseguim un sol arbre.

Observem que les parelles ja estan ordenades (al pas 2). De nou, trieu les dues primeres parelles i uniu-les.

Observem que un node pare no té una freqüència, per tant, hem d'assignar-li una freqüència. La freqüència del node pare serà la suma dels seus nodes fills (esquerra i dreta), és a dir, 2+2= 4.

programació dinàmica

De nou, comprovem si les parelles estan ordenades o no. En aquest pas, hem d'ordenar les parelles.

Segons el pas 3, trieu els dos primers parells i uniu-los, obtenim:

Observem que un node pare no té una freqüència, per tant, hem d'assignar-li una freqüència. La freqüència del node pare serà la suma dels seus nodes fills (esquerra i dreta), és a dir, 2+4= 6.

De nou, comprovem si les parelles estan ordenades o no. En aquest pas, hem d'ordenar les parelles. Després d'ordenar l'arbre té el següent aspecte:

Segons el pas 3, trieu els dos primers parells i uniu-los, obtenim:

Observem que un node pare no té una freqüència, per tant, hem d'assignar-li una freqüència. La freqüència del node pare serà la suma dels seus nodes fills (esquerra i dreta), és a dir, 5+6= 11.

Per tant, obtenim un sol arbre.

Finalment, trobarem el codi de cada caràcter amb l'ajuda de l'arbre anterior. Assigna un pes a cada vora. Tingueu en compte que cadascun La ponderació de la vora esquerra és 0 i la La ponderació de la vora dreta és 1.

Observem que els caràcters d'entrada només es presenten als nodes de sortida i els nodes interns tenen valors nuls. Per trobar el codi de Huffman per a cada caràcter, travessa l'arbre de Huffman des del node arrel fins al node full d'aquest caràcter en concret per al qual volem trobar el codi. La taula descriu el codi i la longitud del codi per a cada caràcter.

Observem que el caràcter més freqüent obté la longitud de codi més curta i el caràcter menys freqüent obté la longitud de codi més gran.

Ara podem codificar la cadena (abracadabra) que hem pres més amunt.

 0 111 10 0 1100 0 1101 0 111 10 0 

(ii) Longitud mitjana del codi per a la cadena

La longitud mitjana del codi de l'arbre de Huffman es pot determinar mitjançant la fórmula que es mostra a continuació:

python bytes a cadena

 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) Longitud de la cadena codificada

La longitud del missatge codificat es pot determinar mitjançant la fórmula següent:

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

= 11 x 2,09090909

= 23 bits

Algoritme de codificació 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) 

L'algoritme de Huffman és un algorisme cobdiciós. Ja que en cada etapa l'algoritme busca les millors opcions disponibles.

La complexitat temporal de la codificació de Huffman és O(nlogn). On n és el nombre de caràcters del text donat.

Descodificació de Huffman

La descodificació Huffman és una tècnica que converteix les dades codificades en dades inicials. Com hem vist en la codificació, l'arbre Huffman està fet per a una cadena d'entrada i els caràcters es descodifiquen en funció de la seva posició a l'arbre. El procés de descodificació és el següent:

chmod 755

• Comenceu a recórrer l'arbre des del arrel node i cerca el personatge.
• Si ens movem a l'esquerra a l'arbre binari, sumeu 0 al codi.
• Si ens movem a la dreta a l'arbre binari, sumeu 1 al codi.

El node fill conté el caràcter d'entrada. Se li assigna el codi format pels 0 i 1 posteriors. La complexitat temporal de la descodificació d'una cadena és O(n), on n és la longitud de la corda.

Programa Java de codificació i descodificació Huffman

Al programa següent, hem utilitzat estructures de dades com ara cues de prioritats, piles i arbres per dissenyar una lògica de compressió i descompressió. Basarem les nostres utilitats en la tècnica algorítmica àmpliament utilitzada de la codificació de 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 -&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()>

Sortida:

 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