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

Форма энтропийного кодирования, используемая при сжатии данных

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

Пример арифметического кодирования, предполагающий фиксированное распределение вероятностей трех символов "A", "B" и "C". Вероятность "A" составляет 50%, вероятность "B" составляет 33% и вероятность "C" составляет 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).

Подробности реализации и примеры

Кодирование сообщения «WIKI» с помощью арифметического кодирования

Пример выше, визуализированный в виде круга, значения красного цвета кодируют «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% вероятность символа END-OF-DATA. (Наличие этого символа означает, что поток будет «внутренне завершен», что довольно часто встречается при сжатии данных; когда этот символ появляется в потоке данных, декодер будет знать, что весь поток был декодирован.)

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

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

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

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

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

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

• интервал для НЕЙТРАЛЬНОГО будет [0, 0,6)
• интервал для ПОЛОЖИТЕЛЬНОГО будет [0,6, 0,8)
• интервал для ОТРИЦАТЕЛЬНОГО будет [0,8, 0,9)
• интервал для КОНЦА ДАННЫХ будет [0,9, 1).

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

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

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

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

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

Процесс начинается с того же интервала, который использует кодер: [0,1), и с использованием той же модели, разделяя его на те же четыре подинтервала, которые должен иметь кодер. Дробь 0,538 попадает в подинтервал для NEUTRAL, [0, 0,6); это указывает на то, что первый символ, который считывал кодер, должен был быть NEUTRAL, поэтому это первый символ сообщения.

Далее разделим интервал [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) .
• интервал для КОНЦА ДАННЫХ будет [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).
• интервал для КОНЦА ДАННЫХ будет [0,534, 0,540).

Теперь 0,538 попадает в интервал символа END-OF-DATA; следовательно, это должен быть следующий символ. Поскольку это также внутренний символ завершения, это означает, что декодирование завершено. Если поток не завершен внутренне, должен быть какой-то другой способ указать, где поток останавливается. В противном случае процесс декодирования может продолжаться вечно, ошибочно считывая больше символов из дроби, чем было фактически закодировано в ней.

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

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

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

∑ − log 2 ⁡ ( p i ) = − log 2 ⁡ ( 0,6 ) − log 2 ⁡ ( 0,1 ) − log 2 ⁡ ( 0,1 ) = 7,381 бит . {\displaystyle \sum -\log _{2}(p_{i})=-\log _{2}(0,6)-\log _{2}(0,1)-\log _{2}(0,1)=7,381{\text{ бит}}.}

Но в двоичном кодировании должно использоваться целое число бит, поэтому кодер для этого сообщения будет использовать не менее 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); [5/27, 6/27); и двоичный интервал [0,00101111011, 0,00111000111). Это также пример того, как статистические методы кодирования, такие как арифметическое кодирование, могут создавать выходное сообщение, которое больше входного сообщения, особенно если модель вероятности отключена.

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

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

Точность и перенормировка

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

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

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

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

${\displaystyle \mathrm {DABDDB} }$

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

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

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

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

${\displaystyle 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 мы умножаем каждый член в приведенном выше выражении на произведение частот всех ранее встречавшихся символов:

${\displaystyle {\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 можно вычислить как:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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 бита на символ по сравнению с одним битом на символ в исходном кодировании, т. е. сжатии. Разрешение произвольно больших последовательностей произвольно приближается к энтропии — как и арифметическое кодирование — но требует для этого огромных кодов, поэтому не так практично, как арифметическое кодирование для этой цели. ${\displaystyle 56.7\%}$

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

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

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

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

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

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

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

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

• Патент США 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 г. – Джоан Л. Митчелл, Уильям Б. Пеннебейкер – Сжатие/распаковка данных арифметического кодирования с помощью выборочно используемых разнообразных кодеров и декодеров арифметического кодирования
• Патент Японии 11782787 – ( NEC ) подан 13 мая 1987 г., выдан 18 ноября 1988 г. – Мичио Шимада – Устройство арифметического кодирования сжатия данных
• Патент Японии 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 г. – Джеймс Д. Аллен – Метод и устройство для энтропийного кодирования

Примечание: Этот список не является исчерпывающим. См. следующие ссылки для списка дополнительных патентов США. ^[8] Кодек Dirac использует арифметическое кодирование и не находится на рассмотрении патента. ^[9]

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

Показатели и другие технические характеристики

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

Смотрите также

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

Примечания

1. Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 апреля 2014 г.). Основы мультимедиа. Springer Science & Business Media. ISBN 978-3-319-05290-8.
2. J. Duda, K. Tahboub, NJ Gadil, EJ Delp, Использование асимметричных систем счисления в качестве точной замены кодирования Хаффмана, Симпозиум по кодированию изображений, 2015.
3. Паско, Ричард Кларк (май 1976 г.). Алгоритмы кодирования исходного кода для быстрого сжатия данных (PhD). Стэнфордский университет. CiteSeerX 10.1.1.121.3377 . 
4. "Что такое JPEG?". comp.compression Часто задаваемые вопросы (часть 1/3) .
5. "Рекомендация T.81 (1992) Исправление 1 (01/04)". Рекомендация T.81 (1992) . Международный союз электросвязи. 9 ноября 2004 г. Получено 3 февраля 2011 г.
6. Пеннебейкер, У. Б.; Митчелл, Дж. Л. (1992). Стандарт сжатия данных неподвижных изображений JPEG . Kluwer Academic Press. ISBN 0442012721.
7. "T.81 – ЦИФРОВОЕ СЖАТИЕ И КОДИРОВАНИЕ НЕПРЕРЫВНЫХ ТОНАЛЬНЫХ ИЗОБРАЖЕНИЙ – ТРЕБОВАНИЯ И РУКОВОДСТВО" (PDF) . CCITT . Сентябрь 1992 . Получено 12 июля 2019 .
8. "Часто задаваемые вопросы". comp.compression .
9. "Выпущен видеокодек Dirac 1.0 [LWN.net]". lwn.net .
10. Например, Howard & Vitter (1994) обсуждают версии арифметического кодирования, основанные на диапазонах действительных чисел, целочисленных приближениях к этим диапазонам и еще более ограниченном типе приближения, который они называют двоичным квазиарифметическим кодированием. Они утверждают, что разница между действительными и целочисленными версиями незначительна, доказывают, что потери при сжатии для их квазиарифметического метода могут быть сделаны произвольно малыми, и ограничивают потери при сжатии, понесенные одним из их приближений, менее 0,06%. См.: Howard, Paul G.; Vitter, Jeffrey S. (1994), "Арифметическое кодирование для сжатия данных" (PDF) , Труды IEEE , 82 (6): 857–865, doi :10.1109/5.286189, hdl : 1808/7229 , заархивировано из оригинала (PDF) 18 октября 2013 г. , извлечено 17 октября 2013 г..

Ссылки

• MacKay, David JC (сентябрь 2003 г.). "Глава 6: Потоковые коды". Теория информации, вывод и алгоритмы обучения . Cambridge University Press . ISBN 0-521-64298-1. Архивировано из оригинала (PDF/ PostScript / DjVu / LaTeX ) 22 декабря 2007 г. . Получено 30 декабря 2007 г. .
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Раздел 22.6. Арифметическое кодирование". Numerical Recipes: The Art of Scientific Computing (3-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-88068-8. Архивировано из оригинала 11 августа 2011 . Получено 18 августа 2011 .
• Риссанен, Йорма (май 1976 г.). «Обобщенное неравенство Крафта и арифметическое кодирование». IBM Journal of Research and Development . 20 (3): 198–203. doi :10.1147/rd.203.0198 . Получено 21 сентября 2007 г.
• Rissanen, JJ; Langdon GG, Jr (март 1979). "Арифметическое кодирование" (PDF) . IBM Journal of Research and Development . 23 (2): 149–162. doi :10.1147/rd.232.0149. S2CID  39909636. Архивировано из оригинала (PDF) 28 сентября 2007 г. . Получено 22 сентября 2007 г. .
• Witten, Ian H.; Neal, Radford M.; Cleary, John G. (июнь 1987 г.). "Арифметическое кодирование для сжатия данных" (PDF) . Communications of the ACM . 30 (6): 520–540. doi :10.1145/214762.214771. S2CID  3343393. Архивировано (PDF) из оригинала 28 сентября 2007 г. . Получено 21 сентября 2007 г. .

• Родионов Анатолий, Волков Сергей (2010) "p-адическое арифметическое кодирование" Contemporary Mathematics Volume 508, 2010 Contemporary Mathematics
• Родионов Анатолий, Волков Сергей (2007) "p-адическое арифметическое кодирование", P-адическое арифметическое кодирование

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

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