ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->        2.2  Оптимальные методы статистического сжатия информации

Теория информации

        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

1

0

0

0

0

0

0

0

 

1

0

0

0

0

0

0

 

 

1

0

0

0

0

0

 

 

 

1

0

0

0

0

 

 

 

 

1

0

0

0

 

 

 

 

 

1

0

0

 

 

 

 

 

 

1

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

åpi=1

åpili=1,815

Для такого кода средняя длина  (бит/сим).

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

 

         Обратим внимание, что для кодов Хаффмена и Шеннона-Фано среднее количество битов, приходящееся на одно элементарное сообщение, приближается к энтропии источника, однако не может быть её меньше.

         Такой вывод является следствием теоремы кодирования источника в отсутствии шума[2]:

любой источник дискретных сообщений  можно закодировать двоичной последовательностью при среднем количестве двоичных символов (битов) на одно элементарное сообщение сколь угодно близком к энтропии источника Н(Х), и невозможно добиться средней длины кода, меньшей, чем энтропия Н(Х).

         Практическое значение этой теоремы трудно переоценить – она устанавливает границы компактности представления информации, которых можно достичь при правильном ее кодировании.

         Недостатки алгоритмов Шеннона-Фано и Хаффмена:

1       Необходимость составления таблицы кодов для каждого типа сжимаемых данных. Данный недостаток несущественен, если сжимается русский или английский текст. Однако в общем случае, когда вероятность символов неизвестна, данные методы кодирования реализуются в два прохода: первый используется для сбора частот символов, оценки их вероятностей и составления кодовой таблицы, второй –  для сжатия.

2       Необходимость хранения (передачи) таблицы кодов вместе со сжатым сообщением, что снижает общий эффект сжатия.

3       Минимальная длина кодовых слов не может быть меньше 1 бита, тогда как энтропия сообщения может быть близка к нулю. В таком случае оптимальные методы сжатия оказываются существенно избыточными. Данный недостаток преодолевается применением алгоритма к блокам символов, рассматриваемым как единицы сообщения, однако при этом усложняется процедура кодирования/ декодирования, и значительно расширяется таблица кодов.

4       Средняя длина кода совпадает с энтропией (наилучший случай) только в случае, когда вероятности символов являются целыми отрицательными степенями двойки, т.е. 1/2, 1/4, 1/8, 1/16 и т.д. На практике такая ситуация встречается редко или может быть искусственно создана блокированием сообщения с вытекающим отсюда усложнением алгоритма кодирования.    

 

 

8