Арифметическое кодирование для сжатия данных: различия между версиями

Базовая реализация арифметического кодирования, описанная выше, имеет две основные трудности: уменьшение текущего интервала требует использования арифметики высокой точности, а вывод не производится до тех пор, пока не будет прочитан весь файл. Наиболее простым решением обеих этих проблем является вывод каждого старшего бита, как только он становится известен, а затем удвоение длины текущего интервала таким образом, чтобы он отражал только неизвестную часть конечного интервала. Виттен, Нил и Клири [11] добавили остроумный механизм, предотвращающий чрезмерное сокращение текущего интервала, когда конечные точки близки к <math>\frac{1}{2}</math>, но расходятся с <math>\frac{1}{2}</math>. В этом случае следующий бит вывода еще не известен – но, каким бы он ни был, ''следующий за ним'' бит будет иметь противоположное значение; можно просто отслеживать этот факт и расширять текущий интервал симметрично относительно <math>\frac{1}{2}</math>. Эта процедура может повторяться любое количество раз, так что размер текущего интервала всегда будет строго больше <math>\frac{1}{4}</math>.

На практике арифметика может быть реализована путем хранения конечных точек текущего интервала в виде достаточно больших целых чисел, а не в виде чисел с плавающей точкой или точных рациональных чисел. Вместо того чтобы начинать с вещественного интервала [0, 1), начните с целочисленного интервала [0, N), где N неизменно является степенью 2. Процесс разбиения заключается в выборе непересекающихся целочисленных интервалов (длиной не менее 1) с длинами, примерно пропорциональными подсчитанным количествам.

Число возможных состояний (после применения процедуры расширения интервала) арифметического кодера, использующего целочисленный интервал [0, N), равно <math>3N^2/16</math>. Очевидным способом уменьшения числа состояний до такого, при котором использование таблиц поиска становится практичным, является уменьшение значения N. Двоичное квазиарифметическое кодирование приводит к незначительному увеличению длины кода по сравнению с чисто арифметическим кодированием.

'''а доля, на которую средняя длина кода, полученная квазиарифметическим кодером, превышает длину кода, полученную точным арифметическим кодером, составляет не более''' <math>\bigg( log_2 \; \frac{2}{e \; ln \; 2} \bigg) \frac{1}{log_2 \; N} + O \bigg( \frac{1}{(log_2 \; N)^2} \bigg) \approx \frac{0,0861}{log_2 \; N} + O \bigg( \frac{1}{(log_2 \; N)^2} \bigg).</math>

Технические проблемы, связанные с арифметическим кодированием, полностью решены. Оставшиеся нерешенными задачи связаны с моделированием – разложением входного набора данных на последовательность событий, причем набор событий, возможных в каждой точке набора данных, должен быть описан распределением вероятностей, пригодным для ввода в кодер. Вопросы моделирования полностью зависят от конкретного применения.