compresibilidad Ejemplo

Question

Desde mi algoritmos de libros de texto:

La carrera de caballos anual del condado está trayendo tres caballos pura sangre que nunca han competido unos contra otros. Emocionado, estudia sus últimas 200 carreras y las resume como distribuciones de probabilidad en cuatro resultados: primero ("primer lugar"), segundo, tercero y otros.

     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? Un acercamiento cuantitativo a esta pregunta es mirar la compresibilidad. Escriba el historial de cada caballo como una cadena de 200 valores (primero, segundo, tercero, otro). El número total de bits necesarios para codificar estas cadenas de registro de pistas se puede calcular utilizando el algoritmo de Huffman. Esto funciona con 290 bits para Aurora, 380 para Whirlwind y 420 para Phantasm (¡compruébalo!). Aurora tiene la codificación más corta y, por lo tanto, en un sentido fuerte es la más predecible.

¿Cómo consiguieron 420 para Phantasm? Sigo obteniendo 400 bytes, como mínimo:

Combinar primero, otro = 0,4, combinar segundo, tercero = 0,6. Termine con 2 bits que codifican cada posición.

¿Hay algo que haya malinterpretado sobre el algoritmo de codificación Huffman?

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

Answer 1

Creo que tiene razón: los 200 resultados de Phantasm se pueden representar utilizando 400 bits (no bytes). 290 para Aurora y 380 para Whirlwind son correctos.

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. Combine los siguientes dos resultados menos probables: 0.3 y 0.3. Obtenga 0,6.
3. Combine 0.4 y 0.6. Obtenga 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. Combine 0.4 y 0.3. (¡Incorrecto!) Obtenga 0.7.
3. Combine 0.7 y 0.3. Obtenga 1.0