Ejemplo compresibilidad

Question

A partir de mis algoritmos Libro de texto:

  

La carrera de caballos anual del condado está trayendo tres caballos pura sangre que nunca han competido unos contra otros. Excitado, estudiar sus últimos 200 carreras y resumir estos como distribuciones de probabilidad sobre cuatro resultados:. Primero ( “primer lugar”), segunda, tercera, y otra

                       Outcome     Aurora   Whirlwind    Phantasm
                        first        0.15      0.30          0.20

                        second       0.10      0.05          0.30

                        third        0.70      0.25          0.30

                        other        0.05      0.40          0.20

  

¿Qué caballo es el más predecible? Una aproximación cuantitativa a esta pregunta es mirar a la compresibilidad. Anote la historia de cada caballo como una cadena de 200 valores (primero, segundo, tercero, otros). El número total de bits necesarios para codificar estas cadenas trayectoria entonces se pueden calcular usando el algoritmo de Huffman. Esto funciona a 290 bits para Aurora, 380 de torbellino, y 420 para el Fantasma (comprobarlo!). Aurora tiene la codificación más corta y por lo tanto es en un sentido fuerte el más predecible.

¿Cómo llegaron a 420 Fantasma? Sigo recibiendo 400 bytes, por lo que:

Combinar primero, otra = 0,4, se combinan segundo, tercero = 0,6. Terminar con 2 bits que codifica cada posición.

¿Hay algo que yo he entendido mal acerca de la codificación de Huffman algoritmo?

libro de texto disponible aquí: http://www.cs.berkeley.edu/~ Vazirani / algorithms.html (página 156).

Answer 1

Te pensar en lo cierto: 200 resultados de Phantasm pueden representarse mediante 400 bits (no bytes). 290 y 380 para Aurora de torbellino son correctas.

El código de Huffman correcta se genera de la siguiente manera:

1. combinar los dos resultados menos probables: 0,2 y 0,2. Obtener 0,4.
2. Combinar los próximos dos resultados menos probables: 0,3 y 0,3. Obtener 0,6.
3. Cosechadora 0,4 y 0,6. Obtener 1.0.

obtendría 420 bits de si se hizo esto en su lugar:

1. combinar los dos resultados menos probables: 0,2 y 0,2. Obtener 0,4.
2. Cosechadora 0,4 y 0,3. (Mal!) Obtener 0,7.
3. Cosechadora 0,7 y 0,3. Obtener 1.0