• Sábado 14 de Diciembre de 2024, 19:35

Autor Tema:  Algoritmo de Huffman  (Leído 1898 veces)

Leber

  • Miembro activo
  • **
  • Mensajes: 65
    • Ver Perfil
Algoritmo de Huffman
« en: Jueves 25 de Agosto de 2011, 13:10 »
0
Hola, que tal.

Llevo un par de dias intentando implementar el algoritmo de huffman ( solo por aprender un poco más ), y a pesar de haber leido varios textos todavía tengo algunas dudas que no consigo resolver, a ver si alguien puede echarme una mano.

De momento tengo hecho:

- Tabla con valor-frequencia.
- Lista enlazada con los valores de la tabla ordenada de menor a mayor.

Es decir, teniendo la frase: "hola papa":

Código: [Seleccionar]
hola papa
Table [ 0 ]      Char:           Freq: 1
Table [ 1 ]      Char: o         Freq: 1
Table [ 2 ]      Char: h         Freq: 1
Table [ 3 ]      Char: l         Freq: 1
Table [ 4 ]      Char: p         Freq: 2
Table [ 5 ]      Char: a         Freq: 3
Total r 6
List: Char:     Freq: 1
List: Char: o   Freq: 1
List: Char: h   Freq: 1
List: Char: l   Freq: 1
List: Char: p   Freq: 2
List: Char: a   Freq: 3

Segun lo leido, el arbol huffman se forma así:

Teniendo eso: [espacio](1) - o(1) - h(1) - l(1) - p(2) - a(3)

- Se toman los dos valores con menos frequencia, por ejemplo: ( [espacio] y o ) y se forma un arbol:

   (          2         )
        /               \
" "[1 peso]          o[1 peso]

Y seguimos, ahora nos quedan: h(1) - l(1) - 2 - p(2) - a(3)
Así que cogemos "h" y "l".

Mi duda es que, a mi parecer, h y l deberían quedar asi:


               (          4        )
                   /            \
(          2         )        (         2     )             
        /          \                /       \
" "[1]           o[1]       h(1)       l(1)

Y nos queda:   p(2) - a(3) - 4


Cogemos p( 2 ) y a(3):

                                 (          9       )
                                    /                  \

               (          4        )                 (       5        )
                   /            \                        /          \
(          2         )        (         2     )         p(2)      a(3)     
        /          \                /       \
" "[1]           o[1]       h(1)       l(1)

Y nos queda: 4:

                              (               14             )
                            /                             \

                                  (          9       )            (         4       )
                                    /                  \

               (          4        )                 (       5        )
                   /            \                        /          \
(          2         )        (         2     )         p(2)      a(3)     
        /          \                /       \
" "[1]           o[1]       h(1)       l(1)

Así que de esta forma quedaría el arbol, pero creo que no es correcto.
A ver si me podéis decir donde me voy del plano y me pierdo.

Gracias de antemano
« última modificación: Jueves 25 de Agosto de 2011, 13:17 por Leber »

MDI

  • Nuevo Miembro
  • *
  • Mensajes: 2
    • Ver Perfil
Re:Algoritmo de Huffman
« Respuesta #1 en: Jueves 25 de Agosto de 2011, 20:05 »
0
 acabo de leerme el algoritmo en wikipedia y yo lo haria asi:


                                 (          9       )     
                             /                           \

               (          4        )                 (       5        )
                   /            \                        /          \
(          2         )        (         2     )         p(2)      a(3)     
        /          \                /       \
" "[1]           o[1]       h(1)       l(1)


que creo que te sobra el (  4  )  y el (  14   ), por que ya lo utilizas (el 4) para sumarselo al 5 que da 9 (que es el total)