Новая тема: арифметическое кодирование
Что плохого в кодах Хаффмана?
В кодах Хаффмана код любой буквы имеет целую длину
>= 1. Но по теореме Шеннона (энтропия распределения
вероятностей) в пределе для достаточно длинных сообщений
число битов, которое необходимо использовать для
кодирования буквы, которая встречается с вероятностью p,
равно
-log_2(p)
Энтропия распределения
сумма_i p_i*(-log_2(p_i))
Допустим, алфавит состоит из 2-х букв {a, b}
с вероятностями {0.9, 0.1}
Для записи буквы a необходимое число битов
-log_2(0.9) ~= 0.152
для буквы b
-log_2(0.1) ~= 3.321
Идея: длинное сообщение кодируется всего
лишь одним вещественным числом в диапазоне
от 0 до 1
Пусть имеем алфавит из букв
a0, a1, a2, ..., a_n-1,
и известны вероятности этих букв
p0, p1, p2, ..., p_n-1,
p0 + p1 + ... + p_n-1 = 1
Сообщению мы ставим в соответствие полуинтервал
[a, b), a < b
внутри отрезка [0, 1]
Делим сначала отрезок [0, 1] на n полуинтервалов
длины p0, p1, p2, ..., p_n-1.
a0 a1 a2 a_n-1
|-----|----------|----------|--------...----|--------|
0 p0 p0+p1 p0+p1+p2 p0+...+p_n-2 1 1
Если первая буква a_k, то выбираем
k-ый полуинтервал
[p0 + p1 + ... + p_k-1, p0 + p1 + ... + p_k)
Потом выбранный полуинтервал снова делим на n частей
пропорционально вероятностям p0, p1, ..., p_n-1,
выбраем его часть, соответствующую второй букве
сообщения, и повторяем это для всех букв сообщения.
Пример: Пусть алфавит состоит из 3-х букв { 0, 1, 2 }
с вероятностями { 0.2, 0.4, 0.4 }
Закодируем сообщение 210.
Делим отрезок [0, 1] на три части в соответствии
с вероятностями:
[0, 0.2), [0.2, 0.6), [0.6, 1)
Они соответствуют буквам 0, 1, 2.
По первой букве 2 сообщения выбираем третий полуинтервал:
[0.6, 1)
Опять делим его на 3 части в соответствии с вероятностями:
[0.6, 0.68), [0.68, 0.84), [0.84, 1)
Они соответствуют сообщениям
20, 21, 22
По второй букве 1 сообщения выбираем полуинтервал
[0.68, 0.84)
и снова делим его на 3 части в соответствии
с вероятностями:
[0.68, 0.712), [0.712, 0.776), [0.776, 0.84)
Поскольку третья буква сообщения 0, то выбираем
первый полуинтервал:
[0.68, 0.712)
Он соответствует последовательности 210.
Для представления этого сообщения можно использовать
любое число из этого полуинтервала, например, 0.68
При расшифровки этого сообщения нам нужно знать,
когда остановиться. Значит, надо
1) либо заранее знать длину исходного
сообщения (3 в нашем случае),
2) либо в алфавите иметь специальный
стоп-символ (обычно он называется
EOF (End Of File) или EOD (End OF Data)),
чаще всего это самый первый символ в алфавите,
в нашем случае 0.
Итак, наше сообщение шифруется полуинтервалом
[0.68, 0.712)
Как получить двоичный код по этому сообщению?
Это делается с помощью последовательного деления
интервала [0, 1) пополам. Причем выбирается та
часть, которая пересекается с нашим интервалом
[0.68, 0.712) (если он пересекается с обеими
частями, то выбирается та, пересечение с
которой больше). Нижняя половина кодируется нулем,
верхняя единицей. Алгоритм останавливается, когда
очередная половина целиком содержится внутри нашего
интервала.
Проиллюстрируем это на картинке:
Первое деление:
[0, 0.5), [0.5, 1)
0 1
Левая половина кодируется битом 0, правая битом 1.
Наш интервал попадает во вторую часть,
поэтому выбираем её:
[0.5, 1)
1
Выбранный полуинтервал опять делим пополам:
[0.5, 0.75), [0.75, 1)
10 11
Первая половина кодируется битами 10, вторая 11.
Выбираем первую половину:
[0.5, 0.75)
10
Опять делим пополам:
[0.5, 0.625), [0.625, 0.75)
100 101
Выбираем вторую половину:
[0.625, 0.75)
101
Делим пополам:
[0.625, 0.6875), [0.6875, 0.75)
1010 1011
Наш интервал [0.68, 0.712) пересекается с обеими
половинами. Выбираем вторую половину (с ней
пересечение больше):
[0.6875, 0.75)
1011
Делим пополам:
[0.6875, 0.71875), [0.71875, 0.75)
10110 10111
Выбираем левый полуинтервал:
[0.6875, 0.71875)
10110
Делим пополам еще раз:
[0.6875, 0.703125), [0.703125, 0.71875)
101100 101101
Мы получили, что наш интервал [0.68, 0.712)
целиком содержит первую половину [0.6875, 0.703125).
Значит, итоговая кодировка 101100 (или число
в двоичной записи 0.101100 = 0.6875 в десятичной).
Если мы вычисляем только одно двоичное число -- первое,
попадающее в заданный интервал [0.68, 0.712),
то при передаче итоговые два нуля закодированного
сообщения можно было бы опустить. Но тогда нам пришлось
бы передавать дополнительно длину сообщения в битах
в заголовке закодированного сообщения (overhead).
Поэтому обычно передается левая граница
бинарного полуинтервала, в нашем случае
[0.6875, 0.703125) =
[0.101100, 0.101101) в двоичной записи,
целиком попадающего внутрь нашего полуинтервала
[0.68, 0.712). В нашем случае закодированное
сообщение -- дробная часть двоичного представления
левой границы полуинтервала, т.е. "101100".
Таким образом, исходное сообщение 210 кодируется двоичной
последовательностью 101100 длиной 6 бит. По теореме
Шеннона, для кодирования одной буквы сообщения
при данном распределении вероятностей букв нужно
в среднем как минимум
0.2*(-log2(0.2))+0.4*(-log2(0.4))+0.4*(-log2(0.4)) ~=
~= 0.2*2.322 + 0.4*1.322 + 0.4*1.322 ~= 1.522
бита, таким образом, для произвольного сообщения длины 3
требуется в среднем как минимум 3*1.522 = 4.566 бита.
Нам потребовалось 6 бит, что достаточно близко к
теоретическому минимуму. При использовании статических
кодов Хаффмана кодовое дерево выглядело бы так:
*
/ \
1 *
/ \
2 0
то есть код буквы 0 = "11", код буквы 1 = "0",
код буквы 2 = "10", сообщение 210 кодировалось бы
последовательностью "10011" длины 5. Таким образом,
в данном примере арифметическое кодирование проигрывает
кодам Хаффмана. Но наш пример совсем короткий, и при
длинных сообщениях, соответствующих зафиксированному
распределению вероятностей, коды при арифметическом
кодированнии приближаются к теоретическому минимуму,
заданному теоремой Шеннона, и выигрывают у кодов
Хаффмана.