Повышение эффективности кодирования. Блочное кодирование.

 

 

Повысить эффективность кодирования можно, строя код не для символа, а для блоков из n символов, причем частота блока рассчитывается как произведение частот символов, входящих в блок. Рассмотрим этот тезис на примере.

Пример 1. Даны символы a и b с частотами, соответственно, 0,9 и 0,1. Построить эффективный код методом Шеннона-Фано для блоков из двух символов (n = 2).

Сформируем список возможных блоков и их частот. При этом частоту блока будем рассчитывать как произведение частот символов, входящих в блок. Тогда имеем:

 

Блоки исходных Частоты блоков

символов

aa                                    0,81

ab                                    0,09

ba                                    0,09

bb                                    0,01

 

Построение кода сведём в таблицу:

 

Блоки           Частоты блоков                                Этапы построения кода

исходных     первый второй третий

символов

 

aa                          0,81  1                                 код построен

 

ab                         0,09  0    1                       код построен

 

ba                         0,09  0   0      1

 

bb                         0,01  0   0         0

 

Таким образом, получены коды:

aa – 1; ab - 01; ba - 001; bb - 000.

 

Определим эффективность построенного кода. Для этого рассчитаем сначала показатель эффективности для блока символов:

 

Iср ^блока = 0,81⋅1 + 0,09⋅2 + 0,09⋅3 + 0,01⋅3 = 1,28.

 

Поскольку в блоке 2 символа (n=2), для одного символа

      

I ср =Iср^блока /2 = 1,28/2 = 0,64.

 

При посимвольном кодировании для эффективного кода потребуется по одному двоичному разряду. В самом деле, применение метода Шеннона-Фано даёт результат, представленный в таблице:

 

Исходные    Частоты          Построение

символы         символов     кода

 

 a                           0,9    1

 b                                0,1    0

 

Таким образом, при блочном кодировании выигрыш составил 1 - 0,64 = 0,36 двоичных разрядов на один кодируемый символ в среднем.

Эффективность блочного кодирования тем выше, чем больше символов включается в блок

Особенностью эффективных кодов является переменное число двоичных разрядов получаемых кодовых комбинациях. Это затрудняет процесс декодирования.

Арифметическое кодирование

Пpи аpифметическом кодиpовании, в отличие от рассмотренных нами методов, когда кодируемый символ (или группа символов) заменяется соответствующим им кодом, результат кодирования всего сообщения пpедставляется одним или парой вещественных чисел в интеpвале от 0 до 1. По меpе кодиpования исходного текста отобpажающий его интеpвал уменьшается, а количество десятичных (или двоичных) разрядов, служащих для его пpедставления, возpастает. Очеpедные символы входного текста сокpащают величину интеpвала исходя из значений их веpоятностей, определяемых моделью. Более веpоятные символы делают это в меньшей степени, чем менее веpоятные, и, следовательно, добавляют меньше разрядов к pезультату.

 

Алгоритм арифметического кодирования

Арифметическое сжатие - достаточно изящный метод, в основе которого лежит очень простая идея. Мы представляем кодируемый текст в виде дроби, при этом строим дробь таким образом, чтобы наш текст был представлен как можно компактнее.

Для примера рассмотрим построение такой дроби на интервале [0, 1) (0 - включается, 1 - нет). Интервал [0, 1) выбран потому, что он удобен для объяснений. Мы разбиваем его на подынтервалы с длинами, равными вероятностям появления символов в потоке. В дальнейшем будем называть их диапазонами соответствующих символов.

Пусть мы сжимаем текст "КОВ.КОРОВА" (что, очевидно, означает "коварная корова"). Распишем вероятности появления каждого символа в тексте (в порядке убывания) и соответствующие этим символам диапазоны:

Символ	Частота	Вероятность	Диапазон
О	3	0.3	[0.0; 0.3)
К	2	0.2	[0.3; 0.5)
В	2	0.2	[0.5; 0.7)
Р	1	0.1	[0.7; 0.8)
А	1	0.1	[0.8; 0.9)
“.”	1	0.1	[0.9; 1.0)

 

Будем считать, что эта таблица известна в компрессоре и декомпрессоре. Кодирование заключается в уменьшении рабочего интервала. Для первого символа в качестве рабочего интервала берется [0, 1). Мы разбиваем его на диапазоны в соответствии с заданными частотами символов (см. таблицу диапазонов). В качестве следующего рабочего интервала берется диапазон, соответствующий текущему кодируемому символу. Его длина пропорциональна вероятности появления этого символа в потоке. Далее считываем следующий символ. В качестве исходного берем рабочий интервал, полученный на предыдущем шаге, и опять разбиваем его в соответствии с таблицей диапазонов. Длина рабочего интервала уменьшается пропорционально вероятности текущего символа, а точка начала сдвигается вправо пропорционально началу диапазона для этого символа. Новый построенный диапазон берется в качестве рабочего и т. д.

Используя исходную таблицу диапазонов, кодируем текст "КОВ.КОРОВА":

Исходный рабочий интервал [0,1).

Символ "К" [0.3; 0.5) получаем [0.3000; 0.5000).

Символ "О" [0.0; 0.3) получаем [0.3000; 0.3600).

Символ "В" [0.5; 0.7) получаем [0.3300; 0.3420).

Символ "." [0.9; 1.0) получаем [0,3408; 0.3420).

Графический процесс кодирования первых трех символов можно представить так, как на рис. 4.

Рис. 4. Графический процесс кодирования первых трех символов

 

Таким образом, окончательная длина интервала равна произведению вероятностей всех встретившихся символов, а его начало зависит от порядка следования символов в потоке. Можно обозначить диапазон символа с как [а[с]; b[с]), а интервал для i-го кодируемого символа потока как [l_i, h_i).

Большой вертикальной чертой на рисунке выше обозначено произвольное число, лежащее в полученном при работе интервале [/_i, h_i). Для последовательности "КОВ.", состоящей из четырех символов, за такое число можно взять 0.341. Этого числа достаточно для восстановления исходной цепочки, если известна исходная таблица диапазонов и длина цепочки.

Рассмотрим работу алгоритма восстановления цепочки. Каждый следующий интервал вложен в предыдущий. Это означает, что если есть число 0.341, то первым символом в цепочке может быть только "К", поскольку только его диапазон включает это число. В качестве интервала берется диапазон "К" - [0.3; 0.5) и в нем находится диапазон [а[с]; b[с]), включающий 0.341. Перебором всех возможных символов по приведенной выше таблице находим, что только интервал [0.3; 0.36), соответствующий диапазону для "О", включает число 0.341. Этот интервал выбирается в качестве следующего рабочего и т. д.