Пример сжимаемости

Question

Из моего учебника по алгоритмам:

Ежегодные скачки в графстве собирают трех чистокровных, которые никогда не соревновались друг с другом. Возбужденные, вы изучаете их последние 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 значений (первое, второе, третье, другое). Общее количество битов, необходимых для кодирования этих строк записи дорожки, затем может быть вычислено с использованием алгоритма Хаффмана. Это работает до 290 битов для Авроры, 380 для Вихря и 420 для Фантазма (проверьте это!). Аврора имеет самую короткую кодировку и поэтому в строгом смысле слова является наиболее предсказуемой.

Как они получили 420 за Призрак? Я продолжаю получать 400 байтов, вот так:

Объединить первое, другое = 0,4, объединить второе, третье = 0,6. Получите 2 бита, кодирующих каждую позицию.

Что-то я неправильно понял в алгоритме кодирования Хаффмана?

Учебник доступен здесь: http://www.cs.berkeley.edu/~vazirani/algorithms.html (стр. 156).

Answer 1

Я думаю, что вы правы: 200 результатов Phantasm могут быть представлены с помощью 400 бит (не байтов).290 для Авроры и 380 для Вихря верны.

Правильный код Хаффмана генерируется следующим образом:

1. Объедините два наименее вероятных результата: 0,2 и 0,2.Получите 0,4.
2. Объедините следующие два наименее вероятных исхода: 0,3 и 0,3.Получите 0,6.
3. Объедините 0,4 и 0,6.Получите 1.0.

Если бы вы сделали это вместо этого, вы получили бы 420 битов:

1. Объедините два наименее вероятных результата: 0.2 и 0.2.Получите 0,4.
2. Объедините 0,4 и 0,3.(Неверно!) Получите 0,7.
3. Объедините 0,7 и 0,3.Получи 1,0