Изменения

{{cleanup-rewrite}}

{{cleanup-rewrite}}

Один из алгоритмов [[энтропийное сжатие|энтропийного сжатия]].

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

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

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

Немного превосходит [[алгоритм Хаффмана]] качеством сжатия, но некоторые версии имеют патентные ограничения от компании [[IBM]].

Немного превосходит [[алгоритм Хаффмана]] качеством сжатия, но некоторые версии имеют патентные ограничения от компании [[IBM]].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

*60% вероятность нейтрального значения сигнала или NEUTRAL

* 60 % вероятность нейтрального значения сигнала или NEUTRAL

*20% вероятность положительного значения сигнала или POSITIVE

* 20 % вероятность положительного значения сигнала или POSITIVE

*10% вероятность отрицательного значения сигнала или NEGATIVE

* 10 % вероятность отрицательного значения сигнала или NEGATIVE

*10% вероятность признака конца кодируемой последовательности или END-OF-DATA.

* 10 % вероятность признака конца кодируемой последовательности или END-OF-DATA.

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

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

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

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

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

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

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

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

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

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

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

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

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

Начальное состояние процесса декодирования совпадает с процессом кодирования и рассматривается интервал <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 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:

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 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 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 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>''

* 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.

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.

* the interval for END-OF-DATA would be <nowiki>[0.534, 0.540)</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.)

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.)

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.

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]

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

{{методы сжатия}}

{{методы сжатия}}