Algoritmo De Huffman
Páginas: 3 (607 palabras)
Publicado: 15 de abril de 2011
PROGRAMACION LOGICA Y FUNCIONAL
ALGORITMO DE HUFFMAN
La codificacion de Huffman es una tecnica para la compresion o encriptacion de datos, mediante el estudio de la frecuencia de aparicion decaracteres,ampliamente usada y muy efectiva. Fue desarrollado por el norteamericano David Albert Huffman en 1952 mientras hacia el doctorado en el MIT. El algortimo funciona a partir de un conjuntodado de simbolos con sus respectivos pesos. Los pesos son la frecuencia de aparicion en una cadena.
Ejemplo: Archivo con 100,000 caracteres. Se sabe que aparecen 6 caracteres diferentes y lafrecuencia de aparicion de cada uno de ellos es:
Como codificar los caracteres para comprimir el espacio ocupado utilizando un codigo binario?
Solucion 1: Codigo de longitud fija
Para seiscaracteres se necesitan 3 bits (300,000 bits)
Solucion 2: Codigo de longitud variable en el que los mas frecuentes tienen el codigo mas corto. Restriccion: ningun codigo es prefijo de otro.
Estatecnica de codificacion se denomina codigo prefijo.
Un arbol binario es una forma de representar el codigo prefijo que significa el proceso de descodificacion:
Las hojas con los caracteres.
El caminode la raiz a las hojas con la interpretacion 0 a la izquierda y 1 a la derecha nos da el codigo de cada hoja.
Este seria el arbol binario de la codificacion de longitud fija:
Y este el de lacodificacion de longitud variable:
Dado T el arbol binario que corresponde a una codificacion prefijo, es facil averiguar el numero de bits necesarios para codificar el archivo:
Para cada caracterc diferente del alfabeto C que aparece en el archivo:
sea f(c) la frecuencia de c en cada entrada
sea dr(c) la profundidad de la hoja c en el arbol T, entonces el numero de bits requeridos es:B(T) = Σ f(c) · dr(c)
c ϵ C
B(T) nos da el coste de T.
CODIGO LIPS
(defstruct nodo
(long 0 :type number)
(elem nil :type t)
(cod nil :type (or null bit-vector))
(izq...
ALGORITMO DE HUFFMAN
La codificacion de Huffman es una tecnica para la compresion o encriptacion de datos, mediante el estudio de la frecuencia de aparicion decaracteres,ampliamente usada y muy efectiva. Fue desarrollado por el norteamericano David Albert Huffman en 1952 mientras hacia el doctorado en el MIT. El algortimo funciona a partir de un conjuntodado de simbolos con sus respectivos pesos. Los pesos son la frecuencia de aparicion en una cadena.
Ejemplo: Archivo con 100,000 caracteres. Se sabe que aparecen 6 caracteres diferentes y lafrecuencia de aparicion de cada uno de ellos es:
Como codificar los caracteres para comprimir el espacio ocupado utilizando un codigo binario?
Solucion 1: Codigo de longitud fija
Para seiscaracteres se necesitan 3 bits (300,000 bits)
Solucion 2: Codigo de longitud variable en el que los mas frecuentes tienen el codigo mas corto. Restriccion: ningun codigo es prefijo de otro.
Estatecnica de codificacion se denomina codigo prefijo.
Un arbol binario es una forma de representar el codigo prefijo que significa el proceso de descodificacion:
Las hojas con los caracteres.
El caminode la raiz a las hojas con la interpretacion 0 a la izquierda y 1 a la derecha nos da el codigo de cada hoja.
Este seria el arbol binario de la codificacion de longitud fija:
Y este el de lacodificacion de longitud variable:
Dado T el arbol binario que corresponde a una codificacion prefijo, es facil averiguar el numero de bits necesarios para codificar el archivo:
Para cada caracterc diferente del alfabeto C que aparece en el archivo:
sea f(c) la frecuencia de c en cada entrada
sea dr(c) la profundidad de la hoja c en el arbol T, entonces el numero de bits requeridos es:B(T) = Σ f(c) · dr(c)
c ϵ C
B(T) nos da el coste de T.
CODIGO LIPS
(defstruct nodo
(long 0 :type number)
(elem nil :type t)
(cod nil :type (or null bit-vector))
(izq...
Leer documento completo
Regístrate para leer el documento completo.