Aus meinem Algorithmen Lehrbuch:Kompressibilität Beispiel
Die jährlichen Kreispferderennen werden in drei Vollblüter zu bringen, die gegen eine nie teilgenommen haben ein anderes. Aufgeregt studieren Sie ihre vergangenen 200 Rennen und fassen diese als Wahrscheinlichkeitsverteilung über vier Ergebnisse zusammen: zuerst ("erster Platz"), zweiter, dritter und anderer.
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
Welches Pferd ist das vorhersehbar? Ein quantitativer Ansatz für diese Frage ist die Komprimierbarkeit. Schreiben Sie die Geschichte jedes Pferdes als eine Kette von 200 Werten auf (erste, zweite, dritte, andere). Die Gesamtzahl der Bits, die zum Codieren dieser Verfolgungsaufzeichnungsfolgen benötigt werden, kann dann unter Verwendung des Huffman-Algorithmus berechnet werden. Dies ergibt 290 Bit für Aurora, 380 für Whirlwind und 420 für Phantasm (überprüfen Sie es!). Aurora hat die kürzeste Kodierung und ist daher in einem starken Sinne am vorhersehbarsten.
Wie haben sie 420 für Phantasm bekommen? Ich bekomme immer 400 Bytes, so:
Kombiniere zuerst, andere = 0,4, kombinieren zweite, dritte = 0,6. Ende mit 2 Bits, die jede Position kodieren.
Gibt es etwas, was ich über den Huffman-Codierungsalgorithmus falsch verstanden habe?
Lehrbuch hier verfügbar: http://www.cs.berkeley.edu/~vazirani/algorithms.html (Seite 156).
"Welches Pferd ist am vorhersehbarsten?" - das beantwortet das nicht, denn die Platzierung hängt von den anderen Pferden im Rennen ab. Aurora könnte den Kurs jedes Mal genau zur gleichen Zeit ausführen - bis zur Millisekunde! - und immer noch die dort gezeigten Ergebnisse wegen der anderen Pferde im Rennen bekommen. –