Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 150 vistas

    Algoritmo de Codificación de HUFFMAN

    Cargado por

    Oscar Gallardo
    El algoritmo de codificación de Huffman asigna códigos más cortos a los símbolos más frecuentes y códigos más largos a los menos frecuentes. Se crea un árbol binario donde cada hoja representa un símbolo y la raíz representa el código completo, asignando un 0 a la rama izquierda y un 1 a la derecha para codificar cada símbolo. La decodificación se realiza recorriendo el mismo árbol bit a bit hasta alcanzar una hoja. El algoritmo depende de estimaciones precisas de las

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd

    Algoritmo de Codificación de HUFFMAN

    Cargado por

    Oscar Gallardo
    150 vistas16 páginas
    El algoritmo de codificación de Huffman asigna códigos más cortos a los símbolos más frecuentes y códigos más largos a los menos frecuentes. Se crea un árbol binario donde cada hoja representa un símbolo y la raíz representa el código completo, asignando un 0 a la rama izquierda y un 1 a la derecha para codificar cada símbolo. La decodificación se realiza recorriendo el mismo árbol bit a bit hasta alcanzar una hoja. El algoritmo depende de estimaciones precisas de las

    Derechos de autor

    © Attribution Non-Commercial (BY-NC)

    Formatos disponibles

    PPTX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El algoritmo de codificación de Huffman asigna códigos más cortos a los símbolos más frecuentes y códigos más largos a los menos frecuentes. Se crea un árbol binario donde cada hoja representa un símbolo y la raíz representa el código completo, asignando un 0 a la rama izquierda y un 1 a la derecha para codificar cada símbolo. La decodificación se realiza recorriendo el mismo árbol bit a bit hasta alcanzar una hoja. El algoritmo depende de estimaciones precisas de las

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    150 vistas16 páginas

    Algoritmo de Codificación de HUFFMAN

    Cargado por

    Oscar Gallardo
    El algoritmo de codificación de Huffman asigna códigos más cortos a los símbolos más frecuentes y códigos más largos a los menos frecuentes. Se crea un árbol binario donde cada hoja representa un símbolo y la raíz representa el código completo, asignando un 0 a la rama izquierda y un 1 a la derecha para codificar cada símbolo. La decodificación se realiza recorriendo el mismo árbol bit a bit hasta alcanzar una hoja. El algoritmo depende de estimaciones precisas de las

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Descargue como PPTX, PDF, TXT o lea en línea desde Scribd
    Descargar como pptx, pdf o txt
    de 16

    Algoritmo de Codificacin de HUFFMAN

    Presentado por Oscar Gallardo R Catedra Diseo y Anlisis de Algoritmo 5 Semestre CIISA 2010

    Caractersticas

    Asigna a los smbolos ms frecuentes un cdigo de compresin de menor longitud a costa de asignar cdigos de mayor longitud a los menos frecuentes.

    El nmero de bits por cdigo de compresin es un nmero entero. Huffman no puede ser considerado como un mtodo de codificacin

    ptimo, pero si es la mejor aproximacin para construir cdigos de


    compresin con un nmero entero de bits.

    Aunque los cdigos asociados a smbolos diferentes tienen diferente longitud, stos pueden ser decodificados de forma nica. Dicha caracterstica recibe el nombre de propiedad del prefijo nico y se basa en que ningn cdigo de compresin es prefijo (forma parte inicial) de cualquier otro cdigo de compresin.

    Algoritmo de creacin del rbol de Huffman


    1.

    Crear tantos nodos (que sern las hojas del rbol) como smbolos vayamos a codificar. En cada nodo almacenaremos el smbolo codificado y su probabilidad. Estos nodos forman la lista de nodos sin procesar.

    Ejemplo a codificar ABBDCCDEDDCADCA


    Se usaran solo los caracteres ABCDE, en maysculas y sin espacios.

    Algoritmo de creacin del rbol de Huffman

    Nodos creados con su frecuencia en el ejemplo D-5 C-4 A-3 B-2 E-1 Para construir nuestro rbol tomamos los nodos mas pequeos y creamos un nodo principal, con la concatenacion de ambos nodos. BE

    Algoritmo de creacin del rbol de Huffman

    Continuamos construyendo nuestro rbol. Paso 2

    ABE
    BE A B E

    Algoritmo de creacin del rbol de Huffman

    Continuamos construyendo nuestro rbol. Paso 3 CABE ABE BE C

    Algoritmo de creacin del rbol de Huffman

    Paso 3 : Finalmente tenemos terminado nuestro rbol

    DCAB E
    CABE ABE BE D C A

    Algoritmo de creacin del rbol de Huffman

    Para preparar el rbol para la codificacion, cada rama se le asigna un 1 a la rama derecha y 0 a la izquierda. DCAB 1 E CABE 1
    0 0

    ABE
    0

    1 0

    BE

    Codificacin

    Para codificar cada letra se recorre el rbol tomando los cdigos asignados a cada rama. DCAB E
    0 0 1

    CABE

    ABE
    0

    1 0

    BE

    Codificacin

    Para codificar cada letra se recorre el rbol tomando los cdigos asignados a cada rama.
    Letra D C A B E Cdigo 0 10 110 1110 1111

    Codificacin

    Finalmente la codificacin queda de la siguiente manera :

    Ejemplo : ABBDCCDEDDCADCA Codificado : 110111011100101001111001011001011 0

    Decodificacin

    La decodificacin se realiza utilizando el mismo rbol de Huffman generado durante el proceso de codificacin. Gracias a la propiedad del prefijo nico, la secuencia de cdigos se recorre bit a bit y un smbolo es decodificado cada vez que desde la raz alcanzamos una hoja. Veamos un ejemplo de decodificacin. Utilizando el rbol de la figura, vamos a decodificar el mensaje comprimido de la seccin anterior.

    Letra

    Cdigo 0 10

    Decodificacin

    D C

    A El primer bit (1) no lo tenemos como un 110 carcter B 1110 valido, seguimos avanzando hasta encontrar la E 1111 primera secuencia vlida en este caso (110) esto indica que el primer smbolo de la secuencia de smbolos es el A. (1101110111001010011110010110010110)

    Para decodificar el siguiente smbolo nos situamos de en la siguiente posicion y utilizamos los bits siguientes hasta que encontremos otra coincidencia, en este caso corresponde (1110) el cual el simbolo es B (1101110111001010011110010110010110)

    Decodificacin

    Dejamos de extraer bits de la secuencia de cdigos cuando alcanzamos una coincidencia. Este proceso se repite hasta que no quedan ms bits que decodificar.
    A B B D C
    Letra D

    110 1110 1110 0 10 10 0 1111 0 0 10 110 0 10 110

    C D

    DD C
    Cdigo 0

    A D C

    C
    A B E

    10
    110 1110 1111

    Limitaciones

    Para poder utilizar el algoritmo de Huffman es necesario conocer de antemano las frecuencias de aparicin de cada smbolo, y su eficiencia depende de lo prximas a las frecuencias reales que sean las estimadas. Algunas implementaciones del algoritmo de Huffman son adaptativas, actualizando las frecuencias de cada smbolo conforme recorre el texto. La eficiencia de la codificacin de Huffman tambin depende del balance que exista entre los hijos de cada nodo del rbol, siendo ms eficiente conforme menor sea la diferencia de frecuencias entre los dos hijos de cada nodo.

    Algoritmo de Codificacin de HUFFMAN


    Presentado por Oscar Gallardo R Catedra Diseo y Anlisis de Algoritmo 5 Semestre CIISA 2010

    También podría gustarte