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

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

Ежегодные гонки графства вводят трех чистокровок, которые никогда не конкурировали друг против друга. Взволнованный, Вы изучаете их прошлые 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).

8
задан Steve Tjoa 10 June 2010 в 16:18
поделиться

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
4
ответ дан 6 December 2019 в 00:05
поделиться
Другие вопросы по тегам:

Похожие вопросы: