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

При ответе на данный вопрос необходимо объяснить понятие «арифметическое кодирование», сравнить его с другими известными вам способами кодирования и рассказать об алгоритме построения арифметического кода некоторого сообщения.

Арифметическое кодирование — один из алгоритмов энтропийного сжатия. Алгоритм арифметического кодирования обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ требуется почти H бит, где H — информационная энтропия источника.

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

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

Опишем принцип действия. Пусть у нас есть некий первичный алфавит, состоящий из трех символов: A = {a, b, !}, а также данные о частотности использования символов P = {0,3; 0,6; 0,1}. Последний символ рассматриваемого алфавита «!» не несет информационной нагрузки на само сообщение, а является признаком конца сообщения и может быть использован только для указания на завершение сообщения. Он необходим декодировщику для однозначного декодирования полученного сообщения. На практике вероятность его использования берут заведомо малой. Данный символ можно не использовать только в том случае, когда декодировщику точно известна длина кодируемого сообщения.

Пусть требуется закодировать сообщение S = «bab!». Рассмотрим на координатной прямой отрезок от 0 до 1. Назовём этот отрезок рабочим. Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа, и каждый такой отрезок будет соответствовать одному символу.

Первый символ сообщения S — символ «b». Ему соответствовала часть рабочего отрезка от 0,3 до 0,9. Теперь эта часть рабочего отрезка сама становится рабочим отрезком следующего этапа кодирования. Разобьём его таким образом чтобы соотношения длин получаемых отрезков соответствовало соотношению вероятностей использования символов — 3:6:1. Длина рассматриваемого рабочего отрезка d = 0,9 - 0,3 = 0,6. Разбиваем его на 10 равных частей (3 + 6 + 1 = 10) длиной 0,06 каждая. Три части (отрезок длиной 0,18) относим к рабочему отрезку буквы «a», шесть частей (отрезок длиной 0,36) — к рабочему отрезку буквы «b» и одну часть длиной 0,06 — к рабочему отрезку символа «!». Порядок следования рабочих отрезков должен соответствовать первоначальному. Получим следующую таблицу разбиения текущего рабочего отрезка:

Далее в сообщении S расположен символ «a». Сейчас ему соответствует отрезок [0,3; 0,48). Выбираем этот отрезок в качестве рабочего и, согласно алгоритму, проведем его деление на части (общая длина отрезка 0,18, значит длина 1/10 части будет 0,018, для буквы «а» нужно три таких части, для «b» - шесть, для «!» - одна часть):

На следующем этапе рабочим отрезком будет [0,354; 0,462) — именно он соответствует новой букве в сообщении S, букве «b». Длина отрезка d = 0,462 — 0,354 = 0,108. Разделяем его на 10 частей длиной 0,0108. Букве «а» будет соответствовать часть рассматриваемого рабочего отрезка длиной 3*0,0108 = 0,0324. Далее расположится часть рабочего отрезка буквы «b». Ее длина будет 6*0,0108 = 0,0648. Оставшаяся часть рабочего отрезка длиной 0,0108 отводится символу «!». Рассмотрим таблицу деления нового рабочего отрезка:

Заканчиваем сообщение символом «!». Его рабочий отрезок на данном этапе [0,4512; 0,462). Выберем любое число из рабочего отрезка, например число 0,46. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.

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

Рассмотрим как происходит декодирование сообщения. Декодировщик получает код сообщения 0,46. Ему известен первичный алфавит и вероятности использования его символов. Он разбивает рабочий отрезок [0; 1) на отрезки согласно вероятностям появления символов:

Полученный код принадлежит отрезку [0,3; 0,9) — это часть отрезка соответствующая букве «b». Значит первый символ закодированного сообщения это символ «b». Далее декодировщик рассматривает рабочий отрезок полученной буквы, делит его пропорционально известным вероятностям появления символов и определяет в какую часть нового рабочего отрезка попадает число 0,46 — код сообщения S.

Число 0,46 принадлежит той части рассматриваемого рабочего отрезка, которая соответствует букве «а». Это второй декодированный символ сообщения S.

Декодировщик продолжает указанное деление до тех пор, пока полученный код не попадет в рабочий отрезок символа «!», являющийся признаком конца сообщения.

Не нашли, что искали? Воспользуйтесь поиском по сайту: