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

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

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

Как правило, превосходит [[алгоритм Хаффмана]] по эффективности сжатия, позволяет сжимать данные с [[Информационная энтропия|энтропией]], меньшей 1 бита на кодируемый символ, но некоторые версии имеют патентные ограничения от компании [[IBM]].<ref>[http://www.compression.ru/arctest/descript/comp-hist.htm История развития теории сжатия информации] / Compression.ru, Sarmin Alexey, 10 марта 2011 </ref>

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

В отличие от [[алгоритм Хаффмана|алгоритма Хаффмана]], метод арифметического кодирования показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов. Однако в случае равновероятного распределения символов, например, для строки бит ''010101…0101'' длины ''s'' метод арифметического кодирования приближается к префиксному коду Хаффмана и даже может занимать на один бит больше.<ref>[http://www.drdobbs.com/dr-dobbs-data-compression-newsletter/184404644 Dr. Dobb's Data Compression Newsletter], August 13, 2001</ref>

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

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

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

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

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

Используя метод арифметического кодирования, можно достичь почти оптимального представления для заданного набора символов и их вероятностей (согласно [[source coding theorem|теории энтропийного кодирования источника Шеннона]] оптимальное представление будет стремиться к числу −log''<sub>2</sub>P'' бит на каждый символ, вероятность которого ''P''). Алгоритмы сжатия данных, использующие в своей работе метод арифметического кодирования, перед непосредственным кодированием формируют [[модель]] входных данных на основании количественных или статистических характеристик, а также, найденных в кодируемой последовательности повторений или паттернов — любой дополнительной информации, позволяющей уточнить вероятность появления символа ''P'' в процессе кодирования. Очевидно, что чем точнее определена или предсказана вероятность символа, тем выше эффективность сжатия.

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

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

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

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

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

NEUTRAL POSITIVE NEGATIVE END-OF-DATA

Сначала разобьём отрезок от 0 до 1 согласно частотам сигналов. Разбивать отрезок будем в порядке, указанном выше: NEUTRAL — от 0 до 0,6; POSITIVE — от 0,6 до 0,8; NEGATIVE — от 0,8 до 0,9; END-OF-DATA — от 0,9 до 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.

=== Декодирование сообщения ===
[[Файл:Arithmetic encoding.svg|400px|thumb|right|На диаграмме представлено декодирование итогового интервального значения 0,538 согласно модели в приведённом примере. Область интервала разбивается на подинтервальные области согласно вероятностным характеристикам появления соответствующих символов. Затем, очередной выбранный интервал разбивается аналогичным способом.]]

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

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

<!-- закомментировано под перевод

We start, as the encoder did, with the interval <nowiki>[0,1)</nowiki>, and using the same model, we divide it into the same four sub-intervals that the encoder must have. Our fraction 0.538 falls into the sub-interval for NEUTRAL, <nowiki>[0, 0.6)</nowiki>; this indicates to us that the first symbol the encoder read must have been NEUTRAL, so we can write that down as the first symbol of our message.

We then divide the interval <nowiki>[0, 0.6)</nowiki> into sub-intervals:
* the interval for NEUTRAL would be <nowiki>[0, 0.36)</nowiki> ''-- 60 % of <nowiki>[0, 0.6)</nowiki>''
* the interval for POSITIVE would be <nowiki>[0.36, 0.48)</nowiki> ''-- 20 % of <nowiki>[0, 0.6)</nowiki>''
* the interval for NEGATIVE would be <nowiki>[0.48, 0.54)</nowiki> ''-- 10 % of <nowiki>[0, 0.6)</nowiki>''
* the interval for END-OF-DATA would be <nowiki>[0.54, 0.6)</nowiki>. ''-- 10 % of <nowiki>[0, 0.6)</nowiki>''

Our fraction of .538 is within the interval <nowiki>[0.48, 0.54)</nowiki>; therefore the second symbol of the message must have been NEGATIVE.
 
Once more we divide our current interval into sub-intervals:
* the interval for NEUTRAL would be <nowiki>[0.48, 0.516)</nowiki>
* the interval for POSITIVE would be <nowiki>[0.516, 0.528)</nowiki>
* the interval for NEGATIVE would be <nowiki>[0.528, 0.534)</nowiki>
* the interval for END-OF-DATA would be <nowiki>[0.534, 0.540)</nowiki>.

Our fraction of .538 falls within the interval of the END-OF-DATA symbol; therefore, this must be our next symbol. Since it is also the internal termination symbol, it means our decoding is complete. (If the stream was not internally terminated, we would need to know where the stream stops from some other source — otherwise, we would continue the decoding process forever, mistakenly reading more symbols from the fraction than were in fact encoded into it.)

The same message could have been encoded by the equally short fractions .534, .535, .536, .537 or .539. This suggests that our use of decimal instead of binary introduced some inefficiency. This is correct; the information content of a three-digit decimal is approximately 9.966 [[bit]]s; we could have encoded the same message in the binary fraction .10001010 (equivalent to .5390625 decimal) at a cost of only 8 bits. (Note that the final zero must be specified in the binary fraction, or else the message would be ambiguous without external information such as compressed stream size.)

This 8 bit output is larger than the information content, or [[information entropy|entropy]] of our message, which is 1.57 * 3 or 4.71 bits. The large difference between the example’s 8 (or 7 with external compressed data size information) bits of output and the entropy of 4.71 bits is caused by the short example message not being able to exercise the coder effectively. We claimed symbol probabilities of <nowiki>[.6, .2, .1, .1]</nowiki>, but the actual frequencies in this example are <nowiki>[.33, 0, .33 .33]</nowiki>. If the intervals are readjusted for these frequencies, the entropy of the message would be 1.58 bits and you could encode the same NEUTRAL NEGATIVE ENDOFDATA message as intervals <nowiki>[0, 1/3); [1/9, 2/9); [5/27, 6/27);</nowiki> and a binary interval of <nowiki>[1011110, 1110001)</nowiki>. This could yield an output message of 111, or just 3 bits. This is also an example of how statistical coding methods like arithmetic encoding can yield a size gain, especially if the probability model is off.

-->

== Примечания ==
{{примечания}}

== Ссылки ==
* [http://www.ddj.com/architect/184404644 (August 13, 2001) Dr. Dobb’s Data Compression Newsletter]

{{методы сжатия}}
{{перевести|en|Arithmetic Coding}}

[[Категория:Теория кодирования]]
[[Категория:Сжатие данных]]
[[Категория:Алгоритмы сжатия без потерь]]