compressibilité Exemple

Question

De mes algorithmes manuel:

La course annuelle de cheval du comté apporte trois pur-sang qui n'ont jamais participé les uns contre les autres. Excités, vous étudiez leurs 200 dernières courses et les résumez sous forme de distributions de probabilités sur quatre résultats: premier («premier lieu»), deuxième, troisième et autre.

     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 

Quel cheval est le plus prévisible? Une approche quantitative de cette question consiste à examiner la compressibilité. Notez l'histoire de chaque cheval comme une chaîne de 200 valeurs (première, deuxième, troisième, autre). Le nombre total de bits nécessaires pour coder ces chaînes de piste peut alors être calculé en utilisant l'algorithme de Huffman. Cela correspond à 290 bits pour Aurora, 380 pour Whirlwind et 420 pour Phantasm (vérifiez-le!). Aurora a l'encodage le plus court et est donc dans un sens fort le plus prévisible. Comment ont-ils obtenu 420 pour Phantasm?

Comment ont-ils obtenu 420 pour Phantasm? Je continue à obtenir 400 octets, comme suit:

Combiner d'abord, autre = 0,4, combiner deuxième, troisième = 0,6. Terminez avec 2 bits codant chaque position.

Y at-il quelque chose que j'ai mal compris à propos de l'algorithme de codage Huffman?

Manuel disponible ici: http://www.cs.berkeley.edu/~vazirani/algorithms.html (page 156).

Answer 1

Je pense que vous avez raison: les 200 résultats de Phantasm peuvent être représentés en utilisant 400 bits (pas des octets). 290 pour Aurora et 380 pour Whirlwind sont corrects.

le bon code de Huffman est généré de la manière suivante:

1. combiner les deux résultats les moins probables: 0,2 et 0,2. Obtenez 0,4.
2. Combiner les deux résultats les moins probables suivants: 0,3 et 0,3. Obtenez 0.6.
3. Combiner 0,4 et 0,6. Obtenez 1.0.

Vous obtenez 420 bits si vous avez fait ceci:

1. combinons les deux résultats les moins probables: 0,2 et 0,2. Obtenez 0,4.
2. Combiner 0,4 et 0,3. (Mauvais!) Obtenez 0,7.
3. Combiner 0,7 et 0,3. Obtenir 1,0