Esempio di compressibilità

Question

Dal mio libro di testo sugli algoritmi:

L'annuale corsa di cavalli della contea coinvolge tre purosangue che non hanno mai gareggiato uno contro l'altro.Entusiasta, studi le loro ultime 200 gare e le riassumi 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 consiste nel considerare la compressibilità.Annota la storia di ciascun 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 senso stretto la più prevedibile.

Come hanno fatto a ottenere 420 per Phantasm?Continuo a ricevere 400 byte, in questo modo:

Combina primo, altro = 0,4, combina secondo, terzo = 0,6.Termina con 2 bit che codificano ciascuna posizione.

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

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

Answer 1

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

Il codice Huffman corretto viene generato nel modo seguente:

1. Combina i due risultati meno probabili:0,2 e 0,2.Ottieni 0,4.
2. Combina i prossimi due risultati meno probabili:0,3 e 0,3.Ottieni 0,6.
3. Combina 0,4 e 0,6.Ottieni 1.0.

Otterresti 420 bit se invece facessi questo:

1. Combina i due risultati 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.Ottieni 1.0