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

Арифметическое кодирование ( AC ) — это форма энтропийного кодирования, используемая при сжатии данных без потерь . Обычно строка символов представляется с использованием фиксированного количества битов на символ, как в коде ASCII . Когда строка преобразуется в арифметическую кодировку, часто используемые символы будут храниться с меньшим количеством битов, а нечасто встречающиеся символы будут храниться с большим количеством битов, в результате чего в общей сложности будет использоваться меньше битов. Арифметическое кодирование отличается от других форм энтропийного кодирования, таких как кодирование Хаффмана , тем, что вместо разделения входных данных на составные символы и замены каждого кодом, арифметическое кодирование кодирует все сообщение в одно число, произвольной точности дробь q . где 0,0 ≤ q < 1,0 . Он представляет текущую информацию в виде диапазона, определяемого двумя числами. Недавнее семейство энтропийных кодеров, называемое асимметричными системами счисления, обеспечивает более быструю реализацию благодаря непосредственной работе с одним натуральным числом, представляющим текущую информацию.

Пример арифметического кодирования, предполагающий фиксированное распределение вероятностей трех символов «A», «B» и «C». Вероятность «А» составляет 50%, вероятность «Б» — 33% и вероятность «С» — 17%. Кроме того, мы предполагаем, что глубина рекурсии известна на каждом шаге. На первом этапе мы кодируем «B», который находится внутри интервала [0,5, 0,83): Двоичное число «0,10 x » — это самый короткий код, который представляет интервал, который полностью находится внутри [0,5, 0,83). « x » означает произвольную последовательность битов. Есть два крайних случая: наименьший x означает ноль, который представляет левую сторону представленного интервала. Тогда левая часть интервала равна dec(0,10) = 0,5. С другой стороны, x обозначает конечную последовательность единиц, которая имеет верхний предел dec(0,11) = 0,75. Следовательно, «0,10 x » представляет собой интервал [0,5, 0,75), который находится внутри [0,5, 0,83). Теперь мы можем опустить «0». часть, поскольку все интервалы начинаются с «0». и мы можем игнорировать часть « x », потому что независимо от того, какую битовую последовательность она представляет, мы останемся внутри [0,5, 0,75).

Детали реализации и примеры

Кодирование сообщения "ВИКИ" арифметическим кодированием

1.	Частоты букв найдены.
2.	Интервал [0, 1) разбивается на соотношение частот.
3–5.	Соответствующий интервал итеративно разбивается для каждой буквы сообщения.
6.	Любое значение в последнем интервале выбирается для представления сообщения.
2*–6*.	Разделение и значение, если вместо этого сообщение было «КИВИ».

Приведенный выше пример визуализируется в виде круга, значения, выделенные красным, кодируют «WIKI» и «KIWI» — на изображении SVG наведите указатель мыши на интервал, чтобы выделить его и отобразить его статистику.

Равные вероятности

В простейшем случае вероятность появления каждого символа одинакова. Например, рассмотрим набор из трех символов: A, B и C, каждый из которых встречается с равной вероятностью. Для кодирования символов по одному потребуется 2 бита на символ, что расточительно: ни один из вариантов битов никогда не используется. То есть символы A, B и C могут быть закодированы соответственно как 00, 01 и 10, причем 11 не используется.

Более эффективное решение — представить последовательность этих трех символов в виде рационального числа по основанию 3, где каждая цифра представляет символ. Например, последовательность «ABBCAB» может стать 0,011201 ₃ в арифметическом кодировании как значение в интервале [0, 1). Следующий шаг — закодировать это троичное число, используя двоичное число с фиксированной точкой достаточной точности для его восстановления, например 0,0010110001 ₂ — это всего 10 бит; 2 бита сохраняются по сравнению с простым блочным кодированием. Это возможно для длинных последовательностей, поскольку существуют эффективные алгоритмы преобразования базы произвольно точных чисел.

Чтобы декодировать значение, зная, что исходная строка имеет длину 6, можно просто преобразовать обратно в систему счисления с основанием 3, округлить до 6 цифр и восстановить строку.

Определение модели

В общем, арифметические кодеры могут выдавать почти оптимальный результат для любого заданного набора символов и вероятностей. (Оптимальное значение составляет −log ₂ P бит для каждого символа с вероятностью P ; см. Теорему об исходном кодировании .) Алгоритмы сжатия, использующие арифметическое кодирование, начинаются с определения модели данных – по сути, прогнозирования того, какие шаблоны будут найдены в символах. сообщения. Чем точнее этот прогноз, тем ближе к оптимальному будет результат.

Пример : простая статическая модель для описания результатов работы конкретного прибора мониторинга с течением времени может быть следующей:

• 60% вероятность появления символа НЕЙТРАЛЬНО
• 20% шанс выпадения символа ПОЗИТИВНЫЙ
• 10% шанс выпадения символа ОТРИЦАТЕЛЬНЫЙ
• 10% вероятность появления символа КОНЕЦ ДАННЫХ. (Наличие этого символа означает, что поток будет «внутренне завершен», что довольно часто встречается при сжатии данных; когда этот символ появляется в потоке данных, декодер будет знать, что весь поток был декодирован.)

Модели также могут обрабатывать алфавиты, отличные от простого набора из четырех символов, выбранного для этого примера. Возможны также более сложные модели: моделирование более высокого порядка меняет оценку текущей вероятности символа на основе символов, которые ему предшествуют ( контекст ), так что в модели для английского текста, например, процентная вероятность « u» будет намного выше, если оно следует за «Q» или «q». Модели могут даже быть адаптивными , то есть они постоянно меняют свои прогнозы данных в зависимости от того, что на самом деле содержит поток. Декодер должен иметь ту же модель, что и кодер.

Кодирование и декодирование: обзор

В общем, каждый шаг процесса кодирования, за исключением последнего, одинаков; кодировщику необходимо учитывать всего три фрагмента данных:

• Следующий символ, который необходимо закодировать
• Текущий интервал (в самом начале процесса кодирования интервал установлен на [0,1], но это изменится)
• Вероятности, которые модель присваивает каждому из различных символов, возможных на этом этапе (как упоминалось ранее, модели высшего порядка или адаптивные модели означают, что эти вероятности не обязательно одинаковы на каждом этапе).

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

Пример : для четырехсимвольной модели выше:

• интервал для НЕЙТРАЛЬНОГО значения будет [0, 0,6)
• интервал для ПОЛОЖИТЕЛЬНОГО будет [0,6, 0,8)
• интервал для ОТРИЦАТЕЛЬНОГО значения будет [0,8, 0,9)
• интервал для END-OF-DATA будет [0,9, 1).

Когда все символы закодированы, полученный интервал однозначно идентифицирует последовательность символов, которая его создала. Любой, у кого есть тот же конечный интервал и используемая модель, может восстановить последовательность символов, которая должна была войти в кодер, чтобы получить этот конечный интервал.

Однако нет необходимости передавать последний интервал; необходимо передать только одну часть , лежащую в этом интервале. В частности, необходимо только передать достаточно цифр (в любом основании) дроби, чтобы все дроби, начинающиеся с этих цифр, попали в конечный интервал; это гарантирует, что полученный код является префиксным кодом .

Кодирование и декодирование: пример

Диаграмма, показывающая декодирование 0,538 (круглая точка) в примере модели. Область разбивается на подобласти, пропорциональные частотам символов, затем таким же образом последовательно подразделяется подобласть, содержащая точку.

Рассмотрим процесс декодирования сообщения, закодированного с помощью данной четырехсимвольной модели. Сообщение кодируется дробью 0,538 (для ясности используется десятичная дробь вместо двоичной; также предполагается, что для декодирования сообщения имеется ровно столько цифр, сколько необходимо).

Процесс начинается с того же интервала, который используется кодировщиком: [0,1), и использует ту же модель, разделяя ее на те же четыре подинтервала, которые должен иметь кодер. Дробь 0,538 попадает в подинтервал НЕЙТРАЛЬНЫХ, [0, 0,6); это указывает на то, что первый символ, прочитанный кодером, должен быть НЕЙТРАЛЬНЫМ, поэтому это первый символ сообщения.

Затем разделите интервал [0, 0,6) на подинтервалы:

• интервал для НЕЙТРАЛЬНОГО значения будет [0, 0,36), 60% от [0, 0,6) .
• интервал для ПОЗИТИВА будет [0,36, 0,48), 20% от [0, 0,6) .
• интервал для ОТРИЦАТЕЛЬНОГО будет [0,48, 0,54), 10% от [0, 0,6) .
• интервал для END-OF-DATA будет [0,54, 0,6), 10% от [0, 0,6) .

Поскольку 0,538 находится в интервале [0,48, 0,54), второй символ сообщения должен быть ОТРИЦАТЕЛЬНЫМ.

Снова разделим наш текущий интервал на подинтервалы:

• интервал НЕЙТРАЛЬНОГО значения будет [0,48, 0,516).
• интервал для ПОЛОЖИТЕЛЬНОГО будет [0,516, 0,528).
• интервал для ОТРИЦАТЕЛЬНОГО значения будет [0,528, 0,534).
• интервал для END-OF-DATA будет [0,534, 0,540).

Теперь 0,538 попадает в интервал символа КОНЕЦ ДАННЫХ; следовательно, это должен быть следующий символ. Поскольку это также внутренний символ завершения, это означает, что декодирование завершено. Если поток не завершен внутренне, должен быть какой-то другой способ указать, где поток останавливается. В противном случае процесс декодирования мог бы продолжаться вечно, ошибочно считывая из дроби больше символов, чем было на самом деле в нее закодировано.

Источники неэффективности

Сообщение 0,538 в предыдущем примере могло быть закодировано одинаково короткими дробями 0,534, 0,535, 0,536, 0,537 или 0,539. Это говорит о том, что использование десятичной системы вместо двоичной приводит к некоторой неэффективности. Это правильно; информационное содержание трехзначной десятичной дроби равно $3\times \log _{2}(10)\approx 9.966$ биты ; то же самое сообщение могло быть закодировано в двоичной дроби 0,10001001 (эквивалентно 0,53515625 десятичной дроби) при стоимости всего 8 бит.

Этот 8-битный вывод превышает информационное содержание или энтропию сообщения, которое

$\sum -\log _{2}(p_{i})=-\log _{2}(0.6)-\log _{2}(0.1)-\log _{2}(0.1)=7.381{\text{ bits}}.$

Но в двоичном кодировании должно использоваться целое число бит, поэтому кодер для этого сообщения будет использовать как минимум 8 бит, в результате чего сообщение будет на 8,4% больше, чем энтропийное содержимое. Эта неэффективность, составляющая не более 1 бита, приводит к относительно меньшим накладным расходам по мере увеличения размера сообщения.

Причем заявленные вероятности символов были [0,6, 0,2, 0,1, 0,1), а реальные частоты в этом примере — [0,33, 0, 0,33, 0,33). Если интервалы перенастроены для этих частот, энтропия сообщения составит 4,755 бит, и то же самое сообщение NEUTRAL NEGATIVE END-OF-DATA может быть закодировано как интервалы [0, 1/3); [1/9, 2/9); [27 мая, 27 июня); и двоичный интервал [0,00101111011, 0,00111000111). Это также пример того, как методы статистического кодирования, такие как арифметическое кодирование, могут создавать выходное сообщение, превышающее входное сообщение, особенно если вероятностная модель отключена.

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

См. Также: Контекстно-адаптивное двоичное арифметическое кодирование.

Одним из преимуществ арифметического кодирования перед другими аналогичными методами сжатия данных является удобство адаптации. Адаптация – это изменение таблиц частот (или вероятностей) при обработке данных. Декодированные данные соответствуют исходным данным до тех пор, пока таблица частот при декодировании заменяется таким же образом и на том же этапе, что и при кодировании. Синхронизация обычно основана на сочетании символов, возникающих в процессе кодирования и декодирования.

Прецизионность и перенормировка

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

Символ	Вероятность	Интервал уменьшен до восьмибитной точности		Диапазон
	(выраженный в виде дроби)	(в виде дробей)	(в двоичном формате)	(в двоичном формате)
А	1/3	[0, 85/256)	[0.00000000, 0.01010101)	00000000 – 01010100
Б	1/3	[85/256, 171/256)	[0.01010101, 0.10101011)	01010101 – 10101010
С	1/3	[171/256, 1)	[0.10101011, 1.00000000)	10101011 – 11111111

Процесс, называемый перенормировкой, не позволяет конечной точности стать ограничением на общее количество символов, которые можно закодировать. Всякий раз, когда диапазон уменьшается до точки, в которой все значения в диапазоне имеют определенные начальные цифры, эти цифры отправляются на выход. обработать компьютер Сколько бы цифр точности ни мог , теперь он обрабатывает меньше, поэтому существующие цифры смещаются влево, а справа добавляются новые цифры, чтобы максимально расширить диапазон. Обратите внимание, что этот результат имеет место в двух из трех случаев из нашего предыдущего примера.

Символ	Вероятность	Диапазон	Цифры, которые можно отправить на вывод	Диапазон после перенормировки
А	1/3	0 0000000 – 0 1010100	0	0000000 0 – 1010100 1
Б	1/3	01010101 – 10101010	Никто	01010101 – 10101010
С	1/3	1 0101011 – 1 1111111	1	0101011 0 – 1111111 1

Арифметическое кодирование как обобщенная замена системы счисления

Напомним, что в случае, когда символы имели равные вероятности, арифметическое кодирование могло быть реализовано простой заменой системы счисления. В общем, арифметическое (и диапазонное) кодирование можно интерпретировать как обобщенное изменение системы счисления . Например, мы можем посмотреть на любую последовательность символов:

$\mathrm {DABDDB}$

как число в определенном основании, предполагая, что задействованные символы образуют упорядоченный набор, и каждый символ в упорядоченном наборе обозначает последовательное целое число A = 0, B = 1, C = 2, D = 3 и так далее. В результате получаются следующие частоты и совокупные частоты:

Символ	Частота встречаемости	Совокупная частота
А	1	0
Б	2	1
Д	3	3

Совокупная частота элемента — это сумма всех частот, предшествующих этому элементу. Другими словами, совокупная частота представляет собой промежуточную сумму частот.

В позиционной системе счисления система счисления или основание численно равна ряду различных символов, используемых для выражения числа. Например, в десятичной системе количество символов равно 10, а именно 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. Система счисления используется для выражения любого конечного целого числа в предполагаемом множителе в полиномиальная форма. Например, число 457 на самом деле равно 4×10. ²  + 5×10 ¹  + 7×10 ⁰ , где предполагается, что основание 10, но не указано явно.

Первоначально мы преобразуем DABDDB в число с основанием 6, поскольку 6 — это длина строки. Строка сначала преобразуется в цифровую строку 301331, которая затем преобразуется в целое число с помощью полинома:

$6^{5}\times 3+6^{4}\times 0+6^{3}\times 1+6^{2}\times 3+6^{1}\times 3+6^{0}\times 1=23671$

Результат 23671 имеет длину 15 бит, что не очень близко к теоретическому пределу (энтропии сообщения ), составляющему примерно 9 бит.

Чтобы закодировать сообщение с длиной, близкой к теоретическому пределу, налагаемому теорией информации, нам нужно немного обобщить классическую формулу изменения системы счисления. Мы вычислим нижнюю и верхнюю границы L и U и выберем число между ними. Для вычисления L мы умножаем каждый член в приведенном выше выражении на произведение частот всех ранее встречавшихся символов:

${\begin{aligned}L={}&(6^{5}\times 3)+{}\\&3\times (6^{4}\times 0)+{}\\&(3\times 1)\times (6^{3}\times 1)+{}\\&(3\times 1\times 2)\times (6^{2}\times 3)+{}\\&(3\times 1\times 2\times 3)\times (6^{1}\times 3)+{}\\&(3\times 1\times 2\times 3\times 3)\times (6^{0}\times 1){}\\={}&25002\end{aligned}}$

Разница между этим полиномом и полиномом выше заключается в том, что каждый член умножается на произведение частот всех ранее встречавшихся символов. В более общем смысле L можно вычислить как:

$L=\sum _{i=1}^{n}n^{n-i}C_{i}{\prod _{k=1}^{i-1}f_{k}}$

где $\scriptstyle C_{i}$ являются совокупными частотами и $\scriptstyle f_{k}$ являются частотами возникновения. Индексы обозначают положение символа в сообщении. В частном случае, когда все частоты $\scriptstyle f_{k}$ равны 1, это формула замены базы.

Верхняя граница U будет равна L плюс произведение всех частот; в этом случае U = L + (3 × 1 × 2 × 3 × 3 × 2) = 25002 + 108 = 25110. В общем, U определяется формулой:

$U=L+\prod _{k=1}^{n}f_{k}$

Теперь мы можем выбрать любое число из интервала [ L , U ) для представления сообщения; Одним из удобных вариантов является значение с максимально длинным следом нулей, 25100, поскольку оно позволяет нам добиться сжатия, представляя результат как 251×10. ² . Нули также можно обрезать, получив 251, если длина сообщения хранится отдельно. Более длинные сообщения будут иметь более длинные следы нулей.

Чтобы декодировать целое число 25100, полиномиальное вычисление можно обратить вспять, как показано в таблице ниже. На каждом этапе идентифицируется текущий символ, затем из результата вычитается соответствующий член.

Остаток	Идентификация	Идентифицированный символ	Исправленный остаток
25100	25100 / 6 5 = 3	Д	(25100 − 6 5 × 3) / 3 = 590
590	590 / 6 4 = 0	А	(590 − 6 4 × 0) / 1 = 590
590	590 / 6 3 = 2	Б	(590 − 6 3 × 1) / 2 = 187
187	187 / 6 2 = 5	Д	(187 − 6 2 × 3) / 3 = 26
26	26 / 6 1 = 4	Д	(26 − 6 1 × 3) / 3 = 2
2	2 / 6 0 = 2	Б	—

Во время декодирования мы берем слово после деления на соответствующую степень 6. Затем результат сопоставляется с совокупными интервалами, и соответствующий символ выбирается из справочной таблицы. Когда символ идентифицирован, результат корректируется. Процесс продолжается в течение известной длины сообщения или до тех пор, пока оставшийся результат будет положительным. Единственное отличие от классической смены базы состоит в том, что с каждым символом может быть связан диапазон значений. В этом примере A всегда равно 0, B — либо 1, либо 2, а D — любое из 3, 4, 5. Это в точном соответствии с нашими интервалами, определяемыми частотами. Когда все интервалы равны 1, мы имеем частный случай классической замены базы.

Теоретический предел сжатого сообщения

Нижняя граница L никогда не превышает n ^н , где n — размер сообщения, поэтому его можно представить в виде $\log _{2}(n^{n})=n\log _{2}(n)$ биты. После вычисления верхней границы U и сокращения сообщения путем выбора числа из интервала [ L , U ) с самым длинным следом из нулей мы можем предположить, что эту длину можно уменьшить на $\textstyle \log _{2}\left(\prod _{k=1}^{n}f_{k}\right)$ биты. Поскольку каждая частота в произведении встречается ровно столько же раз, сколько и значение этой частоты, мы можем использовать размер алфавита A для вычисления произведения.

$\prod _{k=1}^{n}f_{k}=\prod _{k=1}^{A}f_{k}^{f_{k}}.$

Применяя log ₂ для предполагаемого количества битов в сообщении, окончательное сообщение (не считая логарифмических накладных расходов для таблиц длины сообщения и частоты) будет соответствовать количеству битов, заданному энтропией , что для длинных сообщений очень близко к оптимальному:

$-\left[\sum _{i=1}^{A}f_{i}\log _{2}(f_{i})\right]n=nH$

Другими словами, эффективность арифметического кодирования приближается к теоретическому пределу $H$ бит на символ, поскольку длина сообщения приближается к бесконечности.

Асимптотическое равнораспределение

Мы можем понять это интуитивно. Предположим, что источник эргодичен, тогда он обладает свойством асимптотического равнораспределения (СЭП). AEP, после долгого потока $n$ символы, интервал $(0,1)$ практически разбит на интервалы почти одинакового размера.

Технически, для любого маленького $\epsilon >0$, для всех достаточно больших $n$, существует $2^{nH(X)(1+O(\epsilon ))}$ струны $x_{1:n}$, так что каждая строка имеет почти равную вероятность $Pr(x_{1:n})=2^{-nH(X)(1+O(\epsilon ))}$, а их общая вероятность равна $1-O(\epsilon )$.

Любая такая строка арифметически кодируется двоичной строкой длины $k$, где $k$ самый маленький $k$ такая, что существует дробь вида ${\frac {?}{2^{k}}}$ в интервале для $x_{1:n}$. Поскольку интервал для $x_{1:n}$ имеет размер $2^{-nH(X)(1+O(\epsilon ))}$, мы должны ожидать, что он будет содержать одну часть формы ${\frac {?}{2^{k}}}$ когда $k=nH(X)(1+O(\epsilon ))$.

Таким образом, с большой вероятностью $x_{1:n}$ может быть арифметически закодировано двоичной строкой длины $nH(X)(1+O(\epsilon ))$.

Связи с другими методами сжатия

Кодирование Хаффмана

Основная статья: Кодирование Хаффмана

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

При наивном кодировании двоичных строк по методу Хаффмана сжатие невозможно, даже если энтропия мала (например, ({0, 1}) имеет вероятности {0,95, 0,05}). При кодировании Хаффмана каждому значению присваивается 1 бит, в результате чего получается код той же длины, что и входное значение. Напротив, арифметическое кодирование хорошо сжимает биты, приближаясь к оптимальному коэффициенту сжатия.

$1-[-0.95\log _{2}(0.95)+-0.05\log _{2}(0.05)]\approx 71.4\%.$

Одним из простых способов решения проблемы неоптимальности кодирования Хаффмана является объединение символов («блокирование») для формирования нового алфавита, в котором каждый новый символ представляет собой последовательность исходных символов – в данном случае битов – из исходного алфавита. В приведенном выше примере группировка последовательностей из трех символов перед кодированием приведет к созданию новых «суперсимволов» со следующими частотами:

• 000 : 85.7%
• 001 , 010 , 100 : 4,5% каждый
• 011 , 101 , 110 : 0,24% каждый
• 111 : 0.0125%

При такой группировке кодирование Хаффмана в среднем составляет 1,3 бита на каждые три символа, или 0,433 бита на символ, по сравнению с одним битом на символ в исходном кодировании, т.е. $56.7\%$ сжатие. Разрешение произвольно больших последовательностей становится сколь угодно близким к энтропии – точно так же, как арифметическое кодирование – но для этого требуются огромные коды, поэтому это не так практично, как арифметическое кодирование для этой цели.

Альтернативой является кодирование длин серий на основе Хаффмана с помощью кодов Голомба-Райса . Такой подход обеспечивает более простое и быстрое кодирование/декодирование, чем арифметическое кодирование или даже кодирование Хаффмана, поскольку последнее требует поиска в таблице. В примере {0,95, 0,05} код Голомба-Райса с четырехбитным остатком достигает степени сжатия $71.1\%$, что гораздо ближе к оптимальному, чем при использовании трехбитных блоков. Однако коды Голомба-Райса применяются только к входным данным Бернулли, таким как тот, что показан в этом примере, поэтому они не заменяют блокировку во всех случаях.

История и патенты

Базовые алгоритмы арифметического кодирования были независимо разработаны Йормой Дж. Риссаненом из IBM Research и Ричардом К. Паско, доктором философии. студент Стэнфордского университета ; обе были опубликованы в мае 1976 года. Паско цитирует предварительный вариант статьи Риссанена и комментирует взаимосвязь между их работами:

Один алгоритм семейства был независимо разработан Риссаненом [1976]. Он перемещает элемент кода к самому значимому концу аккумулятора, используя указатель, полученный путем сложения и возведения в степень. Теперь мы сравним альтернативы в трех вариантах и ​​увидим, что предпочтительнее сдвинуть элемент кода, а не аккумулятор, и добавить элементы кода к наименее значимому концу аккумулятора.

Менее чем через год после публикации IBM подала заявку на патент США на работу Риссанена. Работа Паско не была запатентована.

Множество конкретных методов арифметического кодирования исторически были защищены патентами США, хотя различные хорошо известные методы с тех пор перешли в общественное достояние, поскольку срок действия патентов истек. Методы, защищенные патентами, могут оказаться важными для реализации алгоритмов арифметического кодирования, указанных в некоторых официальных международных стандартах. В этом случае такие патенты обычно доступны для лицензирования на так называемых «разумных и недискриминационных» ( RAND ) условиях лицензирования (по крайней мере, в соответствии с политикой комитета по стандартам). В некоторых хорошо известных случаях (в том числе связанных с патентами IBM, срок действия которых уже истек) такие лицензии были доступны бесплатно, а в других случаях требовалась лицензионная плата. Наличие лицензий на условиях RAND не обязательно удовлетворит всех, кто захочет использовать эту технологию, поскольку то, что может показаться «разумным» для компании, готовящей проприетарный коммерческий программный продукт, может показаться гораздо менее разумным для бесплатное программное обеспечение или с открытым исходным кодом проект .

По крайней мере, одна значительная программа сжатия, bzip2 , намеренно отказалась от использования арифметического кодирования в пользу кодирования Хаффмана из-за предполагаемой в то время ситуации с патентами. Кроме того, кодеры и декодеры формата файлов JPEG , в которых есть опции как для кодирования Хаффмана, так и для арифметического кодирования, обычно поддерживают только вариант кодирования Хаффмана, что изначально было предусмотрено из-за проблем с патентами; в результате почти все изображения JPEG, используемые сегодня, используют кодировку Хаффмана. хотя патенты JPEG на арифметическое кодирование истекли из-за устаревания стандарта JPEG (разработка которого была примерно завершена к 1990 году). JPEG XL , а также архиваторы, такие как PackJPG, Brunsli и Lepton, которые могут без потерь конвертировать файлы в кодировке Хаффмана в файлы с арифметическим кодированием (или асимметричной системой счисления в случае JPEG XL), демонстрируя экономию размера до 25%.

JPEG Алгоритм арифметического кодирования формата сжатия изображений основан на следующих цитируемых патентах (с истекшим сроком действия).

• Патент США 4652856 - ( IBM ) подан 4 февраля 1986 г., выдан 24 марта 1987 г. - Коттаппурам М.А. Мохиуддин, Йорма Йоханнес Риссанен - ​​Многоалфавитный арифметический код без умножения.
• Патент США 4 905 297 - (IBM) подан 18 ноября 1988 г., выдан 27 февраля 1990 г. - Глен Джордж Лэнгдон, Джоан Л. Митчелл, Уильям Б. Пеннебейкер, Йорма Йоханнес Риссанен - ​​Система арифметического кодирования и декодера.
• Патент США 4 935 882 - (IBM) подан 20 июля 1988 г., выдан 19 июня 1990 г. - Уильям Б. Пеннебейкер, Джоан Л. Митчелл - Вероятностная адаптация для арифметических кодировщиков.
• Патент JP 1021672 - ( Mitsubishi ) подан 21 января 1989 г., выдан 10 августа 1990 г. - Тошихиро Кимура, Сигенори Кино, Фумитака Оно, Масаюки Ёсида - Система кодирования.
• Патент JP 2-46275 - (Mitsubishi) подан 26 февраля 1990 г., выдан 5 ноября 1991 г. - Фумитака Оно, Томохиро Кимура, Масаюки Ёсида, Сигенори Кино - Устройство кодирования и метод кодирования.

Другие патенты (в основном также с истекшим сроком действия), связанные с арифметическим кодированием, включают следующие.

• Патент США 4 122 440 - (IBM) подан 4 марта 1977 г., выдан 24 октября 1978 г. - Глен Джордж Лэнгдон, Йорма Йоханнес Риссанен - ​​Метод и средства кодирования арифметических строк.
• Патент США 4 286 256 - (IBM) подан 28 ноября 1979 г., выдан 25 августа 1981 г. - Глен Джордж Лэнгдон, Йорма Йоханнес Риссанен - ​​Метод и средства арифметического кодирования с использованием уменьшенного количества операций.
• Патент США 4 467 317 - (IBM) подан 30 марта 1981 г., выдан 21 августа 1984 г. - Глен Джордж Лэнгдон, Йорма Йоханнес Риссанен - ​​Высокоскоростное арифметическое сжатое кодирование с использованием одновременного обновления значений.
• Патент США 4 891 643 - (IBM) подан 15 сентября 1986 г., выдан 2 января 1990 г. - Джоан Л. Митчелл, Уильям Б. Пеннебейкер - Сжатие / распаковка данных арифметического кодирования с помощью выборочно используемых различных кодеров и декодеров арифметического кодирования.
• Патент JP 11782787 - ( NEC ) подан 13 мая 1987 г., выдан 18 ноября 1988 г. - Мичио Симада - Устройство арифметического кодирования со сжатием данных.
• Патент JP 15015487 - ( KDDI ) подан 18 июня 1987 г., выдан 22 декабря 1988 г. - Шуичи Мацумото, Масахиро Сайто - Система предотвращения распространения переноса при арифметическом кодировании.
• Патент США 4 933 883 - (IBM) подан 3 мая 1988 г., выдан 12 июня 1990 г. - Уильям Б. Пеннебейкер, Джоан Л. Митчелл - Вероятностная адаптация для арифметических кодировщиков.
• Патент США 4 989 000 - (IBM) подан 19 июня 1989 г., выдан 29 января 1991 г. - Дэн С. Шевион, Эхуд Д. Карнин, Эугениуш Валах - Сжатие строк данных с использованием арифметического кодирования с упрощенной оценкой подинтервала вероятности.
• Патент США 5 099 440 - (IBM) подан 5 января 1990 г., выдан 24 марта 1992 г. - Уильям Б. Пеннебейкер, Джоан Л. Митчелл - Вероятностная адаптация для арифметических кодировщиков.
• Патент США 5 272 478 - ( Ricoh ) подан 17 августа 1992 г., выдан 21 декабря 1993 г. - Джеймс Д. Аллен - Метод и устройство для энтропийного кодирования.

Примечание. Этот список не является исчерпывающим. См. следующие ссылки для получения списка других патентов США. Кодек Дирака использует арифметическое кодирование и не запатентован.

Патенты на арифметическое кодирование могут существовать в других юрисдикциях; см. патенты на программное обеспечение , где обсуждается патентоспособность программного обеспечения во всем мире.

Бенчмарки и другие технические характеристики

Каждая программная реализация арифметического кодирования имеет различную степень сжатия и производительность. Хотя степень сжатия варьируется лишь незначительно (обычно менее 1%), время выполнения кода может варьироваться в 10 раз. Выбор подходящего кодировщика из списка общедоступных кодировщиков — непростая задача, поскольку производительность и степень сжатия зависят также от типа данных, в частности от размера алфавита (количества различных символов). Один из двух конкретных кодировщиков может иметь лучшую производительность для маленьких алфавитов, тогда как другой может показывать лучшую производительность для больших алфавитов. Большинство кодировщиков имеют ограничения на размер алфавита, и многие из них специализируются на алфавитах, состоящих ровно из двух символов (0 и 1).

См. также

• Асимметричные системы счисления
• Контекстно-адаптивное двоичное арифметическое кодирование (CABAC)
• Сжатие данных
• Энтропийное кодирование
• Кодирование Хаффмана
• Кодирование диапазона
• Кодирование длины серии

Ссылки

• Маккей, Дэвид Дж. К. (сентябрь 2003 г.). «Глава 6: Потоковые коды» . Теория информации, вывод и алгоритмы обучения . Издательство Кембриджского университета . ISBN  0-521-64298-1 . Архивировано из оригинала (PDF/ PostScript / DjVu / LaTeX ) 22 декабря 2007 года . Проверено 30 декабря 2007 г.
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Раздел 22.6. Арифметическое кодирование» . Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8 . Архивировано из оригинала 11 августа 2011 года . Проверено 18 августа 2011 г.
• Риссанен, Йорма (май 1976 г.). «Обобщенное неравенство Крафта и арифметическое кодирование» . Журнал исследований и разработок IBM . 20 (3): 198–203. дои : 10.1147/rd.203.0198 . Проверено 21 сентября 2007 г.
• Риссанен, Джей-Джей; Лэнгдон Дж.Г.-младший (март 1979 г.). «Арифметическое кодирование» (PDF) . Журнал исследований и разработок IBM . 23 (2): 149–162. дои : 10.1147/rd.232.0149 . S2CID   39909636 . Архивировано из оригинала (PDF) 28 сентября 2007 года . Проверено 22 сентября 2007 г.
• Виттен, Ян Х.; Нил, Рэдфорд М.; Клири, Джон Г. (июнь 1987 г.). «Арифметическое кодирование для сжатия данных» (PDF) . Коммуникации АКМ . 30 (6): 520–540. дои : 10.1145/214762.214771 . S2CID   3343393 . Архивировано (PDF) из оригинала 28 сентября 2007 г. Проверено 21 сентября 2007 г.

• Родионов Анатолий, Волков Сергей (2010) «p-адическое арифметическое кодирование» Современная математика Том 508, 2010 г. Современная математика
• Родионов Анатолий, Волков Сергей (2007) «p-адическое арифметическое кодирование», P-адическое арифметическое кодирование

Внешние ссылки

• В этой статье использованы общедоступные материалы из Пол Э. Блэк. «Арифметическое кодирование» . Словарь алгоритмов и структур данных . НИСТ .
• Сообщение в группе новостей с кратким примером арифметического кодирования (только целые числа).
• Статья PlanetMath об арифметическом кодировании
• Анатомия кодировщика диапазона. В статье объясняется как диапазонное, так и арифметическое кодирование. Он также содержит примеры кода для трех различных арифметических кодировщиков и сравнение производительности.
• Введение в арифметическое кодирование. Архивировано 9 ноября 2020 года в Wayback Machine . 60 страниц.
• Эрик Бодден , Мальте Класен и Йоахим Кнейс: раскрыто арифметическое кодирование . Технический отчет 2007-5, Исследовательская группа Сейбл, Университет Макгилла.
• Арифметическое кодирование + Статистическое моделирование = Сжатие данных Марка Нельсона.
• Сжатие данных с помощью арифметического кодирования Марка Нельсона (2014)
• Быстрая реализация диапазонного кодирования и RANS Джеймса К. Бонфилда