Huffman

FACULTAD DE CIENCIAS MATEMATICAS
EAP DE INVESTIGACION OPERATIVA

Curso:

✓ Programación de computadoras I

Profesor:

✓ López Villanueva, Pablo

Temas:

✓ Árbol de Huffman

Integrantes:

✓ Apaza Ramos,Shirly 09140244

✓ Benito Arque, Erick 09140247

✓ Del Castillo Arévalo,Juan 09140255

✓ Farfán López, Nataly09140257

✓ Medina Delgado,Yefry 09140082

✓ Rojas Noriega, Jonatan 09140279

INDICE

Pag.

INTRODUCCIÓN

Por lo general las computadoras codifican los caracteres mediante códigos como el ASCII y el EBCDIC. En el caso de ASCII, se maneja con 8 bits para la representación de un byte, por lo tanto hay 28 posibles representaciones de caracteres pero siempre de longitud fija.

Unaposibilidad de disminuir el espacio, sería la de utilizar códigos de longitud variable.

Así por ejemplo, podría representarse la letra a con el valor binario 0, la letra b con el valor binario 1, la letra con el valor binario 01 y así sucesivamente. Pero ante la codificación 0101 podría interpretarse como abab o bien como cc.

El problema de codificar un 01 podría solucionarse mediante lautilización de un prefijo antes de la codificación del carácter que indique el comienzo de un carácter y el fin del anterior, pero esto encarecería nuevamente el tema del espacio que es el que ahora nos preocupa.

En ciencias de la computación y teoría de la información, la codificación Huffman es un algoritmo usado para compresión de datos. El término se refiere al uso de una tabla de códigos delongitud variable para codificar un determinado símbolo (como puede ser un carácter en un archivo), donde la tabla ha sido rellenada de una manera específica basándose en la probabilidad estimada de aparición de cada posible valor de dicho símbolo. Fue desarrollado por David A. Huffman mientras era estudiante de doctorado en el MIT, y publicado en "A Método for the Construction ofMinimum-Redundancy Codes".

♥HISTORIA

En 1951, a David Huffman y sus compañeros de clase de la asignatura “Teoría de la Información” se les permitió optar entre la realización de un examen final o la presentación de un trabajo. El profesor Robert. M. Fano asignó las condiciones del trabajo bajo la premisa de encontrar el código binario más eficiente. Huffman, ante la imposibilidad de demostrar qué código eramás eficiente, se rindió y empezó a estudiar para el examen final. Mientras estaba en este proceso vino a su mente la idea de usar árboles binarios de frecuencia ordenada y rápidamente probó que éste era el método más eficiente.
Con este estudio, Huffman superó a su profesor, quien había trabajado con el inventor de la teoría de la información Claude Shannon con el fin de desarrollar un códigosimilar. Huffman solucionó la mayor parte de los errores en el algoritmo de codificación Shannon-Fano. La solución se basaba en el proceso de construir el árbol de abajo a arriba en vez de al contrario.

DAVID HUFFMAN

Descubierto el método de compresión, el llamado código de Huffman, que son utilizados en data communication gráfica en sistemas de almacenamiento de aplicaciones.
BiographyDavidHuffman, IEEE Fellow, died 7 Oct. at a California hospital after a 10-month battle with cancer. David Huffman, IEEE Fellow, murió 07 de octubre en un hospital de California después de una batalla de 10 meses contra el cáncer. He was 74. Tenía 74 años.
Prof. Huffman earned a BS in electrical engineering from Ohio State University in 1944. Prof. Huffman obtuvo su licenciatura en ingenieríaeléctrica de la Universidad Estatal de Ohio en 1944. Upon finishing his undergraduate work, he entered the US Navy, where he served as a radar maintenance officer on a destroyer. Al terminar sus estudios de pregrado, entró en la Marina de los EE.UU., donde se desempeñó como oficial de mantenimiento del radar de un destructor. After his tour of duty, he resumed his education and received an MS at Ohio...