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

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 бит для Aurora, 380 для Whirlwind и 420 для Phantasm (проверьте это!). Аврора имеет кратчайшую кодировку и, следовательно, в сильном смысле наиболее предсказуема.

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

Комбинируйте сначала, другие = 0.4, соедините второй, третий = 0,6. Завершите с 2 битами, кодирующими каждую позицию.

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

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

Answer 1

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

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

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. Get 1.0