CÓDIGOS DE HUFFMAN
Códigos de Huffman
• Los códigos de Huffman, que representan caracteres por
cadenas de bits de longitud variable, proporcionan
alternativas al ASCII y otros códigos de longitud fija.
• La idea es usar cadenas de bits cortas para representar los
caracteres que se usan con más frecuencia y cadenas de bits
más largas para los caracteres de uso menos frecuente.
• Huffman desarrollo un algoritmo para construir un código
Huffman a partir de la tabla que da la frecuencia de ocurrencia
de los caracteres que se van a representar para que el código
construido represente las cadenas de caracteres en el mínimo
espacio, siempre que las cadenas representadas tengan
frecuencias de caracteres idénticas a las frecuencias de la
tabla.
•Un código Huffman se define con
gran facilidad mediante un árbol
con raíz. Para decodificar una
cadena de bits, comenzamos en la
raíz y seguimos hacia abajo por el
árbol hasta que se encuentra el
carácter. El bit, 0 o 1, dice si
debemos ir a la derecha o a la
izquierda.
•0 = derecha
1 = izquierda
Construcción de un código de Huffman optimo
• Se tiene la siguiente tabla de frecuencia de
caracteres:
• El algoritmo de Huffman comienza reemplazando
repetidas veces las 2 frecuencias más pequeñas con
la suma de las mismas hasta que se obtiene una
sucesión de 2 elementos.
1.
Se suman las 2
frecuencias más
pequeñas.
2. Después, el algoritmo
construye arboles
trabajando hacia atrás,
comenzando con la
sucesión de 2 elementos
12, 20.
3. El segundo árbol se
obtiene del primero
reemplazando el vértice
con etiqueta 20 por sus
sumandos, ya que 20
surgió por la suma de 8 y
12.
4. Se sigue con este
procedimiento hasta
obtener los números
originales (frecuencias).
• Por último, para
obtener el árbol del
código Huffman
óptimo se sustituye
cada frecuencia por
un carácter que
tenga la misma
frecuencia.
• Sin embargo, este árbol de Huffman no es único. Cuando
12 se sustituye por 5, 7, hay otra opción porque se tienen
dos vértices con etiqueta 12. Si se elige el otro con
etiqueta 12, el árbol resultante sería el siguiente:
• Cualquiera de los 2 árboles de Huffman da un código
óptimo; es decir, cualquiera de los 2 codificara texto con
las frecuencias de la tabla exactamente en el mismo
espacio.
Ejemplo:
Valor
0
1
2
3
4
5
Valor codificado
000
001
010
011
100
101
Descargar

Códigos de Huffman