tema 3) Codigo huffman

 Ejemplo de uso del codigo Huffman

David A. Huffman ( 9 de agosto de 1925 - 7 de octubre de 1999) fue un personaje ilustre en el campo de ciencias de la computación en general y en la codificación de datos en particular, además de ser profesor en EE. UU.

La idea central es crear un árbol binario óptimo donde cada carácter tiene asociado un código binario.

El algoritmo de Huffman es un método de compresión sin pérdida que asigna códigos binarios más cortos a los símbolos más frecuentes, y códigos más largos a los menos frecuentes.Si va por la pare izquierda es un 0 y si va por la parte derecha es un 1.

el carácter ‘O’ aparece 11 veces y el carácter ‘C’ aparece 7 veces. Estos son los caracteres que más veces aparecen y por lo tanto tienen la mayor probabilidad de ocurrencia. En cambio, los caracteres ‘I’, ‘N’, ‘R’, ‘S’ y ‘U’ aparecen una única vez; esto signifi ca que la probabilidad de hallar en el archivo alguno de estos caracteres es muy baja. Como ya sabemos, para codifi car cualquier carácter se necesitan 8 bits (1 byte). Sin embargo, supongamos que logramos encontrar una combinación única de 2 bits con la cual codifi car al carácter ‘O’, una combinación única de 3 bits con la cual codifi car al carácter ‘M’ y otra combinación única de 3 bits con la cual codifi car al carácter ‘C’. Byte o Carácter Codifi cación O 01 M 001 C 000 Si esto fuera así, entonces para codifi car los primeros 3 caracteres del texto anterior solo necesitaríamos 1 byte, lo que nos daría una tasa de compresión del 66.6%. Carácter C O M … Byte 000 01 001 … Ahora, el byte 00001001 representa la secuencia de caracteres ‘C’, ‘O’, ‘M’, pero esta información solo podrá ser interpretada si conocemos los códigos binarios que utilizamos para recodifi car los bytes originales. De lo contrario, la información no se podrá recuperar. Para obtener estas combinaciones de bits únicas, el algoritmo de Huffman propone seguir una serie de pasos a través de los cuales obtendremos un árbol binario llamado “arbol Huffman”. Luego, las hojas del árbol representarán a los diferentes caracteres que aparecen en el archivo y los caminos que se deben recorrer para llegar a esas hojas representarán la nueva codifi cación del carácter. A continuación, analizaremos los pasos necesarios para obtener el árbol y los códigos Huffman que corresponden a cada uno de los caracteres del texto expresado más arriba.