Минимальная длина описания и кодирование Хаффмана для двух символов?

Question

Меня смущает толкование минимальной длины описания алфавита из двух символов.

Чтобы быть более конкретным, предположим, что мы хотим закодировать двоичную строку, где 1 встречаются с вероятностью 0,80; например, вот строка длиной 40 с 32 1 и 8 0:

1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 0 0 1

Следуя стандартному анализу MDL, мы можем кодировать эту строку, используя префиксные коды (например, код Хаффмана), и код кодирования этой строки будет (-log(0.8) * 32 - log(0.2) * 8), что ниже, чем дублирование строки без какой-либо кодировки.

Интуитивно понятно, что "дешевле" кодировать эту строку, чем некоторую строку, где 1 и 0 встречаются с равной вероятностью. Однако на практике я не понимаю, почему это так. По крайней мере, нам нужен один бит, чтобы различать 1 и 0. Я не понимаю, как префиксные коды могут работать лучше, чем просто писать двоичные строки без кодирования.

Может кто-нибудь помочь мне прояснить это, пожалуйста?

Answer 1

Я не понимаю, как префиксные коды могут работать лучше, чем просто писать двоичные строки без кодирования.

Вы не можете использовать префиксные коды, если только вы не объедините биты для создания большего количества символов. Например, если вы кодируете каждые два бита, теперь у вас есть четыре символа с вероятностями 0,64, 0,16, 0,16 и 0,04. Это будет закодировано с 0, 10, 110, 111. Это дает в среднем 1,56 бит на символ или 0,7800 бит на исходный бит. Мы приближаемся к оптимальным 0,7219 битам на бит (-0,2 log₂0,2 - 0,8 log₂0,8).

Сделайте это для трехбитных групп, и вы получите 0,7280 бит на бит. Удивительно близко к оптимальному. В этом случае длины кода просто очень хорошо группируются с вероятностями. Код представляет собой 1 бит (0) для символа с вероятностью 0,512, 3 бита (100, 101, 110) для трех символов с вероятностью 0,128 и 5 бит (11100, 11101, 11110, 11111) для обоих трех символов с вероятность 0,032 и один символ с вероятностью 0,008.

Вы можете продолжать движение и асимптотически приближаться к оптимальным 0,7219 битам на бит. Хотя это становится более неэффективным во времени и пространстве для больших группировок. Фронт Парето оказывается кратным трем битам до 15. 6 бит дают 0,7252 бита на бит, 9 - 0,7251, 12 - 0,7250 и 15 - 0,7249. Подход монументально медленный, где вам нужно пройти до 28 бит, чтобы добраться до 0,7221. Таким образом, вы могли бы также остановиться на 6. Или даже 3 довольно хорошо.

В качестве альтернативы вы можете использовать что-то кроме префиксного кодирования, например, арифметическое кодирование, кодирование по диапазону или асимметричное кодирование системы счисления. Они эффективно используют дробные биты для каждого символа.