Теория информации
2.2 Оптимальные методы статистического сжатия информации
Оптимальными методами статистического кодирования сообщений, минимизирующими среднюю длину кода, являются статистические алгоритмы сжатия Шеннона-Фано и Хаффмана. Данные алгоритмы относятся к так называемым кодам без памяти.
Для кода без памяти – кода, не учитывающего значения предыдущих символов, каждый символ в кодируемой последовательности заменяется кодовым словом из префиксного множества двоичных слов.
2.2.1 Элементы теории префиксных множеств
Префиксным множеством двоичных последовательностей S называется конечное множество таких двоичных последовательностей, что ни одна последовательность в этом множестве не является префиксом (началом) никакой другой последовательности S.
Если S={w1, w2, …, wk} – префиксное множество, то можно определить некоторый вектор n(S)=(L1, L2, …, Lk), состоящий из значений длин соответствующих префиксных последовательностей.
Вектор (L1, L2, …, Lk), состоящий из неуменьшающихся положительных целых чисел, называется вектором Крафта. Для него выполняется неравенство
, (2.1)
которое называется неравенством Крафта, для которого справедливо следующее утверждение: если S - какое-либо префиксное множество, то n(S)- вектор Крафта.
Если неравенство (2.1) переходит в строгое равенство, то такой код называется компактным и обладает наименьшей средней длиной среди кодов с данным алфавитом, т.е. является оптимальным.
Примеры префиксных множеств и соответствующих им векторов Крафта:
S1={0, 10, 11}® n(S1)={1, 2, 2};
S2={0, 10, 110, 111}® n(S2)={1, 2, 3, 3};
S3={0, 10, 110, 1110, 1111® n(S3)={1, 2, 3, 4, 4};
S4={0, 10, 1100, 1101, 1110, 1111}® n(S4)={1, 2, 4, 4, 4, 4};
S5={0, 10, 1100, 1101, 1110, 11110, 11111}® n(S5)={1, 2, 4, 4, 4, 5, 5};
S6={0, 10, 1100, 1101, 1110, 11110, 111110, 111111}® n(S6)= {1, 2, 4, 4, 4, 5, 6, 6}.
Допустим, мы хотим разработать код без памяти для сжатия вектора данных x={x1, x2, …, xn} с алфавитом A объемом k.
Обозначим как F=(F1, F2, …, Fk) вектор частот символов алфавита A, встречающихся в сообщении X.
Кодирование кодом без памяти происходит следующим образом:
1) составляется список символов алфавита A: a1, a2, …, as, …, ak в порядке убывания их частот появления в X;
2) каждому символу aj назначается кодовое слово wj из префиксного множества двоичных последовательностей S, для которого вектор Крафта (L1, L2, …, Lk);
3) выход кодера получают объединением в одну последовательность всех полученных двоичных слов.
Тогда длина кодовой последовательности на выходе кодера источника составит
L(X)=L×F=L1×F1+ L2×F2+…+ Lk×Fk. (2.2)
Наилучшим, или оптимальным кодом, является префиксный код, для которого произведение L×F минимально: L×F® min.
2.2.2 Статистические алгоритмы сжатия Шеннона-Фано и Хаффмена
Метод Шеннона-Фано. Значения д. с. в. располагаются в порядке убывания вероятностей. Затем вся совокупность разбивается на две приблизительно равные по сумме вероятностей группы: к коду первой группы добавляют 0, а к коду второй – 1. Каждая из групп по тому же принципу снова разбивается (если это возможно) на две части и т. д.
Пример 3 Рассмотрим пример применения алгоритма Шеннона-Фано для кодирования сообщений, имеющих различную вероятность (табл. 2.2).
Коды значений заданной д. с. в. представлены таблицей 2.3.
Таблица 2.3
Буква хi |
Вероят- ность, pi |
Код |
Длина кода, li |
pili |
||||||
А Б В Г Д Е Ж З |
0,6 0,2 0,1 0,04 0,025 0,015 0,01 0,01 |
0 0 0 0 0 0 |
0 0 0 0 0 0 |
0 0 0 0 0 |
0 0 0 0 |
0 0 |
0 |
|
1 2 3 4 5 6 7 8 |
0,6 0,4 0,3 0,16 0,125 0,09 0,07 0,07 |
åpi=1 |
åpili=1,815 |
|||||||||
Среднее число
символов для такого кода (бит/сим).
Избыточность
кода ,
т.е. на порядок меньше, чем при равномерном кодировании (см. пример
1).
Алгоритм Хаффмана изящно иллюстрирует общую идею статистического кодирования с использованием префиксных множеств.
Метод Хаффмана. Код строится при помощи бинарного дерева. Вероятности д. с. в. располагаются в порядке убывания и приписываются листьям кодового дерева. Величина, приписываемая узлу дерева, называется весом узла. Два листа или узла c наименьшими весами образуют родительский узел с весом, равным сумме весов его образовавших узлов. В дальнейшем этот узел учитывается наравне с оставшимися листьями, а его образовавшие листья или узлы больше не рассматриваются. После постройки корня кодового дерева каждой определенной ветви, исходящей из родительского узла, приписывается 0 или 1, обычно: левой 0, правой – 1. Код значений д. с. в. – это комбинация 0 и 1, получаемая по пути от корня к листу, соответствующему вероятности кодируемого значения д. с. в.
Пример 4 Рассмотрим пример кодирования неравновероятных сообщений по алгоритму Хаффмена.
Дерево кодирования заданной д.с.в. (таблица 2.2) и таблица кодов по алгоритму Хаффмена показаны на рис. 2.6 и в таблице 2.4.
Рисунок 2.6
Таблица 2.4
Буква Хi |
Вероятность рi |
Код Code(Хi) |
Длина кода, li |
lipi |
А Б В Г Д Е Ж З |
0,6 0,2 0,1 0,04 0,025 0,015 0,01 0,01 |
0 1 1 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 |
1 2 3 4 5 6 7 7 |
0,6 0,4 0,3 0,16 0,125 0,09 0,07 0,07 |
|
åpili=1,815 |
Для такого кода средняя длина (бит/сим).
Избыточность
кода ,
т. е. также существенно меньше, чем для примитивного кода.
Обратим внимание, что для кодов Хаффмена и Шеннона-Фано среднее количество битов, приходящееся на одно элементарное сообщение, приближается к энтропии источника, однако не может быть её меньше.
Такой вывод является следствием теоремы кодирования источника в отсутствии шума[2]:
любой источник дискретных сообщений можно закодировать двоичной последовательностью при среднем количестве двоичных символов (битов) на одно элементарное сообщение сколь угодно близком к энтропии источника Н(Х), и невозможно добиться средней длины кода, меньшей, чем энтропия Н(Х).
Практическое значение этой теоремы трудно переоценить – она устанавливает границы компактности представления информации, которых можно достичь при правильном ее кодировании.
Недостатки алгоритмов Шеннона-Фано и Хаффмена:
1 Необходимость составления таблицы кодов для каждого типа сжимаемых данных. Данный недостаток несущественен, если сжимается русский или английский текст. Однако в общем случае, когда вероятность символов неизвестна, данные методы кодирования реализуются в два прохода: первый используется для сбора частот символов, оценки их вероятностей и составления кодовой таблицы, второй – для сжатия.
2 Необходимость хранения (передачи) таблицы кодов вместе со сжатым сообщением, что снижает общий эффект сжатия.
3 Минимальная длина кодовых слов не может быть меньше 1 бита, тогда как энтропия сообщения может быть близка к нулю. В таком случае оптимальные методы сжатия оказываются существенно избыточными. Данный недостаток преодолевается применением алгоритма к блокам символов, рассматриваемым как единицы сообщения, однако при этом усложняется процедура кодирования/ декодирования, и значительно расширяется таблица кодов.
4 Средняя длина кода совпадает с энтропией (наилучший случай) только в случае, когда вероятности символов являются целыми отрицательными степенями двойки, т.е. 1/2, 1/4, 1/8, 1/16 и т.д. На практике такая ситуация встречается редко или может быть искусственно создана блокированием сообщения с вытекающим отсюда усложнением алгоритма кодирования.