La codificación Huffman es un algoritmo de compresión de datos sin pérdidas. La idea es asignar códigos de longitud variable a los caracteres de entrada; las longitudes de los códigos asignados se basan en las frecuencias de los caracteres correspondientes.
Los códigos de longitud variable asignados a los caracteres de entrada son Códigos de prefijo , significa que los códigos (secuencias de bits) se asignan de tal manera que el código asignado a un carácter no sea el prefijo del código asignado a ningún otro carácter. Así es como Huffman Coding se asegura de que no haya ambigüedad al decodificar el flujo de bits generado.
Entendamos los códigos de prefijo con un ejemplo de contador. Sean cuatro caracteres a, b, cy d, y sus correspondientes códigos de longitud variable sean 00, 01, 0 y 1. Esta codificación genera ambigüedad porque el código asignado a c es el prefijo de los códigos asignados a a y b. Si el flujo de bits comprimido es 0001, la salida descomprimida puede ser cccd o ccb o acd o ab.
Ver este para aplicaciones de codificación Huffman.
Hay principalmente dos partes principales en Huffman Coding
- Construya un árbol Huffman a partir de los caracteres ingresados.
- Atraviesa el árbol Huffman y asigna códigos a los personajes.
Algoritmo:
El método que se utiliza para construir el código de prefijo óptimo se llama Codificación Huffman .
Este algoritmo construye un árbol de abajo hacia arriba. Podemos denotar este árbol por t
Sea, |c| ser numero de hojas
|c| -1 es el número de operaciones necesarias para fusionar los nodos. Q sea la cola de prioridad que se puede utilizar al construir el montón 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) }> Pasos para construir el árbol Huffman
La entrada es una serie de caracteres únicos junto con su frecuencia de aparición y la salida es el árbol de Huffman.
- Cree un nodo hoja para cada carácter único y cree un montón mínimo de todos los nodos hoja (el montón mínimo se usa como cola de prioridad. El valor del campo de frecuencia se usa para comparar dos nodos en el montón mínimo. Inicialmente, el carácter menos frecuente está en raíz)
- Extraiga dos nodos con la frecuencia mínima del montón mínimo.
- Cree un nuevo nodo interno con una frecuencia igual a la suma de las frecuencias de los dos nodos. Haga que el primer nodo extraído sea su hijo izquierdo y el otro nodo extraído como su hijo derecho. Agregue este nodo al montón mínimo.
- Repita los pasos 2 y 3 hasta que el montón contenga solo un nodo. El nodo restante es el nodo raíz y el árbol está completo.
Entendamos el algoritmo con un ejemplo:
character Frequency a 5 b 9 c 12 d 13 e 16 f 45>
Paso 1. Construya un montón mínimo que contenga 6 nodos donde cada nodo represente la raíz de un árbol con un solo nodo.
Paso 2 Extraiga dos nodos de frecuencia mínima del montón mínimo. Agregue un nuevo nodo interno con frecuencia 5 + 9 = 14.
Ilustración del paso 2
Ahora el montón mínimo contiene 5 nodos, donde 4 nodos son raíces de árboles con un solo elemento cada uno, y un nodo del montón es la raíz de un árbol con 3 elementos.
character Frequency c 12 d 13 Internal Node 14 e 16 f 45>
Paso 3: Extraiga dos nodos de frecuencia mínima del montón. Agregue un nuevo nodo interno con frecuencia 12 + 13 = 25
Ilustración del paso 3
Ahora el montón mínimo contiene 4 nodos, donde 2 nodos son raíces de árboles con un solo elemento cada uno, y dos nodos del montón son raíces de un árbol con más de un nodo.
character Frequency Internal Node 14 e 16 Internal Node 25 f 45>
Etapa 4: Extraiga dos nodos de frecuencia mínima. Agregue un nuevo nodo interno con frecuencia 14 + 16 = 30
Ilustración del paso 4
Ahora el montón mínimo contiene 3 nodos.
character Frequency Internal Node 25 Internal Node 30 f 45>
Paso 5: Extraiga dos nodos de frecuencia mínima. Agregue un nuevo nodo interno con frecuencia 25 + 30 = 55
Ilustración del paso 5
Ahora el montón mínimo contiene 2 nodos.
character Frequency f 45 Internal Node 55>
Paso 6: Extraiga dos nodos de frecuencia mínima. Agregue un nuevo nodo interno con frecuencia 45 + 55 = 100
Ilustración del paso 6
Ahora el montón mínimo contiene solo un nodo.
character Frequency Internal Node 100>
Dado que el montón contiene sólo un nodo, el algoritmo se detiene aquí.
Pasos para imprimir códigos de Huffman Tree:
Recorre el árbol formado a partir de la raíz. Mantener una matriz auxiliar. Mientras se mueve hacia el hijo izquierdo, escriba 0 en la matriz. Mientras se mueve hacia el hijo derecho, escriba 1 en la matriz. Imprima la matriz cuando se encuentre un nodo hoja.
Pasos para imprimir código desde HuffmanTree
Los códigos son los siguientes:
character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>Práctica recomendada Codificación Huffman ¡Pruébelo!
A continuación se muestra la implementación del enfoque anterior:
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->izquierda = temporal->derecha = NULL;> >temp->datos = datos;> >temp->frecuencia = frecuencia;> > >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->tamaño = 0;> > >minHeap->capacidad = capacidad;> > >minHeap->matriz = (>struct> MinHeapNode**)>malloc>(> >minHeap->capacidad *>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->matriz[izquierda]->frecuencia> >array[smallest]->frecuencia)> >smallest = left;> > >if> (right size> >&& minHeap->matriz[derecha]->frecuencia> >array[smallest]->frecuencia)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->matriz[más pequeña],> >&minHeap->matriz[idx]);> >minHeapify(minHeap, smallest);> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->tamaño == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->matriz[0];> >minHeap->matriz[0] = minHeap->array[minHeap->tamaño - 1];> > >--minHeap->tamaño;> >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->tamaño;> >int> i = minHeap->tamaño - 1;> > >while> (i> >&& minHeapNode->frecuencia> >array[(i - 1) / 2]->frecuencia) {> > >minHeap->matriz[i] = minHeap->matriz[(i - 1) / 2];> >i = (i - 1) / 2;> >}> > >minHeap->matriz[i] = minHeapNode;> }> > // A standard function to build min heap> void> buildMinHeap(>struct> MinHeap* minHeap)> > {> > >int> n = minHeap->tamaño - 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->izquierda) && !(raíz->derecha); } // Crea un montón mínimo de capacidad // igual al tamaño e inserta todos los caracteres de // datos[] en el montón mínimo. Inicialmente, el tamaño de // mínimo montón es igual a la capacidad 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 función principal que construye el árbol Huffman struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top // Paso 1: Crear un montón mínimo de capacidad // igual al tamaño; Inicialmente, hay // modos iguales al tamaño. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Iterar mientras el tamaño del montón no sea 1 while (!isSizeOne(minHeap)) { //. Paso 2: Extraiga los dos elementos // mínimos de frecuencia del montón mínimo left = extractMin(minHeap); frecuencias de dos nodos. // Haga que los dos nodos extraídos sean // hijos izquierdo y derecho de este nuevo nodo // Agregue este nodo al montón mínimo // '$' es un valor especial para los nodos internos, // no. usado top = newNode('$', izquierda->frecuencia + derecha->frecuencia); arriba->izquierda = izquierda; arriba->derecha = derecha; insertMinHeap(minHeap, arriba); } // Paso 4: El nodo restante es el // nodo raíz y el árbol está completo. devolver extraerMin(minHeap); } // Imprime códigos Huffman desde la raíz del árbol Huffman. // Utiliza arr[] para almacenar códigos void printCodes(struct MinHeapNode* root, int arr[], int top) { // Asigna 0 al borde izquierdo y repite if (root->left) { arr[top] = 0 ; printCodes(raíz->izquierda, arr, arriba + 1); } // Asigna 1 al borde derecho y repite if (root->right) { arr[top] = 1; printCodes(raíz->derecha, arr, arriba + 1); } // Si se trata de un nodo hoja, entonces // contiene uno de los // caracteres de entrada, imprima el carácter // y su código desde arr[] if (isLeaf(root)) { printf('%c: ', raíz->datos); printArr(arr, arriba); } } // La función principal que construye un // árbol Huffman e imprime códigos atravesando // el árbol Huffman construido void HuffmanCodes(char data[], int freq[], int size) { // Construye la estructura del árbol Huffman MinHeapNode* raíz = buildHuffmanTree(datos, frecuencia, tamaño); // Imprime códigos Huffman usando // el árbol Huffman creado arriba int arr[MAX_TREE_HT], top = 0; printCodes(raíz, arreglo, arriba); } // Código del controlador int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f ' }; int frecuencia[] = { 5, 9, 12, 13, 16, 45 }; int tamaño = tamaño de (arr) / tamaño de (arr [0]); HuffmanCodes(arr, frecuencia, tamaño); devolver 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->izquierda = temporal->derecha = NULL;> >temp->datos = datos;> >temp->frecuencia = frecuencia;> > >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->tamaño = 0;> > >minHeap->capacidad = capacidad;> > >minHeap->matriz = (>struct> MinHeapNode**)>malloc>(> >minHeap->capacidad *>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->matriz[izquierda]->frecuencia> >array[smallest]->frecuencia)> >smallest = left;> > >if> (right size> >&& minHeap->matriz[derecha]->frecuencia> >array[smallest]->frecuencia)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->matriz[más pequeña],> >&minHeap->matriz[idx]);> >minHeapify(minHeap, smallest);> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->tamaño == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->matriz[0];> >minHeap->matriz[0] = minHeap->array[minHeap->tamaño - 1];> > >--minHeap->tamaño;> >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->tamaño;> >int> i = minHeap->tamaño - 1;> > >while> (i> >&& minHeapNode->frecuencia> >array[(i - 1) / 2]->frecuencia) {> > >minHeap->matriz[i] = minHeap->matriz[(i - 1) / 2];> >i = (i - 1) / 2;> >}> > >minHeap->matriz[i] = minHeapNode;> }> > // A standard function to build min heap> void> buildMinHeap(>struct> MinHeap* minHeap)> > {> > >int> n = minHeap->tamaño - 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->izquierda) && !(raíz->derecha); } // Crea un montón mínimo de capacidad // igual al tamaño e inserta todos los caracteres de // datos[] en el montón mínimo. Inicialmente, el tamaño de // mínimo montón es igual a la capacidad 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 función principal que construye el árbol Huffman struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top // Paso 1: Crear un montón mínimo de capacidad // igual al tamaño; Inicialmente, hay // modos iguales al tamaño. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Iterar mientras el tamaño del montón no sea 1 while (!isSizeOne(minHeap)) { //. Paso 2: Extraiga los dos elementos // mínimos de frecuencia del montón mínimo left = extractMin(minHeap); frecuencias de dos nodos. // Haga que los dos nodos extraídos sean // hijos izquierdo y derecho de este nuevo nodo // Agregue este nodo al montón mínimo // '$' es un valor especial para los nodos internos, // no. usado top = newNode('$', izquierda->frecuencia + derecha->frecuencia); arriba->izquierda = izquierda; arriba->derecha = derecha; insertMinHeap(minHeap, arriba); } // Paso 4: El nodo restante es el // nodo raíz y el árbol está completo. devolver extraerMin(minHeap); } // Imprime códigos Huffman desde la raíz del árbol Huffman. // Utiliza arr[] para almacenar códigos void printCodes(struct MinHeapNode* root, int arr[], int top) { // Asigna 0 al borde izquierdo y repite if (root->left) { arr[top] = 0 ; printCodes(raíz->izquierda, arr, arriba + 1); } // Asigna 1 al borde derecho y repite if (root->right) { arr[top] = 1; printCodes(raíz->derecha, arr, arriba + 1); } // Si se trata de un nodo hoja, entonces // contiene uno de los // caracteres de entrada, imprima el carácter // y su código desde arr[] if (isLeaf(root)) { cout ': '; printArr(arr, arriba); } } // La función principal que construye un // árbol Huffman e imprime códigos atravesando // el árbol Huffman construido void HuffmanCodes(char data[], int freq[], int size) { // Construye la estructura del árbol Huffman MinHeapNode* raíz = buildHuffmanTree(datos, frecuencia, tamaño); // Imprime códigos Huffman usando // el árbol Huffman creado arriba int arr[MAX_TREE_HT], top = 0; printCodes(raíz, arreglo, arriba); } // Código del controlador int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f ' }; int frecuencia[] = { 5, 9, 12, 13, 16, 45 }; int tamaño = tamaño de (arr) / tamaño de (arr [0]); HuffmanCodes(arr, frecuencia, tamaño); devolver 0; }> |
>
>
C++
llamar a la función javascript desde html
// 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>->datos = datos;> >this>->frecuencia = frecuencia;> >}> };> > // For comparison of> // two heap nodes (needed in min heap)> struct> compare {> > >bool> operator()(MinHeapNode* l, MinHeapNode* r)> > >{> >return> (l->frecuencia> r->frecuencia);> >}> };> > // Prints huffman codes from> // the root of Huffman Tree.> void> printCodes(>struct> MinHeapNode* root, string str)> {> > >if> (!root)> >return>;> > >if> (root->datos !=>'$'>)> >cout ': ' << str << '
'; printCodes(root->izquierda, cadena + '0'); printCodes(raíz->derecha, str + '1'); } // La función principal que construye un árbol Huffman e // imprime códigos atravesando el árbol Huffman construido void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Crea un montón mínimo e inserta todos los caracteres de datos[] prioridad_queue compare> minHeap; for (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Iterar mientras el tamaño del montón no llegue a 1 while (minHeap.size() != 1 ) { // Extrae los dos elementos de frecuencia mínima // del montón mínimo left = minHeap.top(); minHeap.pop() right = minHeap.top(); con // frecuencia igual a la suma de las // frecuencias de los dos nodos. Haga que los // dos nodos extraídos sean hijos izquierdo y derecho // de este nuevo nodo. Agregue este nodo // al montón mínimo '$'. un valor especial // para nodos internos, no utilizado top = new MinHeapNode('$', left->freq + right->freq top->left = top->right = right; (arriba); } // Imprime códigos Huffman usando // el árbol Huffman creado arriba printCodes(minHeap.top(), '' } // Código de controlador int main() { char arr[] = { '); a', 'b', 'c', 'd', 'e', 'f' }; int frecuencia[] = { 5, 9, 12, 13, 16 , 45 }; int tamaño = tamaño de (arr) / tamaño de (arr[0]); devolver 0; } // Este código es una contribución de 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) { // extracto del primer minuto. HuffmanNode x = q.peek(); q.encuesta(); // segundo extracto mínimo. HuffmanNode y = q.peek(); q.encuesta(); // nuevo nodo f que es igual a HuffmanNode f = new HuffmanNode(); // a la suma de la frecuencia de los dos nodos // asignando valores al nodo f. f.datos = x.datos + y.datos; f.c = '-'; // primer nodo extraído como hijo izquierdo. f.izquierda = x; // segundo nodo extraído como hijo derecho. f.derecha = y; // marcando el nodo f como nodo raíz. raíz = f; // agrega este nodo a la cola de prioridad. q.add(f); } // imprime los códigos atravesando el árbol printCode(root, ''); } } // la clase de nodo es la estructura básica // de cada nodo presente en el árbol de Huffman. clase HuffmanNode { int datos; carácter c; HuffmanNode se fue; HuffmanNodo derecho; } // la clase de comparación ayuda a comparar el nodo // en función de uno de sus atributos. // Aquí seremos comparados // en base a los valores de datos de los nodos. clase MyComparator implementa Comparador { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // Este código es una contribución de 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}') # caracteres para los caracteres del árbol de Huffman = ['a', 'b', 'c', 'd', 'e', 'f'] # frecuencia de caracteres freq = [5, 9, 12, 13, 16, 45] # lista que contiene nodos no utilizados nodos = [] # conversión de caracteres y frecuencias # en nodos del árbol de Huffman para x en rango(len(chars)): heapq .heappush(nodes, node(freq[x], chars[x])) while len(nodes)> 1: # ordenar todos los nodos en orden ascendente # según su frecuencia left = heapq.heappop(nodes) right = heapq .heappop(nodos) # asigna valor direccional a estos nodos left.huff = 0 right.huff = 1 # combina los 2 nodos más pequeños para crear # un nuevo nodo como su padre newNode = node(left.freq+right.freq, left. símbolo+derecha.símbolo, izquierda, derecha) heapq.heappush(nodos, nuevoNodo) # ¡El árbol Huffman está listo! imprimirNodos(nodos[0])> |
>
clase vs objeto en java
>
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) { // extracto del primer minuto. sea x = q[0]; q.shift(); // segundo extracto mínimo. sea y = q[0]; q.shift(); // nuevo nodo f que es igual let f = new HuffmanNode(); // a la suma de la frecuencia de los dos nodos // asignando valores al nodo f. f.datos = x.datos + y.datos; f.c = '-'; // primer nodo extraído como hijo izquierdo. f.izquierda = x; // segundo nodo extraído como hijo derecho. f.derecha = y; // marcando el nodo f como nodo raíz. raíz = f; // agrega este nodo a la cola de prioridad. q.push(f); q.sort(function(a,b){return a.data-b.data;}); } // imprime los códigos atravesando el árbol printCode(root, ''); // Este código es una contribución de 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> |
>
>Producción
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>
Complejidad del tiempo: O(nlogn) donde n es el número de caracteres únicos. Si hay n nodos, extractMin() se llama 2*(n – 1) veces. extractMin() toma O(logn) tiempo ya que llama a minHeapify(). Entonces, la complejidad general es O (nlogn).
Si la matriz de entrada está ordenada, existe un algoritmo de tiempo lineal. Pronto discutiremos esto en nuestra próxima publicación.
Complejidad espacial: - O (N)
Aplicaciones de la codificación Huffman:
- Se utilizan para transmitir faxes y textos.
- Son utilizados por formatos de compresión convencionales como PKZIP, GZIP, etc.
- Los códecs multimedia como JPEG, PNG y MP3 utilizan la codificación Huffman (para ser más precisos, los códigos de prefijo).
Es útil en los casos en los que hay una serie de caracteres que aparecen con frecuencia.
Referencia:
http://en.wikipedia.org/wiki/Huffman_coding
Este artículo fue compilado por Aashish Barnwal y revisado por el equipo de techcodeview.com.