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

Арифметическое кодирование — один из алгоритмов энтропийного сжатия.

В отличие от алгоритма Хаффмана, не имеет жесткого постоянного соответствия входных символов группам бит выходного потока. Это даёт алгоритму большую гибкость в представлении дробных частот встречаемости символов.

Как правило, превосходит алгоритм Хаффмана по эффективности сжатия, позволяет сжимать данные с энтропией, меньшей 1 бита на кодируемый символ, но некоторые версии имеют патентные ограничения от компании IBM.

Характеристики

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

В отличие от алгоритма Хаффмана, метод арифметического кодирования показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов. Однако в случае равновероятного распределения символов, например для строки бит 010101…0101 длины s метод арифметического кодирования приближается к префиксному коду Хаффмана и даже может занимать на один бит больше.[www.ddj.com/architect/184404644]

Принцип действия

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

Назовём этот отрезок рабочим. Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа, и каждый такой отрезок будет соответствовать одному символу.

Теперь возьмём символ из потока и найдём для него отрезок среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.

Пример работы метода арифметического кодирования

Вероятностная модель

Используя метод арифметического кодирования, можно достичь почти оптимального представления для заданного набора символов и их вероятностей (согласно теории энтропийного кодирования источника Шеннона оптимальное представление будет стремиться к числу −log₂P бит на каждый символ, вероятность которого P). Алгоритмы сжатия данных, использующие в своей работе метод арифметического кодирования, перед непосредственным кодированием формируют модель входных данных на основании количественных или статистических характеристик, а также, найденных в кодируемой последовательности повторений или паттернов — любой дополнительной информации, позволяющей уточнить вероятность появления символа P в процессе кодирования. Очевидно, что чем точнее определена или предсказана вероятность символа, тем выше эффективность сжатия.

Рассмотрим простейший случай статической модели для кодирования информации, поступающей с системы обработки сигнала. Типы сигналов и соответствующие им вероятности распределены следующим образом:

• 60 % вероятность нейтрального значения сигнала или NEUTRAL.
• 20 % вероятность положительного значения сигнала или POSITIVE.
• 10 % вероятность отрицательного значения сигнала или NEGATIVE.
• 10 % вероятность признака конца кодируемой последовательности или END-OF-DATA.

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

Следует также отметить, что в качестве алфавита вероятностной модели метода можно рассматривать любой набор символов, исходя из особенностей решаемой задачи. Более эвристические подходы, использующие основную схему метода арифметического кодирования, применяют динамические или адаптивные модели. Идея данных методов заключается в уточнении вероятности кодируемого символа за счёт учёта вероятности предшествующего или будущего контекста (то есть, вероятность появления кодируемого символа после определённого k-го числа символов слева или справа, где k — это порядок контекста).

Кодирование сообщения

Возьмём для примера следующую последовательность:

NEUTRAL NEGATIVE END-OF-DATA

Сначала разобьём отрезок от 0 до 1 согласно частотам сигналов. Разбивать отрезок будем в порядке, указанном выше.

Теперь начнём кодировать с первого символа. Первому символу — NEUTRAL соответствует отрезок от 0 до 0.6. Разобьём этот отрезок аналогично отрезку от 0 до 1.

Закодируем второй символ — NEGATIVE. На отрезке от 0 до 0.6 ему соответствует отрезок от 0.48 до 0.54. Разобьём этот отрезок аналогично отрезку от 0 до 1.

Закодируем третий символ — END-OF-DATA. На отрезке от 0.48 до 0.54 ему соответствует отрезок от 0.534 до 0.54.

Так как это был последний символ, то кодирование завершено. Закодированное сообщение — отрезок от 0.534 до 0.54 или любое число из него, например, 0.538.

Декодирование сообщения

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

Начальное состояние процесса декодирования совпадает с процессом кодирования и рассматривается интервал [0,1). На основании известной вероятностной модели дробное значение 0.538 попадает в интервал [0, 0.6). Это позволяет определить первый символ, который был выбран кодировщиком, поэтому его значение выводится как первый символ декодированного сообщения.

Ссылки

• [www.ddj.com/architect/184404644 (August 13, 2001) Dr. Dobb’s Data Compression Newsletter]

Отрывок, характеризующий Арифметическое кодирование

Как только адъютант сказал это, старый усатый офицер с счастливым лицом и блестящими глазами, подняв кверху саблю, прокричал: «Виват! – и, скомандовав уланам следовать за собой, дал шпоры лошади и подскакал к реке. Он злобно толкнул замявшуюся под собой лошадь и бухнулся в воду, направляясь вглубь к быстрине течения. Сотни уланов поскакали за ним. Было холодно и жутко на середине и на быстрине теченья. Уланы цеплялись друг за друга, сваливались с лошадей, лошади некоторые тонули, тонули и люди, остальные старались плыть кто на седле, кто держась за гриву. Они старались плыть вперед на ту сторону и, несмотря на то, что за полверсты была переправа, гордились тем, что они плывут и тонут в этой реке под взглядами человека, сидевшего на бревне и даже не смотревшего на то, что они делали. Когда вернувшийся адъютант, выбрав удобную минуту, позволил себе обратить внимание императора на преданность поляков к его особе, маленький человек в сером сюртуке встал и, подозвав к себе Бертье, стал ходить с ним взад и вперед по берегу, отдавая ему приказания и изредка недовольно взглядывая на тонувших улан, развлекавших его внимание.
Для него было не ново убеждение в том, что присутствие его на всех концах мира, от Африки до степей Московии, одинаково поражает и повергает людей в безумие самозабвения. Он велел подать себе лошадь и поехал в свою стоянку.
Человек сорок улан потонуло в реке, несмотря на высланные на помощь лодки. Большинство прибилось назад к этому берегу. Полковник и несколько человек переплыли реку и с трудом вылезли на тот берег. Но как только они вылезли в обшлепнувшемся на них, стекающем ручьями мокром платье, они закричали: «Виват!», восторженно глядя на то место, где стоял Наполеон, но где его уже не было, и в ту минуту считали себя счастливыми.
Ввечеру Наполеон между двумя распоряжениями – одно о том, чтобы как можно скорее доставить заготовленные фальшивые русские ассигнации для ввоза в Россию, и другое о том, чтобы расстрелять саксонца, в перехваченном письме которого найдены сведения о распоряжениях по французской армии, – сделал третье распоряжение – о причислении бросившегося без нужды в реку польского полковника к когорте чести (Legion d'honneur), которой Наполеон был главою.
Qnos vult perdere – dementat. [Кого хочет погубить – лишит разума (лат.) ]


Русский император между тем более месяца уже жил в Вильне, делая смотры и маневры. Ничто не было готово для войны, которой все ожидали и для приготовления к которой император приехал из Петербурга. Общего плана действий не было. Колебания о том, какой план из всех тех, которые предлагались, должен быть принят, только еще более усилились после месячного пребывания императора в главной квартире. В трех армиях был в каждой отдельный главнокомандующий, но общего начальника над всеми армиями не было, и император не принимал на себя этого звания.
Чем дольше жил император в Вильне, тем менее и менее готовились к войне, уставши ожидать ее. Все стремления людей, окружавших государя, казалось, были направлены только на то, чтобы заставлять государя, приятно проводя время, забыть о предстоящей войне.
После многих балов и праздников у польских магнатов, у придворных и у самого государя, в июне месяце одному из польских генерал адъютантов государя пришла мысль дать обед и бал государю от лица его генерал адъютантов. Мысль эта радостно была принята всеми. Государь изъявил согласие. Генерал адъютанты собрали по подписке деньги. Особа, которая наиболее могла быть приятна государю, была приглашена быть хозяйкой бала. Граф Бенигсен, помещик Виленской губернии, предложил свой загородный дом для этого праздника, и 13 июня был назначен обед, бал, катанье на лодках и фейерверк в Закрете, загородном доме графа Бенигсена.
В тот самый день, в который Наполеоном был отдан приказ о переходе через Неман и передовые войска его, оттеснив казаков, перешли через русскую границу, Александр проводил вечер на даче Бенигсена – на бале, даваемом генерал адъютантами.
Был веселый, блестящий праздник; знатоки дела говорили, что редко собиралось в одном месте столько красавиц. Графиня Безухова в числе других русских дам, приехавших за государем из Петербурга в Вильну, была на этом бале, затемняя своей тяжелой, так называемой русской красотой утонченных польских дам. Она была замечена, и государь удостоил ее танца.
Борис Друбецкой, en garcon (холостяком), как он говорил, оставив свою жену в Москве, был также на этом бале и, хотя не генерал адъютант, был участником на большую сумму в подписке для бала. Борис теперь был богатый человек, далеко ушедший в почестях, уже не искавший покровительства, а на ровной ноге стоявший с высшими из своих сверстников.
В двенадцать часов ночи еще танцевали. Элен, не имевшая достойного кавалера, сама предложила мазурку Борису. Они сидели в третьей паре. Борис, хладнокровно поглядывая на блестящие обнаженные плечи Элен, выступавшие из темного газового с золотом платья, рассказывал про старых знакомых и вместе с тем, незаметно для самого себя и для других, ни на секунду не переставал наблюдать государя, находившегося в той же зале. Государь не танцевал; он стоял в дверях и останавливал то тех, то других теми ласковыми словами, которые он один только умел говорить.
При начале мазурки Борис видел, что генерал адъютант Балашев, одно из ближайших лиц к государю, подошел к нему и непридворно остановился близко от государя, говорившего с польской дамой. Поговорив с дамой, государь взглянул вопросительно и, видно, поняв, что Балашев поступил так только потому, что на то были важные причины, слегка кивнул даме и обратился к Балашеву. Только что Балашев начал говорить, как удивление выразилось на лице государя. Он взял под руку Балашева и пошел с ним через залу, бессознательно для себя расчищая с обеих сторон сажени на три широкую дорогу сторонившихся перед ним. Борис заметил взволнованное лицо Аракчеева, в то время как государь пошел с Балашевым. Аракчеев, исподлобья глядя на государя и посапывая красным носом, выдвинулся из толпы, как бы ожидая, что государь обратится к нему. (Борис понял, что Аракчеев завидует Балашеву и недоволен тем, что какая то, очевидно, важная, новость не через него передана государю.)
Но государь с Балашевым прошли, не замечая Аракчеева, через выходную дверь в освещенный сад. Аракчеев, придерживая шпагу и злобно оглядываясь вокруг себя, прошел шагах в двадцати за ними.
Пока Борис продолжал делать фигуры мазурки, его не переставала мучить мысль о том, какую новость привез Балашев и каким бы образом узнать ее прежде других.
В фигуре, где ему надо было выбирать дам, шепнув Элен, что он хочет взять графиню Потоцкую, которая, кажется, вышла на балкон, он, скользя ногами по паркету, выбежал в выходную дверь в сад и, заметив входящего с Балашевым на террасу государя, приостановился. Государь с Балашевым направлялись к двери. Борис, заторопившись, как будто не успев отодвинуться, почтительно прижался к притолоке и нагнул голову.
Государь с волнением лично оскорбленного человека договаривал следующие слова:
– Без объявления войны вступить в Россию. Я помирюсь только тогда, когда ни одного вооруженного неприятеля не останется на моей земле, – сказал он. Как показалось Борису, государю приятно было высказать эти слова: он был доволен формой выражения своей мысли, но был недоволен тем, что Борис услыхал их.
– Чтоб никто ничего не знал! – прибавил государь, нахмурившись. Борис понял, что это относилось к нему, и, закрыв глаза, слегка наклонил голову. Государь опять вошел в залу и еще около получаса пробыл на бале.
Борис первый узнал известие о переходе французскими войсками Немана и благодаря этому имел случай показать некоторым важным лицам, что многое, скрытое от других, бывает ему известно, и через то имел случай подняться выше во мнении этих особ.

Неожиданное известие о переходе французами Немана было особенно неожиданно после месяца несбывавшегося ожидания, и на бале! Государь, в первую минуту получения известия, под влиянием возмущения и оскорбления, нашел то, сделавшееся потом знаменитым, изречение, которое самому понравилось ему и выражало вполне его чувства. Возвратившись домой с бала, государь в два часа ночи послал за секретарем Шишковым и велел написать приказ войскам и рескрипт к фельдмаршалу князю Салтыкову, в котором он непременно требовал, чтобы были помещены слова о том, что он не помирится до тех пор, пока хотя один вооруженный француз останется на русской земле.