TechCodeview

El algoritmo de codificación de Huffman fue propuesto por David A. Huffman en 1950. Es un compresión de datos sin pérdidas mecanismo. También se le conoce como codificación de compresión de datos. Se utiliza ampliamente en la compresión de imágenes (JPEG o JPG). En esta sección, discutiremos la Codificación Huffman y descodificación, y también implementar su algoritmo en un programa Java.

Sabemos que cada carácter es una secuencia de 0 y 1 y se almacena en 8 bits. El mecanismo se llama codificación de longitud fija porque cada carácter utiliza la misma cantidad de almacenamiento de bits fijos.

upcasting

Aquí surge una pregunta, ¿Es posible reducir la cantidad de espacio necesario para almacenar un personaje?

Sí, es posible usando codificación de longitud variable. En este mecanismo, explotamos algunos personajes que ocurren con más frecuencia en comparación con otros personajes. En esta técnica de codificación, podemos representar el mismo fragmento de texto o cadena reduciendo el número de bits.

Codificación Huffman

La codificación Huffman implementa los siguientes pasos.

• Asigna un código de longitud variable a todos los caracteres dados.
• La longitud del código de un carácter depende de la frecuencia con la que aparece en el texto o cadena dada.
• Un carácter obtiene el código más pequeño si ocurre con frecuencia.
• Un personaje obtiene el código más grande si ocurre menos.

La codificación de Huffman sigue un regla de prefijo que evita la ambigüedad durante la decodificación. La regla también garantiza que el código asignado al carácter no se trate como un prefijo del código asignado a ningún otro carácter.

Existen los siguientes dos pasos principales involucrados en la codificación Huffman:

• Primero, construye un árbol de huffman de la cadena de entrada dada, caracteres o texto.
• Asigne un código Huffman a cada personaje atravesando el árbol.

Resumamos los dos pasos anteriores.

Árbol de Huffman

Paso 1: Para cada carácter del nodo, cree un nodo hoja. El nodo hoja de un carácter contiene la frecuencia de ese carácter.

Paso 2: Coloque todos los nodos en orden según su frecuencia.

Paso 3: Puede existir una condición en la que dos nodos tengan la misma frecuencia. En tal caso, haga lo siguiente:

películas

1. Cree un nuevo nodo interno.
2. La frecuencia del nodo será la suma de la frecuencia de aquellos dos nodos que tengan la misma frecuencia.
3. Marque el primer nodo como hijo izquierdo y otro nodo como hijo derecho del nodo interno recién creado.

Etapa 4: Repita los pasos 2 y 3 hasta que todos los nodos formen un solo árbol. Por tanto, obtenemos un árbol de Huffman.

Ejemplo de codificación de Huffman

Supongamos que tenemos que codificar una cadena. abracadabra. Determina lo siguiente:

1. Código Huffman para todos los personajes.
2. Longitud promedio del código para la cadena dada
3. Longitud de la cadena codificada

(i) Código Huffman para todos los personajes

Para determinar el código de cada carácter, primero construimos un Árbol de Huffman.

Paso 1: Haz parejas de personajes y sus frecuencias.

(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)

Paso 2: Ordenando pares con respecto a la frecuencia, obtenemos:

(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)

Paso 3: Elija los dos primeros caracteres y únalos bajo un nodo principal.

Observamos que un nodo padre no tiene frecuencia, por lo que debemos asignarle una frecuencia. La frecuencia del nodo principal será la suma de sus nodos secundarios (izquierdo y derecho), es decir, 1+1= 2.

código c abs

Etapa 4: Repita los pasos 2 y 3 hasta que obtengamos un solo árbol.

Observamos que los pares ya están ordenados (por el paso 2). Nuevamente, elige los dos primeros pares y únelos.

Observamos que un nodo padre no tiene frecuencia, por lo que debemos asignarle una frecuencia. La frecuencia del nodo principal será la suma de sus nodos secundarios (izquierdo y derecho), es decir, 2+2= 4.

Nuevamente, verificamos si los pares están ordenados o no. En este paso, necesitamos ordenar los pares.

Según el paso 3, elige los dos primeros pares y únelos, obtenemos:

Observamos que un nodo padre no tiene frecuencia, por lo que debemos asignarle una frecuencia. La frecuencia del nodo principal será la suma de sus nodos secundarios (izquierdo y derecho), es decir, 2+4= 6.

Nuevamente, verificamos si los pares están ordenados o no. En este paso, necesitamos ordenar los pares. Después de ordenar el árbol se ve así:

Según el paso 3, elige los dos primeros pares y únelos, obtenemos:

Observamos que un nodo padre no tiene frecuencia, por lo que debemos asignarle una frecuencia. La frecuencia del nodo principal será la suma de sus nodos secundarios (izquierdo y derecho), es decir, 5+6= 11.

Por tanto, obtenemos un solo árbol.

Por último, encontraremos el código para cada carácter con la ayuda del árbol de arriba. Asigne un peso a cada borde. Tenga en cuenta que cada ponderado por el borde izquierdo es 0 y el ponderado por el borde derecho es 1.

Observamos que los caracteres de entrada solo se presentan en los nodos de salida y los nodos internos tienen valores nulos. Para encontrar el código de Huffman para cada carácter, recorra el árbol de Huffman desde el nodo raíz hasta el nodo hoja de ese carácter en particular para el cual queremos encontrar el código. La tabla describe el código y la longitud del código para cada carácter.

Observamos que el carácter más frecuente obtiene la longitud de código más corta y el carácter menos frecuente obtiene la longitud de código más grande.

convirtiendo int a cadena

Ahora podemos codificar la cadena. (abracadabra) que hemos tomado arriba.

 0 111 10 0 1100 0 1101 0 111 10 0 

(ii) Longitud promedio del código para la cadena

La longitud promedio del código del árbol de Huffman se puede determinar utilizando la fórmula que se proporciona a continuación:

 Average Code Length = ∑ ( frequency × code length ) / ∑ ( frequency ) 

= { (5 x 1) + (2 x 3) + (1 x 4) + (1 x 4) + (2 x 2) } / (5+2+1+1+2)

= 2.09090909

(iii) Longitud de la cadena codificada

La longitud del mensaje codificado se puede determinar mediante la siguiente fórmula:

 length= Total number of characters in the text x Average code length per character 

= 11 x 2,09090909

= 23 bits

Algoritmo de codificación de Huffman

 Huffman (C) n=|C| Q=C for i=1 to n-1 do z=allocate_Node() x=left[z]=Extract_Min(Q) y=right[z]=Extract_Min(Q) f[z]=f[x]+f[y] Insert(Q,z) return Extract_Min(Q) 

El algoritmo de Huffman es un algoritmo codicioso. Ya que en cada etapa el algoritmo busca las mejores opciones disponibles.

La complejidad temporal de la codificación de Huffman es O(nlogn). Donde n es el número de caracteres del texto dado.

Decodificación de Huffman

La decodificación de Huffman es una técnica que convierte los datos codificados en datos iniciales. Como hemos visto en la codificación, el árbol de Huffman está creado para una cadena de entrada y los caracteres se decodifican según su posición en el árbol. El proceso de decodificación es el siguiente:

marquesina html

• Comience a atravesar el árbol desde el raíz nodo y busque el personaje.
• Si nos movemos hacia la izquierda en el árbol binario, sumamos 0 al código.
• Si nos movemos hacia la derecha en el árbol binario, agregamos 1 al código.

El nodo secundario contiene el carácter de entrada. Se le asigna el código formado por 0 y 1 posteriores. La complejidad temporal de decodificar una cadena es En), donde n es la longitud de la cuerda.

Programa Java de codificación y decodificación de Huffman

En el siguiente programa, utilizamos estructuras de datos como colas, pilas y árboles de prioridad para diseñar una lógica de compresión y descompresión. Basaremos nuestras utilidades en la técnica algorítmica ampliamente utilizada de codificación Huffman.

HuffmanCode.java

 import java.util.Comparator; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; //defining a class that creates nodes of the tree class Node { //storing character in ch variable of type character Character ch; //storing frequency in freq variable of type int Integer freq; //initially both child (left and right) are null Node left = null; Node right = null; //creating a constructor of the Node class Node(Character ch, Integer freq) { this.ch = ch; this.freq = freq; } //creating a constructor of the Node class public Node(Character ch, Integer freq, Node left, Node right) { this.ch = ch; this.freq = freq; this.left = left; this.right = right; } } //main class public class HuffmanCode { //function to build Huffman tree public static void createHuffmanTree(String text) { //base case: if user does not provides string if (text == null || text.length() == 0) { return; } //count the frequency of appearance of each character and store it in a map //creating an instance of the Map Map freq = new HashMap(); //loop iterates over the string and converts the text into character array for (char c: text.toCharArray()) { //storing character and their frequency into Map by invoking the put() method freq.put(c, freq.getOrDefault(c, 0) + 1); } //create a priority queue that stores current nodes of the Huffman tree. //here a point to note that the highest priority means the lowest frequency PriorityQueue pq = new PriorityQueue(Comparator.comparingInt(l -&gt; l.freq)); //loop iterate over the Map and returns a Set view of the mappings contained in this Map for (var entry: freq.entrySet()) { //creates a leaf node and add it to the queue pq.add(new Node(entry.getKey(), entry.getValue())); } //while loop runs until there is more than one node in the queue while (pq.size() != 1) { //removing the nodes having the highest priority (the lowest frequency) from the queue Node left = pq.poll(); Node right = pq.poll(); //create a new internal node with these two nodes as children and with a frequency equal to the sum of both nodes&apos; frequencies. Add the new node to the priority queue. //sum up the frequency of the nodes (left and right) that we have deleted int sum = left.freq + right.freq; //adding a new internal node (deleted nodes i.e. right and left) to the queue with a frequency that is equal to the sum of both nodes pq.add(new Node(null, sum, left, right)); } //root stores pointer to the root of Huffman Tree Node root = pq.peek(); //trace over the Huffman tree and store the Huffman codes in a map Map huffmanCode = new HashMap(); encodeData(root, &apos;&apos;, huffmanCode); //print the Huffman codes for the characters System.out.println(&apos;Huffman Codes of the characters are: &apos; + huffmanCode); //prints the initial data System.out.println(&apos;The initial string is: &apos; + text); //creating an instance of the StringBuilder class StringBuilder sb = new StringBuilder(); //loop iterate over the character array for (char c: text.toCharArray()) { //prints encoded string by getting characters sb.append(huffmanCode.get(c)); } System.out.println(&apos;The encoded string is: &apos; + sb); System.out.print(&apos;The decoded string is: &apos;); if (isLeaf(root)) { //special case: For input like a, aa, aaa, etc. while (root.freq-- &gt; 0) { System.out.print(root.ch); } } else { //traverse over the Huffman tree again and this time, decode the encoded string int index = -1; while (index <sb.length() - 1) { index="decodeData(root," index, sb); } traverse the huffman tree and store codes in a map function that encodes data public static void encodedata(node root, string str, huffmancode) if (root="=" null) return; checks node is leaf or not (isleaf(root)) huffmancode.put(root.ch, str.length()> 0 ? str : &apos;1&apos;); } encodeData(root.left, str + &apos;0&apos;, huffmanCode); encodeData(root.right, str + &apos;1&apos;, huffmanCode); } //traverse the Huffman Tree and decode the encoded string function that decodes the encoded data public static int decodeData(Node root, int index, StringBuilder sb) { //checks if the root node is null or not if (root == null) { return index; } //checks if the node is a leaf node or not if (isLeaf(root)) { System.out.print(root.ch); return index; } index++; root = (sb.charAt(index) == &apos;0&apos;) ? root.left : root.right; index = decodeData(root, index, sb); return index; } //function to check if the Huffman Tree contains a single node public static boolean isLeaf(Node root) { //returns true if both conditions return ture return root.left == null &amp;&amp; root.right == null; } //driver code public static void main(String args[]) { String text = &apos;javatpoint&apos;; //function calling createHuffmanTree(text); } } </sb.length()>

Producción:

 Huffman Codes of the characters are: {p=000, a=110, t=111, v=001, i=010, j=011, n=100, o=101} The initial string is: javatpoint The encoded string is: 011110001110111000101010100111 The decoded string is: javatpoint