Algoritmo de Huffman

Hi!, Hola! and Ciao! Hoy les traemos un nuevo vídeo acerca de un método fácil para la compresión y la encriptación de textos (cadena de caracteres) con la utilización de arboles:

Algoritmo de Huffman.

ALGORITMO DE HUFFMAN

Vamos a declarar nuestra cabecera.

Declaramos dos estructuras, una será para el nodo de tipo Árbol el cual contendrá:

dato - valor

fr - frecuencia con que se repite una letra en la frase

izq, der - Apuntadores al nodo izquierdo y derecho respectivamente.

Estructura Nodo, para hacer una lista doblemente enlazada:

raíz - apuntador a un nodo tipo árbol

siguiente,anterior - Apuntadores al nodo anterior y siguiente respectivamente

Cabecera

• Función insertarCola

Estructura de Nodo y Árbol

Declaramos una función de tipo void y le pasamos como parámetros el dato a insertar,solo le llamaremos dato.

Primero vamos a verificar que el dato no esté ya en la lista, en caso de ya estar se sale de una función.

En caso de no estar en lista, vamos a declarar un apuntador tipo Árbol, para crear un espacio en memoria y le pasamos el dato y un 1, ya que inicialmente solo va a ver 1 solo de ese tipo de letra. Creamos un nodo tipo Nodo y le pasamos el árbol creado.

Finalmente insertamos al final de la lista el nodo creado.

Si la letra no existe en la lista se agrega al final, en caso contrario se le suma uno

en su parte de frecuencia

• Función ordenar

Para ordenar la lista utilizamos el siguiente método de ordenación:

Señalamos el inicio como piv y declaramos otro auxiliar al siguiente nodo

Apuntadores en su posición inicialmente

2. Recorremos el auxiliar hasta encontrar una frecuencia menor al pivote y lo sacamos de la lista y lo unimos en la parte izquierda del pivote (tengan o no tenga otro nodo a la izquierda el pivote).

3. Ahora el pivote va ser igual a aux y aux va ser dos nodos más adelante

4. Seguimos los anteriores pasos hasta que aux sea igual a NULL

5. Cuando el aux llegue a NULL vamos a hacer que el pivote sea igual a su nodo siguiente y el auxiliar sea igual al nodo siguiente de pivote, y así hasta que pivote sea NULL.

Resultado de la función Ordenar

• Función desencolar

Vamos de declarar una función de tipo Árbol apuntador.

Declaramos una apuntador de tipo Nodo, llamado aux.

Ponemos la excepción que si la lista está vacía, si es verdadero nos va a regresar la función un nodo de Árbol NULL.

En caso que no esté vacía, vamos a aislar de la lista el nodo del inicio de la lista.

Después de aislar el nodo de la lista,declaramos una variable de tipo Árbol apuntador que extraerá el árbol del nodo, para así poner liberar aux y retornar el árbol extraído.

Función insertarOrden

Vamos a declarar una función de tipo void, el cual como parámetro de entrada tendrá un el árbol nuevo a insertar.

Declaramos dos apuntadores de tipo Nodo:

nuevo - es el nuevo nodo a insertar en la lista, en un principio creamos espacio de memoria para el nodo con la función y le pasamos como parámetro el nuevo árbol.

aux - nos ayudará para recorrer el árbol desde el inicio.

Primero con aux vamos recorriendo la lista hasta encontrar un nodo que tenga como frecuencia un número mayor o igual a la frecuencia del nuevo nodo, o hasta que sea NULL. Cuando lo encuentra lo inserta en la parte izquierda del nodo aux.

En caso de que el nuevo nodo sea el primero de la lista le asigna el inicio y final o si el nuevo nodo tiene la frecuencia más alta de la lista lo inserta al final.

• Función algoritmoHuffman

Declaramos una función de tipo void sin parámetros.

Lista inicial

Declaramos una variable de tipo entero que nos ayudará a hacer la suma de las frecuencias de los árboles a extraer.

Ya que la función va a ser recursiva ponemos como base que la lista no esté vacía, en caso de ser falso esto termina la función.

Declaramos dos punteros de tipo Arbol y los igualamos a la función desencolar para sacar los dos nodos del inicio.

desencolar

Teniendo estos dos últimos vamos a sumar sus frecuencias y asignarlas a la variable que declaramos inicialmente.

Creamos con otra variables Arbol apuntador otro nodo y le pasamos como parámetro cuál letra o símbolo (incluso un dato NULL) y la variable de la suma de las frecuencias.

Asignamos en su parte izquierda y derecha del nuevo árbol creado los dos árboles desencolados en el orden que salieron.

Finalmente metemos a la lista en el lugar que le corresponde con la función insertarOrden, y llamamos de nuevo a la función algoritmoHuffman,se repite esto hasta que quede un solo nodo en la lista.

• Función Inorden

Vamos a crear nuestro directorio de letras, para ello necesitamos recorrer el árbol, teniendo en cuenta que cuando nos movemos a la rama izquierda es un 0 y a la derecha un 1. Así para conseguir exactamente donde esta nuestras letras.

Árbol y Directorio

Para ello vamos a utilizar la función Inorden, con algunas modificaciones:

Como parámetros además del nodo Arbol donde vamos a empezar a recorrer, le agregamos un dato tipo archivo y un dato entero que es la dirección de los nodos.

NOTA: Aquí se puso un archivo ya que el directorio lo vamos a guardar en un archivo de texto,así que es opción.

Para agregar un 0 cuando nos vayamos a la izquierda, tenemos que multiplicar nuestro directorio por 10,cuando llamemos a la función Inorden.

Para imprimir y guardar la letra y la dirección de cada letra, tenemos que verificar que no sea un nodo vacío (o en mi caso el número 46).

Para agregar un 1 cuando nos vayamos a la derecha, tenemos que multiplicar nuestro directorio por 10 y sumarle 1,cuando llamemos a la función Inorden.

Función comprimir

Declaramos una función de tipo void y que toma como parámetro una cadena de caracteres, llamada binario (Son las letras de la frase representadas en binario con respecto al directorio sacado anteriormente).

Vamos a declarar las siguientes variables:

ASCII - (* Opcional), vamos a escribir nuestro mensaje encriptado en el archivo donde está nuestro directorio.

len - Con ayuda de la función strlen (string.h) necesitamos saber cuando digitos tiene nuestra cadena

bytes - Contiene el números de bytes que podemos hacer con nuestra cadena

sb - Se utiliza si sobran bits que no pueden hacer un byte

num - Se utilizará para guardar el número en decimal de cada byte

aux - Se presentará como un contador

i , j - Variables de nuestro for anidado

byte[] - Guardaremos una cantidad de 8 bits

sll [] - Se utilizará para los bits sobrantes que no pueden hacer un byte

Por medio de for anidados vamos extrayendo 8 bits de muestra cadena, para que después convertirlos en decimales (ya que la cadena es de caracteres) con la función atoi y pasarla a nuestra función convertir a decimal e imprimir el número que nos de en carácter.