Le codage de Huffman est un algorithme de compression de données sans perte. L'idée est d'attribuer des codes de longueur variable aux caractères saisis, les longueurs des codes attribués sont basées sur les fréquences des caractères correspondants.
Les codes de longueur variable attribués aux caractères saisis sont Codes de préfixe , signifie que les codes (séquences de bits) sont attribués de telle manière que le code attribué à un caractère n'est pas le préfixe du code attribué à un autre caractère. C'est ainsi que Huffman Coding s'assure qu'il n'y a pas d'ambiguïté lors du décodage du flux binaire généré.
Comprenons les codes de préfixe avec un contre-exemple. Soit quatre caractères a, b, c et d, et leurs codes de longueur variable correspondants sont 00, 01, 0 et 1. Ce codage conduit à une ambiguïté car le code attribué à c est le préfixe des codes attribués à a et b. Si le flux binaire compressé est 0001, la sortie décompressée peut être cccd ou ccb ou acd ou ab.
Voir ce pour les applications du codage de Huffman.
Il y a principalement deux parties principales dans Huffman Coding
- Construisez un arbre de Huffman à partir des caractères saisis.
- Parcourez l'arbre de Huffman et attribuez des codes aux personnages.
Algorithme:
La méthode utilisée pour construire un code de préfixe optimal est appelée Codage de Huffman .
Cet algorithme construit un arbre de manière ascendante. On peut désigner cet arbre par T
Soit, |c| être le nombre de feuilles
|c| -1 est le nombre d'opérations nécessaires pour fusionner les nœuds. Q est la file d'attente prioritaire qui peut être utilisée lors de la construction du tas binaire.
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) }> Étapes pour construire l'arbre de Huffman
L'entrée est un tableau de caractères uniques ainsi que leur fréquence d'occurrence et la sortie est l'arbre de Huffman.
- Créez un nœud feuille pour chaque caractère unique et créez un tas min de tous les nœuds feuille (Min Heap est utilisé comme file d'attente prioritaire. La valeur du champ de fréquence est utilisée pour comparer deux nœuds dans le tas min. Initialement, le caractère le moins fréquent est à racine)
- Extrayez deux nœuds avec la fréquence minimale du tas min.
- Créez un nouveau nœud interne avec une fréquence égale à la somme des fréquences des deux nœuds. Faites du premier nœud extrait son enfant gauche et l'autre nœud extrait son enfant droit. Ajoutez ce nœud au tas min.
- Répétez les étapes 2 et 3 jusqu'à ce que le tas ne contienne qu'un seul nœud. Le nœud restant est le nœud racine et l’arborescence est complète.
Comprenons l'algorithme avec un exemple :
character Frequency a 5 b 9 c 12 d 13 e 16 f 45>
Étape 1. Créez un tas minimum contenant 6 nœuds où chaque nœud représente la racine d'un arbre avec un seul nœud.
Étape 2 Extrayez deux nœuds de fréquence minimale du tas min. Ajoutez un nouveau nœud interne de fréquence 5 + 9 = 14.
Illustration de l'étape 2
Maintenant, le tas minimum contient 5 nœuds où 4 nœuds sont des racines d'arbres avec un seul élément chacun, et un nœud de tas est la racine d'un arbre avec 3 éléments.
character Frequency c 12 d 13 Internal Node 14 e 16 f 45>
Étape 3: Extrayez deux nœuds de fréquence minimale du tas. Ajouter un nouveau nœud interne de fréquence 12 + 13 = 25
liste des utilisateurs MySQL
Illustration de l'étape 3
Désormais, le tas minimum contient 4 nœuds dont 2 nœuds sont des racines d'arbres avec un seul élément chacun, et deux nœuds de tas sont la racine d'un arbre avec plus d'un nœud.
character Frequency Internal Node 14 e 16 Internal Node 25 f 45>
Étape 4: Extrayez deux nœuds de fréquence minimale. Ajouter un nouveau nœud interne avec une fréquence 14 + 16 = 30
Illustration de l'étape 4
Désormais, le tas minimum contient 3 nœuds.
character Frequency Internal Node 25 Internal Node 30 f 45>
Étape 5 : Extrayez deux nœuds de fréquence minimale. Ajouter un nouveau nœud interne avec une fréquence 25 + 30 = 55
Illustration de l'étape 5
Maintenant, le tas min contient 2 nœuds.
character Frequency f 45 Internal Node 55>
Étape 6 : Extrayez deux nœuds de fréquence minimale. Ajouter un nouveau nœud interne avec une fréquence 45 + 55 = 100
Illustration de l'étape 6
Désormais, le tas min ne contient qu'un seul nœud.
character Frequency Internal Node 100>
Puisque le tas ne contient qu’un seul nœud, l’algorithme s’arrête ici.
Étapes pour imprimer les codes de Huffman Tree :
Parcourez l'arbre formé à partir de la racine. Maintenez un tableau auxiliaire. En vous déplaçant vers l'enfant de gauche, écrivez 0 dans le tableau. Tout en vous déplaçant vers le bon enfant, écrivez 1 dans le tableau. Imprimez le tableau lorsqu'un nœud feuille est rencontré.
Étapes pour imprimer le code de HuffmanTree
Les codes sont les suivants :
character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>Pratique recommandée Encodage Huffman Essayez-le !
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
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->gauche = temp->droite = NULL ;> >temp->données = données ;> >temp->fréquence = fréquence ;> > >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->taille = 0 ;> > >minHeap->capacité = capacité ;> > >minHeap->tableau = (>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->tableau[gauche]->freq> >array[smallest]->fréquence)> >smallest = left;> > >if> (right size> >&& minHeap->tableau[droite]->freq> >array[smallest]->fréquence)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->tableau[le plus petit],> >&minHeap->tableau[idx]);> >minHeapify(minHeap, smallest);> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->taille == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->tableau[0];> >minHeap->array[0] = minHeap->array[minHeap->size - 1];> > >--minHeap->taille;> >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->taille;> >int> i = minHeap->taille - 1 ;> > >while> (i> >&& minHeapNode->fréquence> >array[(i - 1) / 2]->fréquence) {> > >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->taille - 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->gauche) && !(racine->droite); } // Crée un tas min de capacité // égale à la taille et insère tous les caractères de // data[] dans le tas min. Initialement, la taille du // min tas est égale à la 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 fonction principale qui construit l'arbre de Huffman struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Étape 1 : Créer un tas minimum de capacité // égale à la taille struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Itérer pendant que la taille du tas ne devient pas 1 while (!isSizeOne(minHeap)) { //. Étape 2 : Extraire les deux éléments // de fréquence minimale du tas min left = extractMin(minHeap); right = extractMin(minHeap); // Étape 3 : Créer un nouveau nœud // interne avec une fréquence égale à // la somme des fréquences de deux nœuds. // Faire des deux nœuds extraits // les enfants gauche et droit de ce nouveau nœud. // Ajouter ce nœud au tas min // '$' est une valeur spéciale pour les nœuds internes, pas // utilisé top = newNode('$', gauche->freq + droite->freq); haut->gauche = gauche ; haut->droite = droite ; insertMinHeap(minHeap, haut); } // Étape 4 : Le nœud restant est le nœud // racine et l'arborescence est complète. return extractMin(minHeap); } // Imprime les codes Huffman à partir de la racine de Huffman Tree. // Il utilise arr[] pour stocker les codes void printCodes(struct MinHeapNode* root, int arr[], int top) { // Attribue 0 au bord gauche et se reproduit if (root->left) { arr[top] = 0 ; printCodes(root->left, arr, top + 1); } // Attribue 1 au bord droit et récidive if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // S'il s'agit d'un nœud feuille, alors // il contient l'un des // caractères d'entrée, imprime le caractère // et son code depuis arr[] if (isLeaf(root)) { printf('%c: ', racine->données); printArr(arr, haut); } } // La fonction principale qui construit un // arbre de Huffman et imprime les codes en parcourant // l'arbre de Huffman construit void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree (données, fréquence, taille) ; // Affiche les codes de Huffman en utilisant // l'arbre de Huffman construit ci-dessus int arr[MAX_TREE_HT], top = 0; printCodes(racine, arr, top); } // Code du pilote int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f ' } ; int fréquence[] = { 5, 9, 12, 13, 16, 45 }; int taille = taillede(arr) / taillede(arr[0]); HuffmanCodes (arr, fréquence, taille); renvoie 0 ; }> |
>
>
C++
tableau de retour Java
// 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->gauche = temp->droite = NULL ;> >temp->données = données ;> >temp->fréquence = fréquence ;> > >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->taille = 0 ;> > >minHeap->capacité = capacité ;> > >minHeap->tableau = (>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->tableau[gauche]->freq> >array[smallest]->fréquence)> >smallest = left;> > >if> (right size> >&& minHeap->tableau[droite]->freq> >array[smallest]->fréquence)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->tableau[le plus petit],> >&minHeap->tableau[idx]);> >minHeapify(minHeap, smallest);> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->taille == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->tableau[0];> >minHeap->array[0] = minHeap->array[minHeap->size - 1];> > >--minHeap->taille;> >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->taille;> >int> i = minHeap->taille - 1 ;> > >while> (i> >&& minHeapNode->fréquence> >array[(i - 1) / 2]->fréquence) {> > >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->taille - 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->gauche) && !(racine->droite); } // Crée un tas min de capacité // égale à la taille et insère tous les caractères de // data[] dans le tas min. Initialement, la taille du // min tas est égale à la 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 fonction principale qui construit l'arbre de Huffman struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Étape 1 : Créer un tas minimum de capacité // égale à la taille struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Itérer pendant que la taille du tas ne devient pas 1 while (!isSizeOne(minHeap)) { //. Étape 2 : Extraire les deux éléments // de fréquence minimale du tas min left = extractMin(minHeap); right = extractMin(minHeap); // Étape 3 : Créer un nouveau nœud // interne avec une fréquence égale à // la somme des fréquences de deux nœuds. // Faire des deux nœuds extraits // les enfants gauche et droit de ce nouveau nœud. // Ajouter ce nœud au tas min // '$' est une valeur spéciale pour les nœuds internes, pas // utilisé top = newNode('$', gauche->freq + droite->freq); haut->gauche = gauche ; haut->droite = droite ; insertMinHeap(minHeap, haut); } // Étape 4 : Le nœud restant est le nœud // racine et l'arborescence est complète. return extractMin(minHeap); } // Imprime les codes Huffman à partir de la racine de Huffman Tree. // Il utilise arr[] pour stocker les codes void printCodes(struct MinHeapNode* root, int arr[], int top) { // Attribue 0 au bord gauche et récidive if (root->left) { arr[top] = 0 ; printCodes(root->left, arr, top + 1); } // Attribue 1 au bord droit et récidive if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // S'il s'agit d'un nœud feuille, alors // il contient l'un des caractères // d'entrée, imprime le caractère // et son code depuis arr[] if (isLeaf(root)) { cout ': '; printArr(arr, haut); } } // La fonction principale qui construit un // arbre de Huffman et imprime les codes en parcourant // l'arbre de Huffman construit void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree (données, fréquence, taille) ; // Affiche les codes de Huffman en utilisant // l'arbre de Huffman construit ci-dessus int arr[MAX_TREE_HT], top = 0; printCodes(racine, arr, top); } // Code du pilote int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f ' } ; int fréquence[] = { 5, 9, 12, 13, 16, 45 }; int taille = taillede(arr) / taillede(arr[0]); HuffmanCodes (arr, fréquence, taille); renvoie 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>->données = données ;> >this>->fréquence = fréquence ;> >}> };> > // For comparison of> // two heap nodes (needed in min heap)> struct> compare {> > >bool> operator()(MinHeapNode* l, MinHeapNode* r)> > >{> >return> (l->fréq> r->fréq);> >}> };> > // Prints huffman codes from> // the root of Huffman Tree.> void> printCodes(>struct> MinHeapNode* root, string str)> {> > >if> (!root)> >return>;> > >if> (root->données !=>'$'>)> >cout ': ' << str << '
'; printCodes(root->gauche, str + '0'); printCodes(root->right, str + '1'); } // La fonction principale qui construit un arbre de Huffman et // imprime les codes en parcourant l'arbre de Huffman construit void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Crée un tas min et insère tous les caractères de data[] priorité_queue compare> minHeap; for (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Itérer pendant que la taille du tas ne devient pas 1 while (minHeap.size() != 1 ) { // Extraire les deux éléments de // fréquence minimale du tas min left = minHeap.top(); minHeap.pop(); right = minHeap.top(); // Créer un nouveau nœud interne avec // une fréquence égale à la somme des // fréquences des deux nœuds. Faites // des deux nœuds extraits comme enfants gauche et droit // de ce nouveau nœud. Ajoutez ce nœud // au tas min '$' est. une valeur spéciale // pour les nœuds internes, non utilisée top = new MinHeapNode('$', left->freq + right->freq); (top); } // Imprimer les codes de Huffman en utilisant // l'arbre de Huffman construit ci-dessus printCodes(minHeap.top(), ''); } // Driver Code int main() { char arr[] = { ' a', 'b', 'c', 'd', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16 , 45 }; int taille = taillede(arr) / taillede(arr[0]); renvoie 0 ; } // Ce code est contribué par Aditya Goel> |
>
>
Java
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) { // extrait de la première minute. HuffmanNode x = q.peek(); q.poll(); // deuxième extrait min. HuffmanNode y = q.peek(); q.poll(); // nouveau nœud f qui est égal à HuffmanNode f = new HuffmanNode(); // à la somme des fréquences des deux nœuds // en attribuant des valeurs au nœud f. f.data = x.data + y.data; f.c = '-'; // premier nœud extrait en tant qu'enfant gauche. f.gauche = x; // deuxième nœud extrait en tant qu'enfant droit. f.right = y; // marquant le nœud f comme nœud racine. racine = f; // ajoute ce nœud à la file d'attente des priorités. q.ajouter(f); } // affiche les codes en parcourant l'arborescence printCode(root, ''); } } // La classe de nœuds est la structure de base // de chaque nœud présent dans l'arbre de Huffman. classe HuffmanNode { données int ; char c; HuffmanNode à gauche ; HuffmanNode à droite ; } // La classe comparateur permet de comparer le nœud // sur la base de l'un de ses attributs. // Ici, nous serons comparés // sur la base des valeurs de données des nœuds. class MyComparator implémente Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // Ce code est fourni par 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}') # caractères pour les caractères de l'arbre de Huffman = ['a', 'b', 'c', 'd', 'e', 'f'] # fréquence des caractères freq = [5, 9, 12, 13, 16, 45] # liste contenant les nœuds inutilisés nodes = [] # conversion des caractères et des fréquences # en nœuds de l'arbre de Huffman pour x in range(len(chars)): heapq .heappush(nodes, node(freq[x], chars[x])) while len(nodes)> 1 : # trie tous les nœuds par ordre croissant # en fonction de leur fréquence left = heapq.heappop(nodes) right = heapq .heappop(nodes) # attribue une valeur directionnelle à ces nœuds left.huff = 0 right.huff = 1 # combine les 2 plus petits nœuds pour créer # un nouveau nœud en tant que parent newNode = node(left.freq+right.freq, left. symbol+right.symbol, left, right) heapq.heappush(nodes, newNode) # L'arbre de Huffman est prêt ! printNodes(noeuds[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) { // extrait de la première minute. soit x = q[0]; q.shift(); // deuxième extrait min. soit y = q[0]; q.shift(); // nouveau nœud f qui est égal let f = new HuffmanNode(); // à la somme des fréquences des deux nœuds // en attribuant des valeurs au nœud f. f.data = x.data + y.data; f.c = '-'; // premier nœud extrait en tant qu'enfant gauche. f.gauche = x; // deuxième nœud extrait en tant qu'enfant de droite. f.right = y; // marquant le nœud f comme nœud racine. racine = f; // ajoute ce nœud à la file d'attente des priorités. q.push(f); q.sort(function(a,b){return a.data-b.data;}); } // affiche les codes en parcourant l'arborescence printCode(root, ''); // Ce code est contribué par 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> |
bash vérifie si la variable d'environnement est définie
>
>Sortir
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>
Complexité temporelle : O(nlogn) où n est le nombre de caractères uniques. S'il y a n nœuds, extractMin() est appelé 2*(n – 1) fois. extractMin() prend du temps O(logn) lorsqu'il appelle minHeapify(). Ainsi, la complexité globale est O(nlogn).
Si le tableau d'entrée est trié, il existe un algorithme de temps linéaire. Nous en reparlerons bientôt dans notre prochain article.
Complexité spatiale : - O(N)
Applications du codage de Huffman :
- Ils sont utilisés pour transmettre des fax et des textes.
- Ils sont utilisés par les formats de compression conventionnels comme PKZIP, GZIP, etc.
- Les codecs multimédia comme JPEG, PNG et MP3 utilisent le codage Huffman (pour être plus précis les codes de préfixe).
Ceci est utile dans les cas où il existe une série de caractères fréquents.
Référence:
http://en.wikipedia.org/wiki/Huffman_coding
Cet article est compilé par Aashish Barnwal et révisé par l'équipe techcodeview.com.