Los datos se pueden comprimir utilizando la técnica de codificación Huffman para reducir su tamaño sin perder ninguna información. Después de David Huffman, ¿quién lo creó al principio? Los datos que contienen caracteres repetidos con frecuencia normalmente se comprimen mediante codificación Huffman.
Un algoritmo codicioso muy conocido es la codificación Huffman. El tamaño del código asignado a un carácter depende de la frecuencia del carácter, por lo que se lo denomina algoritmo codicioso. El código variable de longitud corta se asigna al carácter con mayor frecuencia y viceversa para los caracteres con menor frecuencia. Emplea una codificación de longitud variable, lo que significa que le da a cada carácter en el flujo de datos proporcionado un código de longitud variable diferente.
Regla de prefijo
Básicamente, esta regla establece que el código asignado a un carácter no será el prefijo de otro código. Si se incumple esta regla, pueden aparecer diversas ambigüedades a la hora de decodificar el árbol de Huffman que se ha creado.
Veamos una ilustración de esta regla para comprenderla mejor: Para cada carácter, se proporciona un código, como por ejemplo:
a - 0 b - 1 c - 01
Suponiendo que el flujo de bits producido es 001, el código puede expresarse de la siguiente manera cuando se decodifica:
0 0 1 = aab 0 01 = ac
¿Qué es el proceso de codificación Huffman?
El Código Huffman se obtiene para cada carácter distinto principalmente en dos pasos:
- Primero cree un árbol Huffman utilizando solo los caracteres únicos en el flujo de datos proporcionado.
- En segundo lugar, debemos proceder a través del árbol Huffman construido, asignar códigos a los caracteres y luego usar esos códigos para decodificar el texto proporcionado.
Pasos a seguir en la codificación Huffman
Los pasos utilizados para construir el árbol de Huffman utilizando los personajes proporcionados.
Input: string str = 'abbcdbccdaabbeeebeab'
Si en este caso se emplea la codificación Huffman para la compresión de datos, se debe determinar la siguiente información para la decodificación:
- Para cada personaje, el Código Huffman.
- Longitud del mensaje codificado por Huffman (en bits), longitud promedio del código
- Utilizando las fórmulas que se tratan a continuación, se descubren las dos últimas.
¿Cómo se puede construir un árbol de Huffman a partir de caracteres de entrada?
Primero se debe determinar la frecuencia de cada carácter en la cadena proporcionada.
| Personaje | Frecuencia |
|---|---|
| a | 4 |
| b | 7 |
| C | 3 |
| d | 2 |
| Es | 4 |
- Ordena los caracteres por frecuencia, de forma ascendente. Estos se mantienen en una cola de prioridad Q/min-heap.
- Para cada carácter distinto y su frecuencia en el flujo de datos, cree un nodo hoja.
- Elimine los dos nodos con las dos frecuencias más bajas de los nodos y se creará la nueva raíz del árbol utilizando la suma de estas frecuencias.
- Haga que el primer nodo extraído sea su hijo izquierdo y el segundo nodo extraído su hijo derecho mientras extrae los nodos con la frecuencia más baja del montón mínimo.
- Al montón mínimo, agregue este nodo.
- Dado que el lado izquierdo de la raíz siempre debe contener la frecuencia mínima.
- Repita los pasos 3 y 4 hasta que solo quede un nodo en el montón o todos los caracteres estén representados por nodos en el árbol. El árbol estará terminado cuando solo quede el nodo raíz.
Ejemplos de codificación Huffman
Usemos una ilustración para explicar el algoritmo:
Algoritmo para la codificación de Huffman
Paso 1: Cree un montón mínimo en el que cada nodo represente la raíz de un árbol con un solo nodo y contenga 5 (la cantidad de caracteres únicos del flujo de datos proporcionado).
Paso 2: Obtenga dos nodos de frecuencia mínima del montón mínimo en el paso dos. Agregue un tercer nodo interno, frecuencia 2 + 3 = 5, que se crea uniendo los dos nodos extraídos.
- Ahora, hay 4 nodos en el montón mínimo, 3 de los cuales son las raíces de árboles con un solo elemento cada uno, y 1 de los cuales es la raíz de un árbol con dos elementos.
Paso 3: Obtenga los dos nodos de frecuencia mínima del montón de manera similar en el paso tres. Además, agregue un nuevo nodo interno formado uniendo los dos nodos extraídos; su frecuencia en el árbol debe ser 4 + 4 = 8.
- Ahora que el montón mínimo tiene tres nodos, un nodo sirve como raíz de árboles con un solo elemento y dos nodos del montón sirven como raíz de árboles con múltiples nodos.
Etapa 4: Obtenga los dos nodos de frecuencia mínima en el paso cuatro. Además, agregue un nuevo nodo interno formado uniendo los dos nodos extraídos; su frecuencia en el árbol debe ser 5 + 7 = 12.
- Al crear un árbol de Huffman, debemos asegurarnos de que el valor mínimo esté siempre en el lado izquierdo y que el segundo valor esté siempre en el lado derecho. Actualmente, la siguiente imagen muestra el árbol que se ha formado:
Paso 5: Obtenga los siguientes dos nodos de frecuencia mínima en el paso 5. Además, agregue un nuevo nodo interno formado uniendo los dos nodos extraídos; su frecuencia en el árbol debe ser 12 + 8 = 20.
Continúe hasta que todos los personajes distintos se hayan agregado al árbol. El árbol de Huffman creado para el elenco de personajes especificado se muestra en la imagen de arriba.
Ahora, para cada nodo que no sea hoja, asigne 0 al borde izquierdo y 1 al borde derecho para crear el código para cada letra.
Reglas a seguir para determinar los pesos de los bordes:
- Deberíamos darle a los bordes derechos un peso de 1 si a los bordes izquierdos les damos un peso de 0.
- Si a los bordes izquierdos se les asigna un peso 1, a los bordes derechos se les debe asignar un peso 0.
- Se podrá utilizar cualquiera de las dos convenciones antes mencionadas.
- Sin embargo, siga también el mismo protocolo al decodificar el árbol.
Tras la ponderación, el árbol modificado se muestra de la siguiente manera:
Comprender el código
- Debemos recorrer el árbol de Huffman hasta llegar al nodo hoja, donde está presente el elemento, para poder decodificar el código de Huffman para cada carácter del árbol de Huffman resultante.
- Los pesos entre los nodos deben registrarse durante el recorrido y asignarse a los elementos ubicados en el nodo de hoja específico.
- El siguiente ejemplo ayudará a ilustrar mejor lo que queremos decir:
- Para obtener el código de cada carácter en la imagen de arriba, debemos recorrer todo el árbol (hasta cubrir todos los nodos de las hojas).
- Como resultado, el árbol creado se utiliza para decodificar los códigos de cada nodo. A continuación se muestra una lista de los códigos para cada personaje:
| Personaje | Frecuencia/recuento | Código |
|---|---|---|
| a | 4 | 01 |
| b | 7 | 11 |
| C | 3 | 101 |
| d | 2 | 100 |
| Es | 4 | 00 |
A continuación se muestra la implementación en programación C:
// C program for Huffman Coding #include #include // This constant can be avoided by explicitly // calculating height of Huffman Tree #define MAX_TREE_HT 100 // A Huffman tree node struct MinHeapNode { // One of the input characters char data; // Frequency of the character unsigned freq; // Left and right child of this node struct MinHeapNode *left, *right; }; // A Min Heap: Collection of // min-heap (or Huffman tree) nodes struct MinHeap { // Current size of min heap unsigned size; // capacity of min heap unsigned capacity; // Array of minheap node pointers struct MinHeapNode** array; }; // A utility function allocate a new // min heap node with given character // and frequency of the character struct MinHeapNode* newNode(char data, unsigned freq) { struct MinHeapNode* temp = (struct MinHeapNode*)malloc( sizeof(struct MinHeapNode)); temp->left = temp->right = NULL; temp->data = data; temp->freq = freq; return temp; } // A utility function to create // a min heap of given capacity struct MinHeap* createMinHeap(unsigned capacity) { struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap)); // current size is 0 minHeap->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHeapNode**)malloc( minHeap->capacity * sizeof(struct MinHeapNode*)); return minHeap; } // A utility function to // swap two min heap nodes void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) { struct MinHeapNode* t = *a; *a = *b; *b = t; } // The standard minHeapify function. void minHeapify(struct MinHeap* minHeap, int idx) { int smallest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2; if (left size && minHeap->array[left]->freq array[smallest]->freq) smallest = left; if (right size && minHeap->array[right]->freq array[smallest]->freq) smallest = right; if (smallest != idx) { swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); minHeapify(minHeap, smallest); } } // A utility function to check // if size of heap is 1 or not int isSizeOne(struct MinHeap* minHeap) { return (minHeap->size == 1); } // A standard function to extract // minimum value node from heap struct MinHeapNode* extractMin(struct MinHeap* minHeap) { struct MinHeapNode* temp = minHeap->array[0]; minHeap->array[0] = minHeap->array[minHeap->size - 1]; --minHeap->size; minHeapify(minHeap, 0); return temp; } // A utility function to insert // a new node to Min Heap void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) { ++minHeap->size; int i = minHeap->size - 1; while (i && minHeapNode->freq array[(i - 1) / 2]->freq) { minHeap->array[i] = minHeap->array[(i - 1) / 2]; i = (i - 1) / 2; } minHeap->array[i] = minHeapNode; } // A standard function to build min heap void buildMinHeap(struct MinHeap* minHeap) { int n = minHeap->size - 1; int i; for (i = (n - 1) / 2; i >= 0; --i) minHeapify(minHeap, i); } // A utility function to print an array of size n void printArr(int arr[], int n) { int i; for (i = 0; i left) && !(root->right); } // Creates a min heap of capacity // equal to size and inserts all character of // data[] in min heap. Initially size of // min heap is equal to capacity struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // The main function that builds Huffman tree struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Step 1: Create a min heap of capacity // equal to size. Initially, there are // modes equal to size. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Iterate while size of heap doesn't become 1 while (!isSizeOne(minHeap)) { // Step 2: Extract the two minimum // freq items from min heap left = extractMin(minHeap); right = extractMin(minHeap); // Step 3: Create a new internal // node with frequency equal to the // sum of the two nodes frequencies. // Make the two extracted node as // left and right children of this new node. // Add this node to the min heap // '$' is a special value for internal nodes, not // used top = newNode('$', left->freq + right->freq); top->left = left; top->right = right; insertMinHeap(minHeap, top); } // Step 4: The remaining node is the // root node and the tree is complete. return extractMin(minHeap); } // Prints huffman codes from the root of Huffman Tree. // It uses arr[] to store codes void printCodes(struct MinHeapNode* root, int arr[], int top) { // Assign 0 to left edge and recur if (root->left) { arr[top] = 0; printCodes(root->left, arr, top + 1); } // Assign 1 to right edge and recur if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // If this is a leaf node, then // it contains one of the input // characters, print the character // and its code from arr[] if (isLeaf(root)) { printf('%c: ', root->data); printArr(arr, top); } } // The main function that builds a // Huffman Tree and print codes by traversing // the built Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree(data, freq, size); // Print Huffman codes using // the Huffman tree built above int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Driver code int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16, 45 }; int size = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, freq, size); return 0; } Producción
archivo json
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 …………… Process executed in 1.11 seconds Press any key to continue.
Implementación Java del código anterior:
import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; class Huffman { // recursive function to print the // huffman-code through the tree traversal. // Here s is the huffman - code generated. public static void printCode(HuffmanNode root, String s) { // base case; if the left and right are null // then its a leaf node and we print // the code s generated by traversing the tree. if (root.left == null && root.right == null && Character.isLetter(root.c)) { // c is the character in the node System.out.println(root.c + ':' + s); return; } // if we go to left then add '0' to the code. // if we go to the right add'1' to the code. // recursive calls for left and // right sub-tree of the generated tree. printCode(root.left, s + '0'); printCode(root.right, s + '1'); } // main function public static void main(String[] args) { Scanner s = new Scanner(System.in); // number of characters. int n = 6; char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' }; int[] charfreq = { 5, 9, 12, 13, 16, 45 }; // creating a priority queue q. // makes a min-priority queue(min-heap). PriorityQueue q = new PriorityQueue( n, new MyComparator()); for (int i = 0; i <n; i++) { creating a huffman node object and add it to the priority queue. huffmannode hn="new" huffmannode(); hn.c="charArray[i];" hn.data="charfreq[i];" hn.left="null;" hn.right="null;" functions adds q.add(hn); } create root here we will extract two minimum value from heap each time until its size reduces 1, all nodes are extracted. while (q.size()> 1) { // first min extract. HuffmanNode x = q.peek(); q.poll(); // second min extract. HuffmanNode y = q.peek(); q.poll(); // new node f which is equal HuffmanNode f = new HuffmanNode(); // to the sum of the frequency of the two nodes // assigning values to the f node. f.data = x.data + y.data; f.c = '-'; // first extracted node as left child. f.left = x; // second extracted node as the right child. f.right = y; // marking the f node as the root node. root = f; // add this node to the priority-queue. q.add(f); } // print the codes by traversing the tree printCode(root, ''); } } // node class is the basic structure // of each node present in the Huffman - tree. class HuffmanNode { int data; char c; HuffmanNode left; HuffmanNode right; } // comparator class helps to compare the node // on the basis of one of its attribute. // Here we will be compared // on the basis of data values of the nodes. class MyComparator implements Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } </n;> Producción
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 ………………. Process executed in 1.11 seconds Press any key to continue.
Explicación:
Al atravesarlo, se crea y decodifica el árbol Huffman. Los valores recopilados durante el recorrido se aplicarán al carácter ubicado en el nodo hoja. Cada carácter único en el flujo de datos proporcionado puede identificarse utilizando el Código Huffman de esta manera. O (nlogn), donde n es el número total de caracteres, es la complejidad del tiempo. ExtractMin() se llama 2*(n - 1) veces si hay n nodos. Dado que extractMin() llama a minHeapify(), su tiempo de ejecución es O (logn). Por tanto, la complejidad total es O (nlogn). Existe un algoritmo de tiempo lineal si la matriz de entrada está ordenada. Esto se cubrirá con más detalle en nuestro próximo artículo.
Problemas con la codificación Huffman
Hablemos de los inconvenientes de la codificación Huffman en esta parte y de por qué no siempre es la mejor opción:
- Si no todas las probabilidades o frecuencias de los personajes son potencias negativas de 2, no se considera ideal.
- Aunque uno puede acercarse al ideal agrupando símbolos y expandiendo el alfabeto, el método de bloqueo requiere manejar un alfabeto más grande. Por lo tanto, es posible que la codificación de Huffman no siempre sea muy eficaz.
- Aunque existen muchas formas efectivas de contar la frecuencia de cada símbolo o carácter, reconstruir el árbol completo para cada uno puede llevar mucho tiempo. Cuando el alfabeto es grande y las distribuciones de probabilidad cambian rápidamente con cada símbolo, este suele ser el caso.
Algoritmo de construcción del código Greedy Huffman
- Huffman desarrolló una técnica codiciosa que genera un código Huffman, un código de prefijo ideal, para cada carácter distinto en el flujo de datos de entrada.
- El enfoque utiliza la menor cantidad de nodos cada vez para crear el árbol de Huffman de abajo hacia arriba.
- Debido a que cada carácter recibe una longitud de código basada en la frecuencia con la que aparece en el flujo de datos determinado, este método se conoce como enfoque codicioso. Es un elemento que ocurre comúnmente en los datos si el tamaño del código recuperado es menor.
El uso de la codificación Huffman
- Aquí, hablaremos sobre algunos usos prácticos de la codificación Huffman:
- Los formatos de compresión convencionales como PKZIP, GZIP, etc. suelen emplear codificación Huffman.
- La codificación Huffman se utiliza para la transferencia de datos por fax y texto porque minimiza el tamaño del archivo y aumenta la velocidad de transmisión.
- La codificación Huffman (particularmente los códigos de prefijo) es utilizada por varios formatos de almacenamiento multimedia, incluidos JPEG, PNG y MP3, para comprimir los archivos.
- La codificación Huffman se utiliza principalmente para la compresión de imágenes.
- Cuando es necesario enviar una cadena de caracteres que se repiten con frecuencia, puede resultar más útil.
Conclusión
- En general, la codificación Huffman es útil para comprimir datos que contienen caracteres que aparecen con frecuencia.
- Podemos ver que el carácter que ocurre con más frecuencia tiene el código más corto, mientras que el que ocurre con menos frecuencia tiene el código más grande.
- La técnica de compresión del Código Huffman se utiliza para crear codificación de longitud variable, que utiliza una cantidad variada de bits para cada letra o símbolo. Este método es superior a la codificación de longitud fija ya que utiliza menos memoria y transmite datos más rápidamente.
- Lea este artículo para tener un mejor conocimiento del algoritmo codicioso.