Código de Huffman

Código de Huffman

de Mariana Karina Gelos Balparda -
Número de respuestas: 3

Hola, haciendo ejercicios de parciales anteriores llegamos a codificaciones distintas a las que plantean las soluciones. Además usando el método que se dio en clase se llega una codificación distinta a la que se obtiene con el método de árboles (método que se usa en la solución del parcial 2014).

La pregunta es si es relevante a que codificación se llega, o lo importante es llegar a alguna codificación con el mínimo largo posible.

Creemos que la diferencia se da cuando hay varias probabilidades iguales y no sabemos cual es el criterio para agruparlas.

Gracias

Saludos

En respuesta a Mariana Karina Gelos Balparda

Re: Código de Huffman

de Yuri Damian Vallejo Iglesias -

No es relevante la codificación a la que se llega. Pero sí podés verifcar si el código está bien comparando los largos con la solución del parcial. Por ejemplo a mí me dio así:

2 1111

3 110

4 011

5 00

6 10

7 010

8 1110

Los largos coinciden con los del parcial, el 2 y el 8 tienen cuatro dígitos, el 3 y el 7 tienen 3, el 4 y el 6 uno tiene 3 y el otro 2 (eso podría haber quedado al revés) y el 5 tiene 2.
Otra verificación es que el código es instantáneo, o sea que ninguna palabra es prefijo de otra.

Cada vez que se abren dos ramas, tenés la posibilidad de asignar 1 o 0 a cualquiera de ellas. Y si por ejemplo tenés tres probabilidades iguales (o una menor y dos iguales), podés agruparlas de tres (dos) maneras distintas.

O sea que tenés varios códigos posibles y todos son correctos.

En respuesta a Yuri Damian Vallejo Iglesias

Re: Código de Huffman

de Federico Lecumberry -

El código óptimo no es único; intercambiando los 0 por 1 y viceversa se llegan a palabras de código diferente, pero el largo medio es el mismo que es la métrica que se desea minimizar.

Ciertas combinaciones de probabilidades pueden lugar a largos de palabras de código diferentes, según cómo se arme el árbol. Por ejemplo, en un paso de la construcción del árbol quedan tres símbolos de probabilidades {1/3,1/3,1/3}; en este caso se pueden armar tres árboles diferentes a partir de este punto, que generarán palabras de código de largos diferentes. Pero el largo medio será el mismo.