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

1. Costruisci un albero di Huffman dai personaggi immessi.
2. 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.

1. 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)
2. Estrai due nodi con la frequenza minima dall'heap minimo.
   
3. 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.
4. 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

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++

// 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>

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

> > // 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:

1. Sono utilizzati per la trasmissione di fax e testo.
2. Sono utilizzati dai formati di compressione convenzionali come PKZIP, GZIP, ecc.
3. 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.