L'algoritmo di codifica di Huffman è stato proposto da David A. Huffman nel 1950. È a compressione dei dati senza perdita di dati meccanismo. È anche noto come codifica della compressione dei dati. È ampiamente utilizzato nella compressione delle immagini (JPEG o JPG). In questa sezione discuteremo di Codifica Huffman E decodifica, e implementare anche il suo algoritmo in un programma Java.
Sappiamo che ogni carattere è una sequenza di 0 e 1 e viene memorizzato utilizzando 8 bit. Il meccanismo si chiama codifica a lunghezza fissa perché ogni carattere utilizza lo stesso numero di memoria a bit fisso.
controllo nullo Java
Qui sorge una domanda, è possibile ridurre la quantità di spazio necessaria per memorizzare un personaggio?
SÌ, è possibile utilizzando codifica a lunghezza variabile. In questo meccanismo sfruttiamo alcuni personaggi che ricorrono più frequentemente rispetto ad altri personaggi. In questa tecnica di codifica possiamo rappresentare lo stesso pezzo di testo o stringa riducendo il numero di bit.
Codifica Huffman
La codifica Huffman implementa i seguenti passaggi.
- Assegna un codice di lunghezza variabile a tutti i caratteri indicati.
- La lunghezza del codice di un carattere dipende dalla frequenza con cui ricorre nel testo o nella stringa specificati.
- Un carattere ottiene il codice più piccolo se si verifica frequentemente.
- Un personaggio ottiene il codice più grande se si verifica meno.
La codifica di Huffman segue a regola del prefisso che previene l'ambiguità durante la decodifica. La regola garantisce inoltre che il codice assegnato al carattere non venga trattato come un prefisso del codice assegnato a qualsiasi altro carattere.
Ci sono i seguenti due passaggi principali coinvolti nella codifica di Huffman:
- Innanzitutto, costruisci a L'albero di Huffman dalla stringa di input, dai caratteri o dal testo specificati.
- Assegna un codice Huffman a ciascun personaggio attraversando l'albero.
Riassumiamo brevemente i due passaggi precedenti.
L'albero di Huffman
Passo 1: Per ogni carattere del nodo, crea un nodo foglia. Il nodo foglia di un carattere contiene la frequenza di quel carattere.
Passo 2: Imposta tutti i nodi in ordine in base alla loro frequenza.
dimensione di pitone
Passaggio 3: Potrebbe esistere una condizione in cui due nodi possono avere la stessa frequenza. In tal caso, procedere come segue:
- Crea un nuovo nodo interno.
- La frequenza del nodo sarà la somma della frequenza di quei due nodi che hanno la stessa frequenza.
- Contrassegna il primo nodo come figlio sinistro e un altro nodo come figlio destro del nodo interno appena creato.
Passaggio 4: Ripetere i passaggi 2 e 3 finché tutti i nodi formano un unico albero. Quindi, otteniamo un albero di Huffman.
Esempio di codifica Huffman
Supponiamo di dover codificare la stringa Abra Cadabra. Determinare quanto segue:
- Codice Huffman per tutti i personaggi
- Lunghezza media del codice per la stringa specificata
- Lunghezza della stringa codificata
(i) Codice Huffman per tutti i personaggi
Per determinare il codice per ciascun carattere, innanzitutto costruiamo a L'albero di Huffman.
Passo 1: Crea coppie di personaggi e le loro frequenze.
(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)
Passo 2: Ordinando le coppie rispetto alla frequenza, otteniamo:
(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)
Passaggio 3: Scegli i primi due personaggi e uniscili sotto un nodo genitore.
Osserviamo che un nodo genitore non ha una frequenza, quindi dobbiamo assegnargli una frequenza. La frequenza del nodo genitore sarà la somma dei suoi nodi figli (sinistro e destro), ovvero 1+1= 2.
sincronizzare Java
Passaggio 4: Ripeti i passaggi 2 e 3 finché non otteniamo un singolo albero.
Osserviamo che le coppie sono già ordinate (dal passaggio 2). Ancora una volta, scegli le prime due coppie e uniscile.
Osserviamo che un nodo genitore non ha una frequenza, quindi dobbiamo assegnargli una frequenza. La frequenza del nodo genitore sarà la somma dei suoi nodi figli (sinistro e destro), ovvero 2+2= 4.
Ancora una volta, controlliamo se le coppie sono ordinate o meno. A questo punto, dobbiamo ordinare le coppie.
Secondo il passaggio 3, scegli le prime due coppie e uniscile, otteniamo:
Osserviamo che un nodo genitore non ha una frequenza, quindi dobbiamo assegnargli una frequenza. La frequenza del nodo genitore sarà la somma dei suoi nodi figli (sinistro e destro), ovvero 2+4= 6.
Ancora una volta, controlliamo se le coppie sono ordinate o meno. A questo punto, dobbiamo ordinare le coppie. Dopo aver ordinato l'albero appare come segue:
Secondo il passaggio 3, scegli le prime due coppie e uniscile, otteniamo:
Osserviamo che un nodo genitore non ha una frequenza, quindi dobbiamo assegnargli una frequenza. La frequenza del nodo genitore sarà la somma dei suoi nodi figli (sinistro e destro), ovvero 5+6= undici.
Pertanto, otteniamo un singolo albero.
Alla fine troveremo il codice per ogni carattere con l'aiuto dell'albero sopra. Assegnare un peso a ciascun bordo. Nota che ciascuno il peso del bordo sinistro è 0 e il il peso sul bordo destro è 1.
Osserviamo che i caratteri di input sono presentati solo nei nodi di uscita e i nodi interni hanno valori nulli. Per trovare il codice Huffman per ogni personaggio, attraversa l'albero Huffman dal nodo radice al nodo foglia di quel particolare personaggio per il quale vogliamo trovare il codice. La tabella descrive il codice e la lunghezza del codice per ciascun carattere.
| Carattere | Frequenza | Codice | Lunghezza del codice |
|---|---|---|---|
| UN | 5 | 0 | 1 |
| B | 2 | 111 | 3 |
| C | 1 | 1100 | 4 |
| D | 1 | 1101 | 4 |
| R | 2 | 10 | 2 |
Osserviamo che il carattere più frequente ottiene la lunghezza del codice più breve e il carattere meno frequente ottiene la lunghezza del codice maggiore.
lancia la stringa su int
Ora possiamo codificare la stringa (Abra Cadabra) che abbiamo preso sopra.
0 111 10 0 1100 0 1101 0 111 10 0
(ii) Lunghezza media del codice per la stringa
La lunghezza media del codice dell'albero di Huffman può essere determinata utilizzando la formula riportata di seguito:
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) Lunghezza della stringa codificata
La lunghezza del messaggio codificato può essere determinata utilizzando la seguente formula:
length= Total number of characters in the text x Average code length per character
= 11x2.09090909
= 23 bit
Algoritmo di codifica di 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’algoritmo di Huffman è un algoritmo avido. Poiché in ogni fase l'algoritmo cerca le migliori opzioni disponibili.
La complessità temporale della codifica Huffman è O(nlogn). Dove n è il numero di caratteri nel testo specificato.
Decodifica Huffman
La decodifica Huffman è una tecnica che converte i dati codificati in dati iniziali. Come abbiamo visto nella codifica, l'albero di Huffman è realizzato per una stringa di input e i caratteri vengono decodificati in base alla loro posizione nell'albero. Il processo di decodifica è il seguente:
interfaccia comparabile in Java
- Inizia ad attraversare l'albero da radice nodo e cercare il personaggio.
- Se ci spostiamo a sinistra nell'albero binario, aggiungiamo 0 al codice.
- Se ci spostiamo a destra nell'albero binario, aggiungiamo 1 al codice.
Il nodo figlio contiene il carattere di input. Gli viene assegnato il codice formato da 0 e 1 successivi. La complessità temporale della decodifica di una stringa è SU), dove n è la lunghezza della stringa.
Programma Java di codifica e decodifica Huffman
Nel seguente programma, abbiamo utilizzato strutture di dati come code di priorità, stack e alberi per progettare una logica di compressione e decompressione. Baseremo le nostre utilità sulla tecnica algoritmica ampiamente utilizzata della codifica di 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()> Produzione:
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