La codifica di Huffman è un algoritmo di compressione dei dati senza perdita di dati. L'idea è di assegnare codici di lunghezza variabile ai caratteri di input, le lunghezze dei codici assegnati sono basate sulle frequenze dei caratteri corrispondenti.
I codici a lunghezza variabile assegnati ai caratteri di input sono Codici prefisso , significa che i codici (sequenze di bit) sono assegnati in modo tale che il codice assegnato a un carattere non sia il prefisso del codice assegnato a qualsiasi altro carattere. In questo modo Huffman Coding garantisce che non vi siano ambiguità durante la decodifica del bitstream generato.
Cerchiamo di comprendere i codici prefisso con un controesempio. Supponiamo che ci siano quattro caratteri a, b, c e d e che i corrispondenti codici a lunghezza variabile siano 00, 01, 0 e 1. Questa codifica porta all'ambiguità perché il codice assegnato a c è il prefisso dei codici assegnati ad a e b. Se il flusso di bit compresso è 0001, l'output decompresso può essere cccd o ccb o acd o ab.
Vedere Questo per applicazioni di codifica Huffman.
Ci sono principalmente due parti principali in Huffman Coding
- Costruisci un albero di Huffman dai personaggi immessi.
- Attraversa l'Huffman Tree e assegna i codici ai personaggi.
Algoritmo:
Viene chiamato il metodo utilizzato per costruire il codice del prefisso ottimale Codifica di Huffman .
Questo algoritmo costruisce un albero in modo bottom-up. Possiamo denotare questo albero con T
Sia |c| essere il numero di foglie
|c| -1 è il numero di operazioni necessarie per unire i nodi. Q sia la coda con priorità che può essere utilizzata durante la costruzione dell'heap binario.
Algorithm Huffman (c) { n= |c| Q = c for i<-1 to n-1 do { temp <- get node () left (temp] Get_min (Q) right [temp] Get Min (Q) a = left [templ b = right [temp] F [temp]<- f[a] + [b] insert (Q, temp) } return Get_min (0) }> Passi per costruire l'Huffman Tree
L'input è una serie di caratteri univoci insieme alla loro frequenza di occorrenza e l'output è Huffman Tree.
- Crea un nodo foglia per ogni carattere univoco e crea un heap minimo di tutti i nodi foglia (il Min Heap viene utilizzato come coda di priorità. Il valore del campo frequenza viene utilizzato per confrontare due nodi nell'heap minimo. Inizialmente, il carattere meno frequente è a radice)
- Estrai due nodi con la frequenza minima dall'heap minimo.
- Crea un nuovo nodo interno con una frequenza pari alla somma delle frequenze dei due nodi. Rendi il primo nodo estratto come figlio sinistro e l'altro nodo estratto come figlio destro. Aggiungi questo nodo all'heap minimo.
- Ripetere i passaggi n. 2 e n. 3 finché l'heap non contiene un solo nodo. Il nodo rimanente è il nodo radice e l'albero è completo.
Cerchiamo di comprendere l'algoritmo con un esempio:
character Frequency a 5 b 9 c 12 d 13 e 16 f 45>
Passo 1. Costruisci un heap minimo che contenga 6 nodi in cui ciascun nodo rappresenta la radice di un albero con un singolo nodo.
Passo 2 Estrai due nodi di frequenza minima dall'heap minimo. Aggiungi un nuovo nodo interno con frequenza 5 + 9 = 14.
Illustrazione del passaggio 2
Ora l'heap minimo contiene 5 nodi dove 4 nodi sono radici di alberi con un singolo elemento ciascuno e un nodo heap è la radice dell'albero con 3 elementi
versione java linux
character Frequency c 12 d 13 Internal Node 14 e 16 f 45>
Passaggio 3: Estrai due nodi di frequenza minima dall'heap. Aggiungi un nuovo nodo interno con frequenza 12 + 13 = 25
Illustrazione del passaggio 3
Ora l'heap minimo contiene 4 nodi dove 2 nodi sono radici di alberi con un singolo elemento ciascuno e due nodi heap sono radici di alberi con più di un nodo
character Frequency Internal Node 14 e 16 Internal Node 25 f 45>
Passaggio 4: Estrai due nodi di frequenza minima. Aggiungi un nuovo nodo interno con frequenza 14 + 16 = 30
Illustrazione del passaggio 4
Ora l'heap minimo contiene 3 nodi.
character Frequency Internal Node 25 Internal Node 30 f 45>
Passaggio 5: Estrai due nodi di frequenza minima. Aggiungi un nuovo nodo interno con frequenza 25 + 30 = 55
Illustrazione del passaggio 5
Ora l'heap minimo contiene 2 nodi.
character Frequency f 45 Internal Node 55>
Passaggio 6: Estrai due nodi di frequenza minima. Aggiungi un nuovo nodo interno con frequenza 45 + 55 = 100
Illustrazione del passaggio 6
Ora l'heap minimo contiene un solo nodo.
character Frequency Internal Node 100>
Poiché l'heap contiene un solo nodo, l'algoritmo si ferma qui.
Passaggi per stampare i codici da Huffman Tree:
Attraversare l'albero formato partendo dalla radice. Mantenere un array ausiliario. Mentre ti sposti sul figlio sinistro, scrivi 0 nell'array. Mentre ti sposti sul figlio destro, scrivi 1 nell'array. Stampa l'array quando viene incontrato un nodo foglia.
Passaggi per stampare il codice da HuffmanTree
I codici sono i seguenti:
character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>Pratica consigliata per la codifica Huffman Provalo!
Di seguito è riportata l'implementazione dell'approccio di cui sopra:
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->sinistra = temp->destra = NULL;> >temp->dati = dati;> >temp->frequenza = frequenza;> > >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->dimensione = 0;> > >minHeap->capacità = capacità;> > >minHeap->matrice = (>struct> MinHeapNode**)>malloc>(> >minHeap->capacità *>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[sinistra]->freq> >array[smallest]->frequenza)> >smallest = left;> > >if> (right size> >&& minHeap->array[destra]->freq> >array[smallest]->frequenza)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->array[più piccolo],> >&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->taglia == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->matrice[0];> >minHeap->array[0] = minHeap->array[minHeap->dimensione - 1];> > >--minHeap->misurare;> >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->misurare;> >int> i = minHeap->dimensione - 1;> > >while> (i> >&& minHeapNode->frequenza> >array[(i - 1) / 2]->frequenza) {> > >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->dimensione - 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 printf('%d', arr[i]); printf('
'); } // Utility function to check if this node is leaf int isLeaf(struct MinHeapNode* root) { return !(root->sinistra) && !(radice->destra); } // Crea un heap minimo di capacità // uguale alla dimensione e inserisce tutti i caratteri di // data[] nell'heap minimo. Inizialmente la dimensione // min heap è uguale alla capacità struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i minHeap->array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // La funzione principale che costruisce l'albero di Huffman struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Passaggio 1: crea un heap minimo di capacità // uguale alla dimensione Inizialmente, ci sono // modalità uguali a size. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size) { // Itera mentre la dimensione dell'heap non diventa 1 while (!isSizeOne(minHeap)); Passaggio 2: estrarre i due elementi // freq minimi da min heap left = extractMin(minHeap); right = extractMin(minHeap); Passaggio 3: creare un nuovo // nodo interno con frequenza uguale alla // somma di frequenze di due nodi. // Rendi i due nodi estratti come // figli sinistro e destro di questo nuovo nodo // Aggiungi questo nodo all'heap minimo // '$' è un valore speciale per i nodi interni, non //. usato top = newNode('$', sinistra->freq + destra->freq); in alto->sinistra = sinistra; in alto->destra = destra; insertMinHeap(minHeap, superiore); } // Passo 4: Il nodo rimanente è il // nodo radice e l'albero è completo. return estrattoMin(minHeap); } // Stampa i codici Huffman dalla radice di Huffman Tree. // Utilizza arr[] per memorizzare i codici void printCodes(struct MinHeapNode* root, int arr[], int top) { // Assegna 0 al bordo sinistro e ricorsi if (root->left) { arr[top] = 0 ; printCodes(root->left, arr, top + 1); } // Assegna 1 al bordo destro e ricorre if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Se questo è un nodo foglia, allora // contiene uno dei // caratteri di input, stampa il carattere // e il suo codice da arr[] if (isLeaf(root)) { printf('%c: ', root->dati); printArr(arr, superiore); } } // La funzione principale che costruisce un // Huffman Tree e stampa i codici attraversando // l'Huffman Tree creato void HuffmanCodes(char data[], int freq[], int size) { // Costruisci Huffman Tree struct MinHeapNode* root = buildHuffmanTree(dati, frequenza, dimensione); // Stampa i codici Huffman utilizzando // l'albero Huffman costruito sopra int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Codice driver int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f '}; int frequenza[] = { 5, 9, 12, 13, 16, 45 }; int dimensione = dimensioneof(arr) / dimensioneof(arr[0]); HuffmanCodes(arr, freq, dimensione); restituire 0; }> |
>
>
C++
// C++ program for Huffman Coding> #include> #include> using> namespace> std;> > // 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->sinistra = temp->destra = NULL;> >temp->dati = dati;> >temp->frequenza = frequenza;> > >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->dimensione = 0;> > >minHeap->capacità = capacità;> > >minHeap->matrice = (>struct> MinHeapNode**)>malloc>(> >minHeap->capacità *>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[sinistra]->freq> >array[smallest]->frequenza)> >smallest = left;> > >if> (right size> >&& minHeap->array[destra]->freq> >array[smallest]->frequenza)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->array[più piccolo],> >&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->taglia == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->matrice[0];> >minHeap->array[0] = minHeap->array[minHeap->dimensione - 1];> > >--minHeap->misurare;> >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->misurare;> >int> i = minHeap->dimensione - 1;> > >while> (i> >&& minHeapNode->frequenza> >array[(i - 1) / 2]->frequenza) {> > >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->dimensione - 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 cout << arr[i]; cout << '
'; } // Utility function to check if this node is leaf int isLeaf(struct MinHeapNode* root) { return !(root->sinistra) && !(radice->destra); } // Crea un heap minimo di capacità // uguale alla dimensione e inserisce tutti i caratteri di // data[] nell'heap minimo. Inizialmente la dimensione // min heap è uguale alla capacità struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i minHeap->array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // La funzione principale che costruisce l'albero di Huffman struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Passaggio 1: crea un heap minimo di capacità // uguale alla dimensione Inizialmente, ci sono // modalità uguali a size. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size) { // Itera mentre la dimensione dell'heap non diventa 1 while (!isSizeOne(minHeap)); Passaggio 2: estrarre i due elementi // freq minimi da min heap left = extractMin(minHeap); right = extractMin(minHeap); Passaggio 3: creare un nuovo // nodo interno con frequenza uguale alla // somma di frequenze di due nodi. // Rendi i due nodi estratti come // figli sinistro e destro di questo nuovo nodo // Aggiungi questo nodo all'heap minimo // '$' è un valore speciale per i nodi interni, non //. usato top = newNode('$', sinistra->freq + destra->freq); in alto->sinistra = sinistra; in alto->destra = destra; insertMinHeap(minHeap, superiore); } // Passo 4: Il nodo rimanente è il // nodo radice e l'albero è completo. return estrattoMin(minHeap); } // Stampa i codici Huffman dalla radice di Huffman Tree. // Utilizza arr[] per memorizzare i codici void printCodes(struct MinHeapNode* root, int arr[], int top) { // Assegna 0 al bordo sinistro e ricorsi if (root->left) { arr[top] = 0 ; printCodes(root->left, arr, top + 1); } // Assegna 1 al bordo destro e ricorsi if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Se questo è un nodo foglia, allora // contiene uno dei // caratteri di input, stampa il carattere // e il suo codice da arr[] if (isLeaf(root)) { cout ': '; printArr(arr, superiore); } } // La funzione principale che costruisce un // Huffman Tree e stampa i codici attraversando // l'Huffman Tree creato void HuffmanCodes(char data[], int freq[], int size) { // Costruisci Huffman Tree struct MinHeapNode* root = buildHuffmanTree(dati, frequenza, dimensione); // Stampa i codici Huffman utilizzando // l'albero Huffman costruito sopra int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Codice driver int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f '}; int frequenza[] = { 5, 9, 12, 13, 16, 45 }; int dimensione = dimensioneof(arr) / dimensioneof(arr[0]); HuffmanCodes(arr, freq, dimensione); restituire 0; }> |
>
>
C++
codice di codifica huffman
// C++(STL) program for Huffman Coding with STL> #include> using> namespace> std;> > // A Huffman tree node> struct> MinHeapNode {> > >// One of the input characters> >char> data;> > >// Frequency of the character> >unsigned freq;> > >// Left and right child> >MinHeapNode *left, *right;> > >MinHeapNode(>char> data, unsigned freq)> > >{> > >left = right = NULL;> >this>->dati = dati;> >this>->frequenza = frequenza;> >}> };> > // For comparison of> // two heap nodes (needed in min heap)> struct> compare {> > >bool> operator()(MinHeapNode* l, MinHeapNode* r)> > >{> >return> (l->frequenza> r->freq);> >}> };> > // Prints huffman codes from> // the root of Huffman Tree.> void> printCodes(>struct> MinHeapNode* root, string str)> {> > >if> (!root)> >return>;> > >if> (root->dati !=>'$'>)> >cout ': ' << str << '
'; printCodes(root->sinistra, str + '0'); printCodes(root->destra, str + '1'); } // La funzione principale che costruisce un Huffman Tree e // stampa i codici attraversando l'Huffman Tree creato void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Crea un heap minimo e inserisce tutti i caratteri di data[] priority_queue compare> minHeap; for (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Itera mentre la dimensione dell'heap non diventa 1 while (minHeap.size() != 1 ) { // Estrai i due elementi // minimi da min heap left = minHeap.pop(); right = minHeap.pop(); con // frequenza uguale alla somma delle // frequenze dei due nodi. Rendi i // due nodi estratti come figli sinistro e destro // di questo nuovo nodo. Aggiungi questo nodo // all'heap minimo '$' un valore speciale // per i nodi interni, non utilizzato top = new MinHeapNode('$', left->freq + right->freq); (top); } // Stampa i codici Huffman utilizzando // l'albero Huffman creato sopra printCodes(minHeap.top(), '') } // Codice driver int main() { char arr[] = { '); a', 'b', 'c', 'd', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16 , 45 }; int dimensione = dimensione(arr) / dimensione(arr[0]); HuffmanCodes(arr, frequenza, dimensione); restituire 0; } // Questo codice è un contributo di Aditya Goel> |
>
>
Giava
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 // 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; // add functions adds // the huffman node to the queue. q.add(hn); } // create a root node HuffmanNode root = null; // Here we will extract the two minimum value // from the heap each time until // its size reduces to 1, extract until // all the nodes are extracted. while (q.size()>1) { // estratto del primo minuto. HuffmanNode x = q.peek(); q.sondaggio(); // estratto del secondo minuto. HuffmanNode y = q.peek(); q.poll(); // nuovo nodo f che è uguale HuffmanNode f = new HuffmanNode(); // alla somma delle frequenze dei due nodi // assegnando valori al nodo f. f.dati = x.dati + y.dati; f.c = '-'; // primo nodo estratto come figlio sinistro. f.sinistra = x; // secondo nodo estratto come figlio destro. f.destra = y; // contrassegna il nodo f come nodo radice. radice = f; // aggiunge questo nodo alla coda di priorità. q.add(f); } // stampa i codici attraversando l'albero printCode(root, ''); } } // la classe del nodo è la struttura di base // di ciascun nodo presente nell'albero di Huffman. class HuffmanNode { int dati; carattere c; HuffmanNodo a sinistra; HuffmanNodo a destra; } // la classe comparatore aiuta a confrontare il nodo // sulla base di uno dei suoi attributi. // Qui verremo confrontati // sulla base dei valori dei dati dei nodi. class MyComparator implementa Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // Questo codice è un contributo di Kunwar Desh Deepak Singh> |
>
>
sincronizzazione dei thread
Python3
# A Huffman Tree Node> import> heapq> > > class> node:> >def> __init__(>self>, freq, symbol, left>=>None>, right>=>None>):> ># frequency of symbol> >self>.freq>=> freq> > ># symbol name (character)> >self>.symbol>=> symbol> > ># node left of current node> >self>.left>=> left> > ># node right of current node> >self>.right>=> right> > ># tree direction (0/1)> >self>.huff>=> ''> > >def> __lt__(>self>, nxt):> >return> self>.freq # utility function to print huffman # codes for all symbols in the newly # created Huffman tree def printNodes(node, val=''): # huffman code for current node newVal = val + str(node.huff) # if node is not an edge node # then traverse inside it if(node.left): printNodes(node.left, newVal) if(node.right): printNodes(node.right, newVal) # if node is edge node then # display its huffman code if(not node.left and not node.right): print(f'{node.symbol} ->{newVal}') # caratteri per i caratteri dell'albero di Huffman = ['a', 'b', 'c', 'd', 'e', 'f'] # frequenza dei caratteri freq = [5, 9, 12, 13, 16, 45] # lista contenente i nodi non utilizzati nodes = [] # conversione di caratteri e frequenze # in huffman tree nodes for x in range(len(chars)): heapq .heappush(nodes, node(freq[x], chars[x])) while len(nodes)> 1: # ordina tutti i nodi in ordine crescente # in base alla loro frequenza left = heapq.heappop(nodes) right = heapq .heappop(nodes) # assegna un valore direzionale a questi nodi left.huff = 0 right.huff = 1 # combina i 2 nodi più piccoli per creare # un nuovo nodo come genitore newNode = node(left.freq+right.freq, left. simbolo+destra.simbolo, sinistra, destra) heapq.heappush(nodi, nuovoNodo) # L'Huffman Tree è pronto! printNodi(nodi[0])> |
>
>
Javascript
stato git -s
> > // node class is the basic structure> // of each node present in the Huffman - tree.> class HuffmanNode> {> >constructor()> >{> >this>.data = 0;> >this>.c =>''>;> >this>.left =>this>.right =>null>;> >}> }> > // recursive function to print the> >// huffman-code through the tree traversal.> >// Here s is the huffman - code generated.> >function> printCode(root,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> >&& (root.c).toLowerCase() != (root.c).toUpperCase()) {> > >// c is the character in the node> >document.write(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> // number of characters.> >let n = 6;> >let charArray = [>'a'>,>'b'>,>'c'>,>'d'>,>'e'>,>'f'> ];> >let charfreq = [ 5, 9, 12, 13, 16, 45 ];> > >// creating a priority queue q.> >// makes a min-priority queue(min-heap).> >let q = [];> > >for> (let i = 0; i // creating a Huffman node object // and add it to the priority queue. let hn = new HuffmanNode(); hn.c = charArray[i]; hn.data = charfreq[i]; hn.left = null; hn.right = null; // add functions adds // the huffman node to the queue. q.push(hn); } // create a root node let root = null; q.sort(function(a,b){return a.data-b.data;}); // Here we will extract the two minimum value // from the heap each time until // its size reduces to 1, extract until // all the nodes are extracted. while (q.length>1) { // estratto del primo minuto. sia x = q[0]; q.shift(); // estratto del secondo minuto. sia y = q[0]; q.shift(); // nuovo nodo f che è uguale let f = new HuffmanNode(); // alla somma delle frequenze dei due nodi // assegnando valori al nodo f. f.dati = x.dati + y.dati; f.c = '-'; // primo nodo estratto come figlio sinistro. f.sinistra = x; // secondo nodo estratto come figlio destro. f.destra = y; // contrassegna il nodo f come nodo radice. radice = f; // aggiunge questo nodo alla coda di priorità. q.spingere(f); q.sort(funzione(a,b){return a.data-b.data;}); } // stampa i codici attraversando l'albero printCode(root, ''); // Questo codice è stato fornito da avanitrachhadiya2155> |
>
>
C#
// C# program for the above approach> > using> System;> using> System.Collections.Generic;> > // A Huffman tree node> public> class> MinHeapNode> {> >// One of the input characters> >public> char> data;> > >// Frequency of the character> >public> uint> freq;> > >// Left and right child> >public> MinHeapNode left, right;> > >public> MinHeapNode(>char> data,>uint> freq)> >{> >left = right =>null>;> >this>.data = data;> >this>.freq = freq;> >}> }> > // For comparison of two heap nodes (needed in min heap)> public> class> CompareMinHeapNode : IComparer> {> >public> int> Compare(MinHeapNode x, MinHeapNode y)> >{> >return> x.freq.CompareTo(y.freq);> >}> }> > class> Program> {> >// Prints huffman codes from the root of Huffman Tree.> >static> void> printCodes(MinHeapNode root,>string> str)> >{> >if> (root ==>null>)> >return>;> > >if> (root.data !=>'$'>)> >Console.WriteLine(root.data +>': '> + str);> > >printCodes(root.left, str +>'0'>);> >printCodes(root.right, str +>'1'>);> >}> > >// The main function that builds a Huffman Tree and> >// print codes by traversing the built Huffman Tree> >static> void> HuffmanCodes(>char>[] data,>uint>[] freq,>int> size)> >{> >MinHeapNode left, right, top;> > >// Create a min heap & inserts all characters of data[]> >var> minHeap =>new> SortedSet(>new> CompareMinHeapNode());> > >for> (>int> i = 0; i minHeap.Add(new MinHeapNode(data[i], freq[i])); // Iterate while size of heap doesn't become 1 while (minHeap.Count != 1) { // Extract the two minimum freq items from min heap left = minHeap.Min; minHeap.Remove(left); right = minHeap.Min; minHeap.Remove(right); // 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 = new MinHeapNode('$', left.freq + right.freq); top.left = left; top.right = right; minHeap.Add(top); } // Print Huffman codes using the Huffman tree built above printCodes(minHeap.Min, ''); } // Driver Code static void Main() { char[] arr = { 'a', 'b', 'c', 'd', 'e', 'f' }; uint[] freq = { 5, 9, 12, 13, 16, 45 }; int size = arr.Length; HuffmanCodes(arr, freq, size); } } // This code is contributed by sdeadityasharma> |
>
>Produzione
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>
Complessità temporale: O(nlogn) dove n è il numero di caratteri univoci. Se ci sono n nodi, extractMin() viene chiamato 2*(n – 1) volte. extractMin() impiega tempo O(logn) mentre chiama minHeapify(). Quindi, la complessità complessiva è O(nlogn).
Se l'array di input è ordinato, esiste un algoritmo temporale lineare. Di questo parleremo presto nel nostro prossimo post.
Complessità spaziale: - O(N)
Applicazioni della codifica Huffman:
- Sono utilizzati per la trasmissione di fax e testo.
- Sono utilizzati dai formati di compressione convenzionali come PKZIP, GZIP, ecc.
- I codec multimediali come JPEG, PNG e MP3 utilizzano la codifica Huffman (per essere più precisi i codici di prefisso).
È utile nei casi in cui è presente una serie di caratteri ricorrenti.
Riferimento:
http://en.wikipedia.org/wiki/Huffman_coding
Questo articolo è stato compilato da Aashish Barnwal e rivisto dal team techcodeview.com.