Exemple compressibilité

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é, vous étudiez leurs 200 dernières courses et résumez ceux-ci comme des distributions de probabilité sur quatre résultats:. Tout d'abord ( « premier lieu »), deuxième, troisième, et d'autres

                       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 à cette question est de regarder compressibilité. Notez l'historique de chaque cheval comme une chaîne de 200 valeurs (premier, deuxième, troisième ou autre). Le nombre total de bits nécessaires pour coder ces chaînes piste enregistrement peuvent alors être calculés en utilisant l'algorithme de Huffman. Cela équivaut à 290 bits pour Aurora, 380 pour Whirlwind, et 420 pour Phantasm (vérifier!). Aurora a le plus court et le codage est donc dans un sens le plus fort prévisible.

Comment sont-ils 420 pour Phantasm? Je continue à obtenir 400 octets, comme ceci:

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

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

Textbook ici: http://www.cs.berkeley.edu/~ Vazirani / algorithms.html (page 156).

Answer 1

Je pense que vous avez raison: 200 résultats de Phantasm peuvent être représentés à l'aide de 400 bits (octets non). 290 et 380 pour Aurora 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 moins probables: 0,3 et 0,3. Obtenez 0,6.
3. Combiner 0,4 et 0,6. Obtenez 1.0.

Vous obtiendrait 420 bits si vous avez fait ceci:

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