Асимметричные системы счисления

Асимметричные системы счисления ( АНС ) это семейство методов энтропийного кодирования, введенное Ярославом (Яреком) Дудой. из Ягеллонского университета , используется для сжатия данных с 2014 года. из-за улучшенной производительности по сравнению с предыдущими методами. ANS сочетает в себе степень сжатия арифметического кодирования (которое использует почти точное распределение вероятностей ) с затратами на обработку, аналогичными затратам на обработку при кодировании Хаффмана . В табличном варианте ANS (tANS) это достигается путем построения конечного автомата для работы с большим алфавитом без использования умножения.

Помимо прочего, ANS используется в Facebook Zstandard . компрессоре (также используется, например, в ядре Linux , Гугл Хром , браузер Андроид операционная система была опубликована как RFC 8478 для MIME. и HTTP ), Apple LZFSE , компрессор Google Draco 3D compressor (используется, например, в Pixar. универсального описания сцены формате ) и компрессор изображений PIK, CRAM Компрессор ДНК из SAMtools , утилит NVIDIA nvCOMP, Библиотека высокоскоростного сжатия Dropbox DivANS, Компрессор Компрессор текстур Microsoft DirectStorage BCPack, и JPEG XL компрессор изображений.

Основная идея состоит в том, чтобы закодировать информацию в одно натуральное число. $x$. В стандартную двоичную систему счисления можно добавить немного $s\in \{0,1\}$ информации для $x$ добавив $s$ в конце $x$, что дает нам $x'=2x+s$. Для энтропийного кодера это оптимально, если $\Pr(0)=\Pr(1)=1/2$. ANS обобщает этот процесс для произвольных наборов символов. $s\in S$ с сопутствующим распределением вероятностей $(p_{s})_{s\in S}$. В ANS, если информация из $s$ добавляется к $x$ привести к $x'$, затем $x'\approx x\cdot p_{s}^{-1}$. Эквивалентно, $\log _{2}(x')\approx \log _{2}(x)+\log _{2}(1/p_{s})$, где $\log _{2}(x)$ количество бит информации, хранящейся в числе $x$, и $\log _{2}(1/p_{s})$ количество бит, содержащихся в символе $s$.

В правиле кодирования набор натуральных чисел разбивается на непересекающиеся подмножества, соответствующие разным символам — например, на четные и нечетные числа, но с плотностью, соответствующей распределению вероятностей кодируемых символов. Затем, чтобы добавить информацию из символа $s$ в информацию, уже хранящуюся в текущем номере $x$, идем на номер $x'=C(x,s)\approx x/p$ является позиция $x$-ое появление из $s$-е подмножество.

Есть альтернативные способы применить его на практике – прямые математические формулы для шагов кодирования и декодирования (варианты uABS и raNS), либо можно поместить все поведение в таблицу (вариант tANS). Перенормировка используется для предотвращения $x$ уход в бесконечность – передача накопленных битов в битовый поток или из него.

Энтропийное кодирование

Предположим, что будет закодирована последовательность из 1000 нулей и единиц, для непосредственного хранения которой потребуется 1000 бит. Однако, если каким-то образом известно, что он содержит только 1 ноль и 999 единиц, было бы достаточно закодировать положение нуля, для чего требуется всего лишь $\lceil \log _{2}(1000)\rceil \approx 10$ бит здесь вместо исходных 1000 бит.

Обычно такая длина $n$ последовательности, содержащие $pn$ нули и $(1-p)n$ единицы, с некоторой вероятностью $p\in (0,1)$, называются комбинациями . Используя приближение Стирлинга, мы получаем их асимптотическое число:

${n \choose pn}\approx 2^{nh(p)}{\text{ for large }}n{\text{ and }}h(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p),$

называется энтропией Шеннона .

Следовательно, для выбора одной такой последовательности нам нужно примерно $nh(p)$ биты. Это все еще $n$ биты, если $p=1/2$, однако оно также может быть намного меньше. Например, нам нужно всего лишь $\approx n/2$ биты для $p=0.11$.

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

В отличие от комбинаций кодирования, это распределение вероятностей обычно варьируется в компрессорах данных. Для этой цели энтропию Шеннона можно рассматривать как средневзвешенное значение: символ вероятности. $p$ содержит $\log _{2}(1/p)$ биты информации. АНС кодирует информацию в одно натуральное число. $x$, интерпретируемый как содержащий $\log _{2}(x)$ биты информации. Добавление информации из символа вероятности $p$ увеличивает это информационное содержание до $\log _{2}(x)+\log _{2}(1/p)=\log _{2}(x/p)$. Следовательно, новый номер, содержащий обе информации, должен быть $x'\approx x/p$.

Мотивирующие примеры

Рассмотрим источник с 3 буквами А, Б, С с вероятностью 1/2, 1/4, 1/4. Оптимальный префиксный код построить в двоичном виде просто: A = 0, B = 10, C = 11. Тогда сообщение кодируется как ABC -> 01011.

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

• Начните с цифры 1 и выполните операцию с числом для каждой введенной буквы.
• А = умножить на 2; B = умножить на 4, прибавить 2; C = умножить на 4, прибавить 3.
• Выразите число в двоичном виде, затем удалите первую цифру 1.

Рассмотрим более общий источник из k букв с рациональными вероятностями. $n_{1}/N,...,n_{k}/N$. Тогда для выполнения арифметического кодирования источника требуется только точная арифметика с целыми числами.

В общем, АНС — это аппроксимация арифметического кодирования, аппроксимирующая реальные вероятности. $r_{1},...,r_{k}$ рациональными числами $n_{1}/N,...,n_{k}/N$ с маленьким знаменателем $N$.

Основные понятия АНС

Сравнение понятия арифметического кодирования (слева) и АНС (справа). Обе можно рассматривать как обобщения стандартных систем счисления, оптимальных для равномерного распределения вероятностей цифр, в оптимизированные для некоторого выбранного распределения вероятностей. Арифметическое или диапазонное кодирование соответствует добавлению новой информации в наиболее значимой позиции, тогда как АНС обобщает добавление информации в наименее значимой позиции. Его правило кодирования таково: « x переходит к x -му появлению подмножества натуральных чисел, соответствующего текущему кодированному символу». В представленном примере последовательность (01111) кодируется натуральным числом 18, которое меньше 47, полученного с использованием стандартной двоичной системы, из-за лучшего согласования с частотами кодируемой последовательности. Преимущество ANS заключается в хранении информации в одном натуральном числе, в отличие от двух, определяющих диапазон.

Представьте, что есть некоторая информация, хранящаяся в натуральном числе. $x$, например, как битовая последовательность его двоичного расширения. Чтобы добавить информацию из двоичной переменной $s$, мы можем использовать функцию кодирования $x'=C(x,s)=2x+s$, который сдвигает все биты на одну позицию вверх и помещает новый бит в наименее значащую позицию. Теперь функция декодирования $D(x')=(\lfloor x'/2\rfloor ,\mathrm {mod} (x',2))$ позволяет восстановить предыдущий $x$ и этот добавленный бит: $D(C(x,s))=(x,s),\ C(D(x'))=x'$. Мы можем начать с $x=1$ исходное состояние, затем используйте $C$ функцию над последовательными битами конечной битовой последовательности для получения окончательного $x$ число, хранящее всю эту последовательность. Затем используя $D$ функционировать несколько раз, пока $x=1$ позволяет получить последовательность битов в обратном порядке.

Описанная процедура оптимальна для равномерного (симметричного) распределения вероятностей символов. $\Pr(0)=\Pr(1)=1/2$. ANS обобщает его, чтобы сделать его оптимальным для любого выбранного (асимметричного) распределения вероятностей символов: $\Pr(s)=p_{s}$. Пока $s$ в приведенном выше примере выбирал между четным и нечетным $C(x,s)$, в АНС это четное/нечетное деление натуральных чисел заменяется делением на подмножества, имеющие плотности, соответствующие предполагаемому распределению вероятностей $\{p_{s}\}_{s}$: до позиции $x$, есть примерно $xp_{s}$ появления символа $s$.

Функция кодирования $C(x,s)$ возвращает $x$-е появление из такого подмножества, соответствующего символу $s$. Предположение о плотности эквивалентно условию $x'=C(x,s)\approx x/p_{s}$. Предполагая, что натуральное число $x$ содержит $\log _{2}(x)$ кусочки информации, $\log _{2}(C(x,s))\approx \log _{2}(x)+\log _{2}(1/p_{s})$. Отсюда и символ вероятности $p_{s}$ кодируется как содержащий $\approx \log _{2}(1/p_{s})$ бит информации, как это требуется от энтропийных кодировщиков .

Варианты

Унифицированный бинарный вариант (uABS)

Начнем с двоичного алфавита и распределения вероятностей $\Pr(1)=p$, $\Pr(0)=1-p$. До позиции $x$ мы хотим примерно $p\cdot x$ аналоги нечетных чисел (для $s=1$). Мы можем выбрать это количество появлений как $\lceil x\cdot p\rceil$, получающий $s=\lceil (x+1)\cdot p\rceil -\lceil x\cdot p\rceil$. Этот вариант называется uABS и приводит к следующим функциям декодирования и кодирования:

Расшифровка:

s = ceil((x+1)*p) - ceil(x*p)  // 0 if fract(x*p) < 1-p, else 1
if s = 0 then new_x = x - ceil(x*p)   // D(x) = (new_x, 0), this is the same as new_x = floor(x*(1-p))
if s = 1 then new_x = ceil(x*p)  // D(x) = (new_x, 1)

Кодировка:

if s = 0 then new_x = ceil((x+1)/(1-p)) - 1 // C(x,0) = new_x
if s = 1 then new_x = floor(x/p)  // C(x,1) = new_x

Для $p=1/2$ это соответствует стандартной двоичной системе (с перевернутыми 0 и 1), для другого $p$ оно становится оптимальным для данного данного распределения вероятностей. Например, для $p=0.3$ эти формулы приводят к таблице для малых значений $x$:

$C(x,s)$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
$s=0$		0	1		2	3		4	5	6		7	8		9	10		11	12	13
$s=1$	0			1			2				3			4			5				6

Символ $s=1$ соответствует подмножеству натуральных чисел с плотностью $p=0.3$, которые в данном случае являются позициями $\{0,3,6,10,13,16,20,23,26,\ldots \}$. Как $1/4<0.3<1/3$, эти позиции увеличиваются на 3 или 4. Поскольку $p=3/10$ здесь набор символов повторяется каждые 10 позиций.

Кодирование $C(x,s)$ можно найти, взяв строку, соответствующую данному символу $s$, и выбрав данное $x$ в этом ряду. Тогда верхняя строка обеспечивает $C(x,s)$. Например, $C(7,0)=11$ от среднего к верхнему ряду.

Представьте, что мы хотели бы закодировать последовательность «0100», начиная с $x=1$. Первый $s=0$ отвезет нас в $x=2$, затем $s=1$ к $x=6$, затем $s=0$ к $x=9$, затем $s=0$ к $x=14$. С помощью функции декодирования $D(x')$ в этом финале $x$, мы можем получить последовательность символов. Используя для этого таблицу, $x$ в первой строке определяет столбец, затем непустая строка и записанное значение определяют соответствующее $s$ и $x$.

Варианты диапазона (rANS)

Вариант диапазона также использует арифметические формулы, но позволяет работать с большим алфавитом. Интуитивно он делит множество натуральных чисел на размеры $2^{n}$ диапазоны и разбить каждый из них одинаковым образом на поддиапазоны с пропорциями, заданными предполагаемым распределением вероятностей.

Начнем с квантования распределения вероятностей до $2^{n}$ знаменатель, где n (обычно 8-12 бит): выбирается $p_{s}\approx f[s]/2^{n}$ для некоторого естественного $f[s]$ числа (размеры поддиапазонов).

Обозначим ${\text{mask}}=2^{n}-1$и кумулятивную функцию распределения:

$\operatorname {CDF} [s]=\sum _{i<s}f[i]=f[0]+\cdots +f[s-1].$

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

Для $y\in [0,2^{n}-1]$ обозначают функцию (обычно представленную в таблице)

symbol(y) = s  such that  CDF[s] <= y < CDF[s+1]

Теперь функция кодирования:

C(x,s) = (floor(x / f[s]) << n) + (x % f[s]) + CDF[s]

Расшифровка: s = symbol(x & mask)

D(x) = (f[s] * (x >> n) + (x & mask ) - CDF[s], s)

Таким образом, мы можем закодировать последовательность символов в большое натуральное число x . Чтобы избежать использования арифметики больших чисел, на практике используются потоковые варианты: которые обеспечивают $x\in [L,b\cdot L-1]$ путем перенормировки: отправка младших битов x в битовый поток или из него (обычно L и b представляют собой степени 2).

В варианте rans x , например, 32-битный. Для 16-битной перенормировки $x\in [2^{16},2^{32}-1]$, декодер при необходимости дополняет младшие биты из битового потока:

if(x < (1 << 16)) x = (x << 16) + read16bits()

Табличный вариант (tANS)

Простой пример автомата АНС с 4 состояниями для распределения вероятностей Pr( a ) = 3/4, Pr( b ) = 1/4. Символ b содержит −lg(1/4) = 2 бита информации и поэтому всегда дает два бита. Напротив, символ a содержит -lg(3/4) ~ 0,415 бит информации, поэтому иногда он выдает один бит (из состояния 6 и 7), иногда 0 бит (из состояния 4 и 5), только увеличивая состояние, что действует как буфер, содержащий дробное число битов: lg( x ). На практике количество состояний составляет, например, 2048 для алфавита размером 256 (для прямого кодирования байтов).

Вариант tANS помещает все поведение (включая перенормировку) для $x\in [L,2L-1]$ в таблицу, которая дает конечный автомат, избегающий необходимости умножения.

Наконец, шаг цикла декодирования можно записать так:

t = decodingTable(x);  
x = t.newX + readBits(t.nbBits); //state transition
writeSymbol(t.symbol); //decoded symbol

Шаг цикла кодирования:

s = ReadSymbol();
nbBits = (x + ns[s]) >> r;  // # of bits for renormalization
writeBits(x, nbBits);  // send the least significant bits to bitstream
x = encodingTable[start[s] + (x >> nbBits)];

Конкретное кодирование tANS определяется путем присвоения символа каждому $[L,2L-1]$ позиции, их количество появлений должно быть пропорционально предполагаемым вероятностям. Например, можно выбрать назначение «abdacdac» для распределения вероятностей Pr(a)=3/8, Pr(b)=1/8, Pr(c)=2/8, Pr(d)=2/8. Если символы назначаются в диапазонах длин, являющихся степенями 2, мы получим кодирование Хаффмана . Например, префиксный код a->0, b->100, c->101, d->11 будет получен для tANS с присвоением символа «aaaabcdd».

Пример генерации таблиц tANS для алфавита размера m = 3 и состояний L = 16 с последующим применением их для декодирования потока. Сначала мы аппроксимируем вероятности, используя дробь, знаменателем которой является количество состояний. Затем мы распространяем эти символы практически единообразно, при необходимости детали могут зависеть от криптографического ключа для одновременного шифрования. Затем мы перечисляем появления, начиная со значения — их количества для данного символа. Затем мы повторно заполняем младшие биты потока, чтобы вернуться к предполагаемому диапазону x (перенормировка).

Замечания

Что касается кодирования Хаффмана, изменение распределения вероятностей tANS является относительно дорогостоящим, поэтому оно в основном используется в статических ситуациях, обычно с некоторой схемой Лемпеля-Зива (например, ZSTD, LZFSE). В этом случае файл разбивается на блоки – для каждого из них независимо подсчитываются частоты символов, затем после аппроксимации (квантования) записываются в заголовок блока и используются как статическое распределение вероятностей для tANS.

Напротив, rANS обычно используется как более быстрая замена кодирования диапазона (например, CRAM , LZNA, Draco, ). Он требует умножения, но более эффективен в использовании памяти и подходит для динамической адаптации распределений вероятностей.

Кодирование и декодирование ANS выполняются в противоположных направлениях, образуя стек символов. Это неудобство обычно устраняется путем кодирования в обратном направлении, после чего можно выполнить декодирование в прямом направлении. Для зависимости от контекста, как в модели Маркова , кодировщику необходимо использовать контекст с точки зрения последующего декодирования. Для обеспечения адаптивности кодер должен сначала пойти вперед, чтобы найти вероятности, которые будут использоваться (прогнозированы) декодером, и сохранить их в буфере, а затем закодировать в обратном направлении, используя буферизованные вероятности.

Конечное состояние кодирования необходимо для начала декодирования, поэтому его необходимо сохранить в сжатом файле. Эту стоимость можно компенсировать сохранением некоторой информации в исходном состоянии кодера. Например, вместо того, чтобы начинать с состояния «10000», начните с состояния «1****», где «*» — это некоторые дополнительные сохраненные биты, которые можно получить в конце декодирования. В качестве альтернативы это состояние можно использовать в качестве контрольной суммы, начиная кодирование с фиксированного состояния и проверяя, является ли конечное состояние декодирования ожидаемым.

Патентный спор

Автор нового алгоритма ANS и его вариантов tANS и ranS специально намеревался сделать свою работу свободно доступной в общественном достоянии по альтруистическим причинам. Он не стремился извлечь из них выгоду и предпринял шаги, чтобы гарантировать, что они не станут «законным минным полем», не будут ограничены другими или получат от них выгоду. В 2015 году Google опубликовала в США, а затем и во всем мире патент на «Смешанное кодирование логических токенов и коэффициентов». В то время Google попросил профессора Дуду помочь ему со сжатием видео, поэтому он был хорошо осведомлен об этой области, и им помогал первоначальный автор.

Дуда не был доволен тем, что (случайно) узнал о патентных намерениях Google, поскольку он ясно дал понять, что хочет сделать это общественным достоянием, и помогал Google именно на этом основании. Впоследствии Дуда подал стороннюю заявку. в Патентное ведомство США с просьбой об отказе. В 2018 году USPTO отклонило заявку, а Google впоследствии отказался от патента.

В июне 2019 года Microsoft подала заявку на патент под названием «Особенности кодирования и декодирования асимметричной системы счисления». 27 октября 2020 г. ВПТЗ США окончательно отклонило заявку. Однако 2 марта 2021 г. Microsoft подала в ВПТЗ США пояснительную заявку, в которой говорилось: «Заявитель со всем уважением не согласен с отклонениями». стремясь отменить окончательный отказ в рамках программы «Пилот после окончательного рассмотрения 2.0». После повторного рассмотрения USPTO удовлетворило заявку 25 января 2022 года.

См. также

• Энтропийное кодирование
• Кодирование Хаффмана
• Арифметическое кодирование
• Кодирование диапазона
• Zstandard Facebook компрессор
• LZFSE Компрессор Apple

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

• Аппаратные архитектуры с высокой пропускной способностью для энтропийного кодирования асимметричных систем счисления С. М. Наджмабади, З. Ван, Ю. Баруд, С. Саймон, ISPA 2015
• Энтропийные кодеры нового поколения Реализация tANS с энтропией конечного состояния (FSE) от Янна Колле
• rygorous/ryg_rans Реализация RANS Фабианом Гизеном
• jkbonfield/rans_static Быстрая реализация raNS и арифметического кодирования Джеймса К. Бонфилда
• facebook/zstd Компрессор Facebook Zstandard от Янна Колле (автора LZ4 )
• LZFSE LZFSE Компрессор (LZ+FSE) компании Apple Inc.
• Компрессор ДНК CRAM 3.0 (ранс порядка 1) (часть SAMtools ) от Европейского института биоинформатики
• [1] реализация для Google VP10
• [2] реализация для Google WebP
• [3] Google Draco. Библиотека сжатия 3D
• aom_dsp — aom — Git и Google реализуют Alliance for Open Media
• Сжатие данных с использованием асимметричных систем счисления - Демонстрационный проект Wolfram
• GST: сверхсжатые текстуры, декодируемые графическим процессором. , декодируемые графическим процессором. GST: сверхсжатые текстуры
• Книга «Понимание сжатия» А. Хаеки, К. Маканлиса