Codificacion huftman

ALGORITMO DE COMPRESIÓN DE HUFFMAN

FUNDAMENTOS DE TRANSMISIÓN DE DATOS

1.- Descripción El algoritmo de Huffman se basa en la asignación de códigos de longitud variable a cada uno de lossímbolos de una fuente de mensajes. Se trata de un codificador óptimo, por lo que puede ser utilizado para la compresión de ficheros. Otra aplicación de este codificador es la de encriptación de datos. Lacapacidad de compresión de la información se debe a la asignación de códigos de menor longitud a los símbolos que aparecen con más probabilidad en la fuente, consiguiendo con ello la reducción de lalongitud media de las palabras código asociadas a los mensajes. Para realizar la codificación, se ordenan los símbolos en orden decreciente de sus probabilidades. Los dos símbolos menos probables seagrupan en un pseudosímbolo cuya probabilidad es la suma de las probabilidades de los símbolos fusionados (la palabra código asignada a estos símbolos difiere solamente en la última posición). Losrestantes símbolos-pseudosímbolos son nuevamente ordenados en función de sus probabilidades, combinando los dos menos probables y sumando sus probabilidades en un nuevo pseudosímbolo. El proceso se repitehasta que todo el árbol generado se reduce a un símbolo con probabilidad igual a la unidad. Para recuperar el fichero original es necesario conocer el código asignado a cada carácter, así como sulongitud en bits. Si esta información se omite, y el receptor del fichero la conoce, podrá recuperar la información original. De este modo es posible utilizar el algoritmo para encriptar ficheros. 2.-Realización del algoritmo El procedimiento a seguir en la realización del algoritmo de compresión sería el siguiente:
• Contar cuantas veces aparece cada carácter en la secuencia a comprimir y

crearuna lista enlazada con la información de caracteres y frecuencias. • Ordenar la lista de menor a mayor en función de la frecuencia. • Convertir cada elemento de la lista en un árbol. • Fusionar todos...