compressibilità Esempio

Question

Dal mio algoritmi libro di testo:

L'annuale corsa di cavalli della contea sta portando in tre purosangue che non hanno mai gareggiato uno contro l'altro. Eccitato, studi le loro ultime 200 gare e le riassumo come distribuzioni di probabilità su quattro risultati: primo ("primo posto"), secondo, terzo e altro.

     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 

Quale cavallo è il più prevedibile? Un approccio quantitativo a questa domanda è guardare alla compressibilità. Annota la storia di ogni cavallo come una stringa di 200 valori (primo, secondo, terzo, altro). Il numero totale di bit necessari per codificare queste stringhe del track record può quindi essere calcolato utilizzando l'algoritmo di Huffman. Funziona a 290 bit per Aurora, 380 per Whirlwind e 420 per Phantasm (controllalo!). Aurora ha la codifica più breve ed è quindi in un certo senso il più prevedibile.

Come hanno ottenuto 420 per Phantasm? Continuo a ricevere 400 byte, così:

Combina prima, altro = 0,4, combina secondo, terzo = 0,6. Finisci con 2 bit che codificano ogni posizione.

C'è qualcosa che ho frainteso sull'algoritmo di codifica di Huffman?

Testo disponibile qui: http://www.cs.berkeley.edu/~vazirani/algorithms.html (pagina 156).

Answer 1

Penso che tu abbia ragione: i 200 risultati di Phantasm possono essere rappresentati utilizzando 400 bit (non i byte). 290 per Aurora e 380 per Whirlwind sono corretti.

Il codice Huffman corretto viene generato nel modo seguente:

1. combinare i due esiti meno probabili: 0,2 e 0,2. Ottieni 0.4.
2. Combina i due risultati meno probabili seguenti: 0.3 e 0.3. Ottieni 0.6.
3. Combina 0.4 e 0.6. Ottieni 1.0.

Si otterrebbe 420 bit se avete fatto questo, invece:

1. combinare i due esiti meno probabili: 0,2 e 0,2. Ottieni 0.4.
2. Combina 0.4 e 0.3. (Sbagliato!) Ottieni 0.7.
3. Combina 0,7 e 0,3. Get 1.0