Изменения

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

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

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

 

Обеспечивает лучшую степень сжатия чем [[алгоритм Хаффмана]]. То есть в соответсвии с [[теоремой Шеннона]] — -log₂(f) бит на цепочку.

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

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

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

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

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

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

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

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

 

Как только символы закончатся, выберем число из рабочего отрезка — это единственное число, которое требуется, чтобы закодировать последовательность чисел.

 

То же самое, но с оговоркой, что мы работаем и используем [[дискретные]] величины.