Изменения

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

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

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

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

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

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

Для описания алгоритма на некотором алфавите с данными о частотности использования символов используется отрезок <math>[0;1]</math>, называемый «рабочим», на котором располагаются точки таким образом, что длины образованных отрезков будут равны частоте использования символа, и каждый такой отрезок соответствует одному символу.

Для описания алгоритма на некотором алфавите с данными о частотности использования символов используется отрезок <math>[0;1]</math>, называемый «рабочим», на котором располагаются точки таким образом, что длины образованных отрезков будут равны частоте использования символа, и каждый такой отрезок соответствует одному символу.

Для символа из потока выбирается соответствующий ему отрезок, после чего он становится рабочим отрезокм. Далее отрезок разбивается его таким же образом, как был разбит <math>[0;1]</math>; операция выполняется для некоторого числа последовательных символов. Затем выбирается произвольное число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и считаются результатом арифметического кодирования использованных символов потока.

Для символа из потока выбирается соответствующий ему отрезок, после чего он становится рабочим отрезком. Далее отрезок разбивается его таким же образом, как был разбит <math>[0;1]</math>; операция выполняется для некоторого числа последовательных символов. Затем выбирается произвольное число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и считаются результатом арифметического кодирования использованных символов потока.

== Пример ==

== Пример ==