Из моего учебника алгоритмов:
Ежегодные гонки графства вводят трех чистокровок, которые никогда не конкурировали друг против друга. Взволнованный, Вы изучаете их прошлые 200 гонок и суммируете их как распределения вероятностей более чем четыре результата: первый (“первое место”), во-вторых, в-третьих, и другой.
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
Какая лошадь является самой предсказуемой? Один количественный подход к этому вопросу должен посмотреть на сжимаемость. Запишите историю каждой лошади как строка 200 значений (первый, второй, третий, другой). Общее количество битов должно было закодировать эти строки послужного списка, может затем быть вычислен с помощью алгоритма Huffman. Это удается к 290 битам для Авроры, 380 для Вихря, и 420 для Фантома (проверьте его!). Аврора имеет самое короткое кодирование и находится поэтому в строгом смысле самое предсказуемое.
Как они добирались 420 для Фантома? Я продолжаю получать 400 байтов, как так:
Объединитесь сначала, другой = 0.4, объединение, второе, третье = 0.6. Закончите с 2 битами, кодирующими каждое положение.
Есть ли что-то, что я неправильно понял об алгоритме Кодирования методом Хаффмана?
Учебник, доступный здесь: http://www.cs.berkeley.edu/~vazirani/algorithms.html (страница 156).
Думаю, вы правы: 200 результатов Phantasm могут быть представлены в 400 битах (не байтах). 290 для Авроры и 380 для Вихря верны.
Правильный код Хаффмана генерируется следующим образом:
Вы бы получили 420 бит, если бы вместо этого сделали следующее: