Tarea 2
Algoritmo de Huffman
La finalidad de este algoritmo es encontrar una manera de comprimir datos, la manera en que lo hace es dandole a cada símbolo un código, el código que se le da a cada símbolo depende de la frecuencia con que el símbolo aparece en los datos, es fácil de comprender, al símbolo que aparezca más veces en los datos tendrá un código de representación más corto que un símbolo que aparesca menos veces.
Para hacerlo se debe primero hacer una tabla que relacione al símbolo con su frecuencia(esto no corresponde al algoritmo de Huffman), para así empezar a hacer el árbol binario usando el algoritmo de Huffman.
Voy a hacer un ejemplo con la frase: "clase de algoritmos computacionales"
| Letra | Frecuencia |
|---|---|
| a | 4 |
| c | 3 |
| d | 1 |
| e | 3 |
| g | 1 |
| i | 2 |
| l | 3 |
| m | 2 |
| n | 1 |
| o | 4 |
| p | 1 |
| r | 1 |
| s | 3 |
| t | 2 |
| u | 1 |
| " " | 3 |
Ahora teniendo mi frencuencia de palabras en la frase puedo empezar a dibujar mi árbol binario, el método para hacerlo es:
- Hacer un arbol para cada símbolo escribiendo el símbolo con su frecuencia
- Juntar los arboles con menor frecuencia para formar un nuevo árbol(binario), las etiquetas de los nodos serán la suma de las frecuencias de los hijos
- Se repite el proceso hasta tener un solo árbol binario
Y este es el árbol que diseñé para la frase "clase de algoritmos computacionales"
Y ahora si estamos listos para codificar los símbolos, este paso del algoritmo es muy sencillo se escriben números en cada rama de el árbol, 0 para el lado izquierdo y 1 para el lado derecho.
Y ahora se ve de esta manera:
Entonces ahora poder encontrar el código de cada símbolo debemos empezar desde la raiz hasta el símbolo, por ejemplo:
para la letra "a" el código 010,
para la letra m el código 0011,
y para la letra "u" el código 01100,
podemos ver que entre menos es la frecuencia de la letra el tamaño de la cadena de código que representa a la letra se vuelve mas larga. Esto es el funcionamiento de el algoritmo.
Definición formal
Entradas
Tenemos el conjunto A que representa a los símbolos que se codificarán A={a1, a2,...an}
También el conjunto F que representa la frecuencia de cada símbolo F={f1, f2....fn},
Salidas
C representara el conjunto de códigos que representan a cada símbolo entonces tenemos C(A, F)={c1, c2, ... cn}. Esto quiere decir que por ejemplo c1 es la cadena de código que me representa a a1, a1 es el símbolo de entrada.
Complejidad
Por ser un algoritmo iterativo tiene su complejidad O(nlogn).
Ya que se tiene un bucle interno con complejidad logn y luego se repite n veces, dónde n es el conjunto de símbolos.
Características del algoritmo
La manera en que se ecuentra la tabla de frecuencia de palabras no es asunto de este algoritmo.
El caso óptimo es cuando se tiene que la probabilidad de que salga un número es una potencia negativa de dos.
El peor caso es cuando se tiene 2^-1.
Esto tiene sentido porque cuando se tiene una letra que sale el 50%, se supone que entre todos las demas símbolos habran probabilidades demasiado bajas, entonces se tendrán para ellos cadenas muy largas, que es lo contrario a lo que se busca.
Otros algoritmos
Existe otro algoritmo "codificación aritmética" que tiene ventaja sobre la codificación de Huffman pero su ventaja no es tan grande como para cambiar la simplicidad de Huffman y el no pago de patentes por la complejidad de codificación aritmética además de que este método no es tan libre de usarse ya que esta patentado por IBM.
Aplicaciones
Este algoritmo sigue siendo muy utilizado debido a su simplicidad, velocidad y no problemas de patentes.
Ejemplos de su uso en compresión multimedia de jpeg y mp3.
Referencias
No hay comentarios:
Publicar un comentario