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

        2.2  Оптимальные методы статистического сжатия информации

 

         Оптимальными методами статистического кодирования сообщений, минимизирующими среднюю длину кода, являются статистические алгоритмы сжатия Шеннона-Фано и Хаффмана. Данные алгоритмы относятся к так называемым кодам без памяти.

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

 

 

2.2.1  Элементы теории префиксных множеств

 

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

         Если S={w₁, w₂, …, w_k} – префиксное множество, то можно определить некоторый вектор n(S)=(L₁, L₂, …, L_k), состоящий из значений длин соответствующих префиксных последовательностей.

         Вектор (L₁, L₂, …, L_k), состоящий из неуменьшающихся положительных целых чисел, называется вектором Крафта. Для него выполняется неравенство

 

                      ,                               (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={x₁, x₂, …, x_n} с алфавитом A объемом k.

         Обозначим как F=(F₁, F₂, …, F_k) вектор частот символов алфавита A, встречающихся в сообщении X.

         Кодирование кодом без памяти происходит следующим образом:

1)       составляется список символов алфавита A: a₁, a₂, …, a_s, …, a_k в порядке убывания их частот появления в X;

2)    каждому символу a_j назначается кодовое слово w_j из префиксного множества двоичных последовательностей S, для которого вектор Крафта (L₁, L₂, …, L_k);

3)    выход кодера получают объединением в одну последовательность всех полученных двоичных слов.

         Тогда длина кодовой последовательности на выходе кодера источника составит

 

                  L(X)=L×F=L₁×F₁+ L₂×F₂+…+ L_k×F_k.                        (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 и т.д. На практике такая ситуация встречается редко или может быть искусственно создана блокированием сообщения с вытекающим отсюда усложнением алгоритма кодирования.    

 

 

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Схожі підручники

• Одураченные случайностью
• Ауторегуляция мозгового кровообращения
• Зловживання довірою як спосіб вчинення злочину поняття і кримінально-правове значення
• Письма баламута
• Правоведение
• Організація і тактика слідчих дій при затриманні