I dati possono essere compressi utilizzando la tecnica della codifica Huffman per rimpicciolirli senza perdere nessuna informazione. Dopo David Huffman, chi lo ha creato all'inizio? I dati che contengono caratteri ripetuti frequentemente vengono generalmente compressi utilizzando la codifica Huffman.
Un noto algoritmo Greedy è Huffman Coding. La dimensione del codice assegnato a un carattere dipende dalla frequenza del carattere, motivo per cui viene definito un algoritmo goloso. Il codice variabile di breve lunghezza viene assegnato al carattere con la frequenza più alta e viceversa per i caratteri con frequenze più basse. Utilizza una codifica a lunghezza variabile, il che significa che assegna a ciascun carattere nel flusso di dati fornito un codice di lunghezza variabile diverso.
Regola del prefisso
In sostanza, questa regola stabilisce che il codice assegnato a un carattere non deve essere il prefisso di un altro codice. Se questa regola viene infranta, potrebbero apparire varie ambiguità durante la decodifica dell'albero di Huffman che è stato creato.
Vediamo un'illustrazione di questa regola per comprenderla meglio: Per ogni carattere viene fornito un codice, ad esempio:
a - 0 b - 1 c - 01
Supponendo che il flusso di bit prodotto sia 001, il codice può essere espresso come segue una volta decodificato:
ottenere la connessione
0 0 1 = aab 0 01 = ac
Cos'è il processo di codifica Huffman?
Il Codice Huffman si ottiene per ogni personaggio distinto principalmente in due passaggi:
- Crea prima un albero di Huffman utilizzando solo i caratteri univoci nel flusso di dati fornito.
- In secondo luogo, dobbiamo procedere attraverso l'Huffman Tree costruito, assegnare codici ai personaggi e quindi utilizzare tali codici per decodificare il testo fornito.
Passaggi da eseguire nella codifica Huffman
I passaggi utilizzati per costruire l'albero di Huffman utilizzando i caratteri forniti
Input: string str = 'abbcdbccdaabbeeebeab'
Se in questo caso per la compressione dei dati viene utilizzata la codifica Huffman, per la decodifica è necessario determinare le seguenti informazioni:
significato di xdxd
- Per ogni personaggio, il Codice Huffman
- Lunghezza del messaggio con codifica Huffman (in bit), lunghezza media del codice
- Utilizzando le formule trattate di seguito, vengono scoperti gli ultimi due.
Come si può costruire un albero di Huffman partendo dai caratteri immessi?
È necessario innanzitutto determinare la frequenza di ciascun carattere nella stringa fornita.
| Carattere | Frequenza |
|---|---|
| UN | 4 |
| B | 7 |
| C | 3 |
| D | 2 |
| È | 4 |
- Ordina i caratteri per frequenza, in ordine crescente. Questi vengono mantenuti in una coda con priorità heap Q/min.
- Per ogni carattere distinto e la sua frequenza nel flusso di dati, crea un nodo foglia.
- Rimuovi i due nodi con le due frequenze più basse dai nodi e la nuova radice dell'albero viene creata utilizzando la somma di queste frequenze.
- Rendi il primo nodo estratto il suo figlio sinistro e il secondo nodo estratto il suo figlio destro mentre estrai i nodi con la frequenza più bassa dal min-heap.
- All'heap minimo, aggiungi questo nodo.
- Poiché il lato sinistro della radice dovrebbe sempre contenere la frequenza minima.
- Ripetere i passaggi 3 e 4 finché non rimane un solo nodo nell'heap o tutti i caratteri sono rappresentati da nodi nell'albero. L'albero è finito quando rimane solo il nodo radice.
Esempi di codifica Huffman
Usiamo un'illustrazione per spiegare l'algoritmo:
Algoritmo per la codifica di Huffman
Passo 1: Costruisci un heap minimo in cui ogni nodo rappresenta la radice di un albero con un singolo nodo e contiene 5 (il numero di caratteri univoci dal flusso di dati fornito).
Passo 2: Ottieni due nodi di frequenza minima dall'heap minimo nel passaggio due. Aggiungiamo un terzo nodo interno, frequenza 2+3=5, che si crea unendo i due nodi estratti.
- Ora ci sono 4 nodi nel min-heap, 3 dei quali sono le radici di alberi con un singolo elemento ciascuno e 1 dei quali è la radice di un albero con due elementi.
Passaggio 3: Ottieni i due nodi di frequenza minima dall'heap in modo simile nel passaggio tre. Inoltre, aggiungi un nuovo nodo interno formato unendo i due nodi estratti; la sua frequenza nell'albero dovrebbe essere 4 + 4 = 8.
- Ora che l'heap minimo ha tre nodi, un nodo funge da radice degli alberi con un singolo elemento e due nodi dell'heap fungono da radice degli alberi con più nodi.
Passaggio 4: Ottieni i due nodi di frequenza minima nel passaggio quattro. Inoltre, aggiungi un nuovo nodo interno formato unendo i due nodi estratti; la sua frequenza nell'albero dovrebbe essere 5 + 7 = 12.
- Quando creiamo un albero di Huffman, dobbiamo assicurarci che il valore minimo sia sempre sul lato sinistro e che il secondo valore sia sempre sul lato destro. Attualmente, l'immagine qui sotto mostra l'albero che si è formato:
Passaggio 5: Ottieni i seguenti due nodi di frequenza minima nel passaggio 5. Inoltre, aggiungi un nuovo nodo interno formato unendo i due nodi estratti; la sua frequenza nell'albero dovrebbe essere 12 + 8 = 20.
Continua finché tutti i personaggi distinti non sono stati aggiunti all'albero. L'albero di Huffman creato per il cast di personaggi specificato è mostrato nell'immagine sopra.
Ora, per ogni nodo non foglia, assegna 0 al bordo sinistro e 1 al bordo destro per creare il codice per ogni lettera.
Regole da seguire per determinare i pesi dei bordi:
- Dovremmo dare ai bordi destri il peso 1 se dai ai bordi sinistri il peso 0.
- Se ai bordi sinistri viene assegnato peso 1, ai bordi destri deve essere assegnato peso 0.
- Può essere utilizzata una qualsiasi delle due convenzioni sopra menzionate.
- Tuttavia, seguire lo stesso protocollo anche durante la decodifica dell'albero.
Dopo la ponderazione, l'albero modificato viene visualizzato come segue:
Comprendere il codice
- Dobbiamo attraversare l'albero di Huffman fino a raggiungere il nodo foglia, dove è presente l'elemento, per decodificare il codice Huffman per ciascun carattere dall'albero di Huffman risultante.
- I pesi tra i nodi devono essere registrati durante l'attraversamento e assegnati agli elementi situati nel nodo foglia specifico.
- Il seguente esempio aiuterà a illustrare ulteriormente cosa intendiamo:
- Per ottenere il codice per ogni carattere nell'immagine sopra, dobbiamo percorrere l'intero albero (fino a coprire tutti i nodi foglia).
- Di conseguenza, l'albero che è stato creato viene utilizzato per decodificare i codici per ciascun nodo. Di seguito è riportato un elenco dei codici per ciascun carattere:
| Carattere | Frequenza/conteggio | Codice |
|---|---|---|
| UN | 4 | 01 |
| B | 7 | undici |
| C | 3 | 101 |
| D | 2 | 100 |
| È | 4 | 00 |
Di seguito è riportata l'implementazione nella programmazione C:
// C program for Huffman Coding #include #include // This constant can be avoided by explicitly // calculating height of Huffman Tree #define MAX_TREE_HT 100 // A Huffman tree node struct MinHeapNode { // One of the input characters char data; // Frequency of the character unsigned freq; // Left and right child of this node struct MinHeapNode *left, *right; }; // A Min Heap: Collection of // min-heap (or Huffman tree) nodes struct MinHeap { // Current size of min heap unsigned size; // capacity of min heap unsigned capacity; // Array of minheap node pointers struct MinHeapNode** array; }; // A utility function allocate a new // min heap node with given character // and frequency of the character struct MinHeapNode* newNode(char data, unsigned freq) { struct MinHeapNode* temp = (struct MinHeapNode*)malloc( sizeof(struct MinHeapNode)); temp->left = temp->right = NULL; temp->data = data; temp->freq = freq; return temp; } // A utility function to create // a min heap of given capacity struct MinHeap* createMinHeap(unsigned capacity) { struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap)); // current size is 0 minHeap->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHeapNode**)malloc( minHeap->capacity * sizeof(struct MinHeapNode*)); return minHeap; } // A utility function to // swap two min heap nodes void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) { struct MinHeapNode* t = *a; *a = *b; *b = t; } // The standard minHeapify function. void minHeapify(struct MinHeap* minHeap, int idx) { int smallest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2; if (left size && minHeap->array[left]->freq array[smallest]->freq) smallest = left; if (right size && minHeap->array[right]->freq array[smallest]->freq) smallest = right; if (smallest != idx) { swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); minHeapify(minHeap, smallest); } } // A utility function to check // if size of heap is 1 or not int isSizeOne(struct MinHeap* minHeap) { return (minHeap->size == 1); } // A standard function to extract // minimum value node from heap struct MinHeapNode* extractMin(struct MinHeap* minHeap) { struct MinHeapNode* temp = minHeap->array[0]; minHeap->array[0] = minHeap->array[minHeap->size - 1]; --minHeap->size; minHeapify(minHeap, 0); return temp; } // A utility function to insert // a new node to Min Heap void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) { ++minHeap->size; int i = minHeap->size - 1; while (i && minHeapNode->freq array[(i - 1) / 2]->freq) { minHeap->array[i] = minHeap->array[(i - 1) / 2]; i = (i - 1) / 2; } minHeap->array[i] = minHeapNode; } // A standard function to build min heap void buildMinHeap(struct MinHeap* minHeap) { int n = minHeap->size - 1; int i; for (i = (n - 1) / 2; i >= 0; --i) minHeapify(minHeap, i); } // A utility function to print an array of size n void printArr(int arr[], int n) { int i; for (i = 0; i left) && !(root->right); } // Creates a min heap of capacity // equal to size and inserts all character of // data[] in min heap. Initially size of // min heap is equal to capacity struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // The main function that builds Huffman tree struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Step 1: Create a min heap of capacity // equal to size. Initially, there are // modes equal to size. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Iterate while size of heap doesn't become 1 while (!isSizeOne(minHeap)) { // Step 2: Extract the two minimum // freq items from min heap left = extractMin(minHeap); right = extractMin(minHeap); // Step 3: Create a new internal // node with frequency equal to the // sum of the two nodes frequencies. // Make the two extracted node as // left and right children of this new node. // Add this node to the min heap // '$' is a special value for internal nodes, not // used top = newNode('$', left->freq + right->freq); top->left = left; top->right = right; insertMinHeap(minHeap, top); } // Step 4: The remaining node is the // root node and the tree is complete. return extractMin(minHeap); } // Prints huffman codes from the root of Huffman Tree. // It uses arr[] to store codes void printCodes(struct MinHeapNode* root, int arr[], int top) { // Assign 0 to left edge and recur if (root->left) { arr[top] = 0; printCodes(root->left, arr, top + 1); } // Assign 1 to right edge and recur if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // If this is a leaf node, then // it contains one of the input // characters, print the character // and its code from arr[] if (isLeaf(root)) { printf('%c: ', root->data); printArr(arr, top); } } // The main function that builds a // Huffman Tree and print codes by traversing // the built Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree(data, freq, size); // Print Huffman codes using // the Huffman tree built above int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Driver code int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16, 45 }; int size = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, freq, size); return 0; } Produzione
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 …………… Process executed in 1.11 seconds Press any key to continue.
Implementazione Java del codice sopra:
import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; class Huffman { // recursive function to print the // huffman-code through the tree traversal. // Here s is the huffman - code generated. public static void printCode(HuffmanNode root, String s) { // base case; if the left and right are null // then its a leaf node and we print // the code s generated by traversing the tree. if (root.left == null && root.right == null && Character.isLetter(root.c)) { // c is the character in the node System.out.println(root.c + ':' + s); return; } // if we go to left then add '0' to the code. // if we go to the right add'1' to the code. // recursive calls for left and // right sub-tree of the generated tree. printCode(root.left, s + '0'); printCode(root.right, s + '1'); } // main function public static void main(String[] args) { Scanner s = new Scanner(System.in); // number of characters. int n = 6; char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' }; int[] charfreq = { 5, 9, 12, 13, 16, 45 }; // creating a priority queue q. // makes a min-priority queue(min-heap). PriorityQueue q = new PriorityQueue( n, new MyComparator()); for (int i = 0; i <n; i++) { creating a huffman node object and add it to the priority queue. huffmannode hn="new" huffmannode(); hn.c="charArray[i];" hn.data="charfreq[i];" hn.left="null;" hn.right="null;" functions adds q.add(hn); } create root here we will extract two minimum value from heap each time until its size reduces 1, all nodes are extracted. while (q.size()> 1) { // first min extract. HuffmanNode x = q.peek(); q.poll(); // second min extract. HuffmanNode y = q.peek(); q.poll(); // new node f which is equal HuffmanNode f = new HuffmanNode(); // to the sum of the frequency of the two nodes // assigning values to the f node. f.data = x.data + y.data; f.c = '-'; // first extracted node as left child. f.left = x; // second extracted node as the right child. f.right = y; // marking the f node as the root node. root = f; // add this node to the priority-queue. q.add(f); } // print the codes by traversing the tree printCode(root, ''); } } // node class is the basic structure // of each node present in the Huffman - tree. class HuffmanNode { int data; char c; HuffmanNode left; HuffmanNode right; } // comparator class helps to compare the node // on the basis of one of its attribute. // Here we will be compared // on the basis of data values of the nodes. class MyComparator implements Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } </n;> Produzione
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 ………………. Process executed in 1.11 seconds Press any key to continue.
Spiegazione:
Attraversandolo, l'albero di Huffman viene creato e decodificato. I valori raccolti durante l'attraversamento devono poi essere applicati al carattere situato nel nodo foglia. Ogni carattere univoco nel flusso di dati fornito può essere identificato utilizzando il Codice Huffman in questo modo. O (nlogn), dove n è il numero totale di caratteri, è la complessità temporale. ExtractMin() viene chiamato 2*(n - 1) volte se ci sono n nodi. Poiché extractMin() chiama minHeapify(), il suo tempo di esecuzione è O (logn). La complessità totale è quindi O (nlogn). Esiste un algoritmo temporale lineare se l'array di input è ordinato. Questo sarà trattato più dettagliatamente nel nostro prossimo pezzo.
Problemi con la codifica Huffman
Parliamo degli svantaggi della codifica Huffman in questa parte e del perché non è sempre l'opzione migliore:
Java principale
- Se non tutte le probabilità o frequenze dei personaggi sono potenze negative di 2, non è considerato ideale.
- Anche se è possibile avvicinarsi all'ideale raggruppando i simboli ed espandendo l'alfabeto, il metodo di blocco richiede la gestione di un alfabeto più grande. Pertanto, la codifica di Huffman potrebbe non essere sempre molto efficace.
- Sebbene esistano molti modi efficaci per contare la frequenza di ciascun simbolo o carattere, ricostruire l'intero albero per ciascuno di essi può richiedere molto tempo. Quando l'alfabeto è grande e le distribuzioni di probabilità cambiano rapidamente con ciascun simbolo, in genere è così.
Algoritmo di costruzione del codice Greedy Huffman
- Huffman ha sviluppato una tecnica avida che genera un codice Huffman, un codice prefisso ideale, per ogni carattere distinto nel flusso di dati di input.
- L'approccio utilizza ogni volta il minor numero di nodi per creare l'albero di Huffman dal basso verso l'alto.
- Poiché ogni carattere riceve una lunghezza di codice in base alla frequenza con cui appare nel flusso di dati, questo metodo è noto come approccio greedy. È un elemento frequente nei dati se la dimensione del codice recuperato è inferiore.
L'uso della codifica Huffman
- Qui parleremo di alcuni usi pratici di Huffman Coding:
- I formati di compressione convenzionali come PKZIP, GZIP, ecc. utilizzano tipicamente la codifica Huffman.
- La codifica Huffman viene utilizzata per il trasferimento di dati tramite fax e testo perché riduce al minimo le dimensioni del file e aumenta la velocità di trasmissione.
- La codifica Huffman (in particolare i codici prefisso) viene utilizzata da diversi formati di archiviazione multimediale, inclusi JPEG, PNG e MP3, per comprimere i file.
- La codifica Huffman viene utilizzata principalmente per la compressione delle immagini.
- Quando è necessario inviare una stringa di caratteri spesso ricorrenti, può essere più utile.
Conclusione
- In generale, Huffman Coding è utile per comprimere dati che contengono caratteri ricorrenti.
- Possiamo vedere che il carattere che ricorre più frequentemente ha il codice più corto, mentre quello che ricorre meno frequentemente ha il codice più grande.
- La tecnica di compressione del codice Huffman viene utilizzata per creare una codifica a lunghezza variabile, che utilizza una quantità variabile di bit per ciascuna lettera o simbolo. Questo metodo è superiore alla codifica a lunghezza fissa poiché utilizza meno memoria e trasmette i dati più rapidamente.
- Leggi questo articolo per avere una migliore conoscenza dell'algoritmo greedy.