Асимметричные системы счисления (ANS ) - это семейство методы энтропийного кодирования, представленные Ярославом (Ярек) Дудой из Ягеллонского университета, используемые в сжатии данных с 2014 года благодаря улучшенной производительности по сравнению с ранее используемыми методами, В 30 раз быстрее. ANS сочетает степень сжатия арифметического кодирования (которое использует почти точное распределение вероятностей) со стоимостью обработки, аналогичной затратам на обработку кодирования Хаффмана. В табличном варианте ANS (tANS) это достигается путем построения конечного автомата для работы с большим алфавитом без использования умножения.
Среди прочего, ANS используется в компрессоре Facebook Zstandard (также используется, например, в ядре Linux, Android операционной системы, был опубликован как RFC 8478 для MIME и HTTP ), в компрессоре Apple LZFSE, Google 3D-компрессор Draco (используется, например, в Pixar формате универсального описания сцены ) и компрессор изображений PIK в CRAM ДНК-компрессор из Утилиты SAMtools, Dropbox компрессор DivANS, а также в стандарте сжатия изображений следующего поколения JPEG XL.
Основная идея состоит в том, чтобы кодировать информацию в одно натуральное число . В стандартной двоичной системе счисления мы можем добавить бит информации к путем добавления в конце , что дает нам . Для энтропийного кодера это оптимально, если . ANS обобщает этот процесс для произвольных наборов символов с соответствующим распределением вероятностей . В ANS, если является результатом добавления информации из в , затем . Эквивалентно , где - количество битов информации, хранящихся в числе и - количество битов, содержащихся в символе .
Для правила кодирования набор натуральных чисел разбивается на непересекающиеся подмножества, соответствующие разным символам - например, в четные и нечетные числа, но с плотностями, соответствующими распределению вероятностей символов для кодирования. Затем, чтобы добавить информацию из символа в информацию, уже сохраненную в текущем числе , мы переходим к числу - позиция -е появление из -го подмножества.
Есть альтернативные способы применения на практике - прямые математические формулы для шагов кодирования и декодирования (варианты uABS и rANS), или можно поместить все поведение в таблицу (вариант tANS). Ренормализация используется для предотвращения перехода к бесконечности - передачи накопленных битов в поток битов или из него.
Предположим, что последовательность из 1000 нулей и единиц будет закодирована, что займет 1000 бит для хранения прямо. Однако, если каким-то образом известно, что он содержит только 1 ноль и 999 единиц, этого будет достаточно для кодирования положения нуля, для чего требуется только бит здесь вместо исходных 1000 бит.
Обычно такая длина последовательностей, содержащих нули и единиц для некоторой вероятности , называются комбинациями. Используя приближение Стирлинга, мы получаем их асимптотическое число, равное
называется энтропия Шеннона.
Следовательно, чтобы выбрать одну такую последовательность, нам нужно приблизительно бит. Это по-прежнему бит, если , однако он также может быть значительно меньше. Например, нам нужно только бит для .
энтропия coder позволяет кодировать последовательность символов, используя приблизительно биты энтропии Шеннона на символ. Например, ANS можно напрямую использовать для перечисления комбинаций: назначать разные натуральные числа каждой последовательности символов, имеющих фиксированные пропорции, почти оптимальным образом.
В отличие от комбинаций кодирования, это распределение вероятностей обычно варьируется в компрессорах данных. Для этой цели энтропию Шеннона можно рассматривать как средневзвешенное значение: символ вероятности содержит биты информации. ANS кодирует информацию в одно натуральное число , интерпретируемое как содержащее бит информации. Добавление информации из символа вероятности увеличивает это информационное содержание до . Следовательно, новое число, содержащее обе данные, должно быть .
Представьте, что есть некоторая информация, хранящаяся в натуральном числе , например, как битовая последовательность его двоичного расширения. Чтобы добавить информацию из двоичной переменной , мы можем использовать функцию кодирования , который сдвигает все биты на одну позицию вверх и помещает новый бит в наименее значимую позицию. Теперь функция декодирования позволяет получить предыдущий и этот добавленный бит: . Мы можем начать с исходного состояния , а затем использовать функцию для последовательных битов конечная последовательность битов для получения окончательного числа , в котором хранится вся эта последовательность. Затем используйте функцию несколько раз, пока не позволит получить последовательность битов в обратном порядке.
Описанная выше процедура оптимальна для равномерного (симметричного) распределения вероятностей символов . ANS обобщает его, чтобы сделать его оптимальным для любого выбранного (асимметричного) распределения вероятностей символов: . В то время как в приведенном выше примере выбирал между четным и нечетным , в ANS это четное / нечетное деление натуральных чисел заменено делением на подмножества с плотностями, соответствующими предполагаемому распределению вероятностей : до позиции примерно вхождений символа .
Функция кодирования возвращает -е появление из такого подмножества, соответствующее символу . Предположение о плотности эквивалентно условию . Предполагая, что натуральное число содержит бит информация, . Следовательно, символ вероятности кодируется как содержащий битов информации, которые требуются от энтропийных кодеров.
Начнем с двоичного алфавита и распределение вероятностей , . До позиции нам нужно приблизительно аналоги нечетных чисел (для ). Мы можем выбрать это количество появлений как , получив . Этот вариант называется uABS и приводит к следующим функциям декодирования и кодирования:
Декодирование:
s = ceil ((x + 1) * p) - ceil (x * p) // 0 если фракция (x * p) < 1-p, else 1 if s = 0 then new_x = x - ceil(x*p) // D(x) = (new_x, 0) if s = 1 then new_x = ceil(x*p) // D(x) = (new_x, 1)
Кодировка:
если s = 0, то new_x = ceil ((x + 1) / (1-p)) - 1 // C (x, 0) = new_x, если s = 1 тогда new_x = floor (x / p) // C (x, 1) = new_x
Для это составляет стандартная двоичная система (с инвертированными 0 и 1), для другого она становится оптимальной для данного распределения вероятностей. Например, для эти формулы приводят к таблице малых значений :
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ||||||||
0 | 1 | 2 | 3 | 4 | 5 | 6 |
символ соответствует подмножеству натуральных чисел с плотностью , которые в данном случае являются позициями . Поскольку , эти позиции увеличиваются на 3 или 4. Поскольку здесь, образец символов повторяется каждые 10 позиций.
Кодирование можно найти, взяв строку, соответствующую данному символу и выбирая данный в этой строке. Затем в верхней строке содержится . Например, от середины до верхней строки.
Представьте, что мы хотели бы закодировать последовательность '0100', начиная с . Сначала ведет нас к , затем на , затем до , затем от до . Используя функцию декодирования на этом окончательном , мы можем получить последовательность символов. Используя таблицу для этой цели, в первой строке определяет столбец, затем непустая строка и записанное значение определяют соответствующий и .
Вариант диапазона также использует арифметические формулы, но позволяет работать с большим алфавитом. Интуитивно он делит набор натуральных чисел на диапазоны размера и разделяет каждый из них идентичным образом на поддиапазоны пропорций, заданных предполагаемой вероятностью распространение.
Мы начинаем с квантования распределения вероятностей до знаменателя , где (обычно 8-12 бит): для некоторых натуральных чисел (размеры поддиапазонов).
Обозначьте , кумулятивная функция распределения:
для обозначает функцию (обычно в таблице)
symbol (y) = s, такое что CDF [s] <= y < CDF[s+1]
.
Теперь функция кодирования:
C (x, s) = (floor (x / f [s]) << n) + (x % f[s]) + CDF[s]
Декодирование: s = символ (x маска)
D (x) = (f [s] * (x>>n) + (x mask) - CDF [s], s)
Таким образом, мы можем закодировать последовательность символов в большое натуральное число . Чтобы избежать использования арифметики с большими числами, на практике используются потоковые варианты: которые обеспечивают выполнение путем перенормировки: отправка младших битов в поток битов или из него (обычно и - степени двойки).
В варианте RANS равно например 32 бит. Для 16-битной перенормировки , декодер пополняется наименьшие значащие биты из потока битов при необходимости:
if (x < (1 << 16)) x = (x << 16) + read16bits()
вариант tANS помещает все поведение (включая перенормировку) для в таблицу, которая дает конечный автомат, избегая необходимости умножения.
Наконец, шаг цикла декодирования можно записать как:
t = decodingTable (x); x = t.newX + readBits (t.nbBits); // переход состояния writeSymbol (t.symbol); // декодированный символ
Шаг цикла кодирования:
s = ReadSymbol (); nbBits = (x + ns [s])>>r; // # бит для перенормировки writeBits (x, nbBits); // отправляем младшие биты в битовый поток x = encodingTable [start [s] + (x>>nbBits)];
Конкретное кодирование tANS определяется путем присвоения символа каждой позиции , их количество появлений должно быть пропорциональным предполагаемым вероятностям. Например, можно выбрать присвоение "abdacdac" для распределения вероятностей Pr (a) = 3/8, Pr (b) = 1/8, Pr (c) = 2/8, Pr (d) = 2/8. Если символы назначены в диапазонах длин, являющихся степенями двойки, мы получим кодирование Хаффмана. Например, префиксный код a->0, b->100, c->101, d->11 будет получен для tANS с присвоением символа «aaaabcdd».
.
Пример создания таблиц tANS для алфавита размера m = 3 и L = 16 состояний с последующим их применением для декодирования потока. Сначала мы аппроксимируем вероятности дробью, знаменателем которой является количество состояний. Затем мы распределяем эти символы почти единообразно, при желании детали могут зависеть от криптографического ключа для одновременного шифрования. Затем мы перечисляем появления, начиная со значения, равного их количеству для данного символа. Затем мы пополняем самые младшие биты из потока, чтобы вернуться к предполагаемому диапазону для x (перенормировка).Что касается кодирования Хаффмана, изменение распределения вероятностей tANS относительно дорого, поэтому в основном используется в статических ситуациях, обычно с некоторой схемой Лемпеля – Зива (например, ZSTD, LZFSE). В этом случае файл разбивается на блоки - для каждого из них независимо подсчитываются частоты символов, которые после аппроксимации (квантования) записываются в заголовок блока и используются как статическое распределение вероятностей для tANS.
Напротив, rANS обычно используется в качестве более быстрой замены для кодирования диапазона (например, CRAM, LZNA, Draco, AV1). Он требует умножения, но более эффективен с точки зрения памяти и подходит для динамической адаптации распределений вероятностей.
Кодирование и декодирование ANS выполняются в противоположных направлениях, что делает его стеком для символов. Это неудобство обычно устраняется путем кодирования в обратном направлении, после чего декодирование может выполняться вперед. Для зависимости от контекста, такой как модель Маркова, кодировщику необходимо использовать контекст с точки зрения последующего декодирования. Для адаптивности кодировщик должен сначала пойти вперед, чтобы найти вероятности, которые будут использоваться (спрогнозированы) декодером, и сохранить их в буфере, а затем закодировать в обратном направлении, используя буферизованные вероятности.
Конечное состояние кодирования требуется для начала декодирования, поэтому оно должно быть сохранено в сжатом файле. Эти затраты могут быть компенсированы сохранением некоторой информации в исходном состоянии кодировщика. Например, вместо того, чтобы начинать с состояния «10000», начните с состояния «1 ****», где «*» - некоторые дополнительные сохраненные биты, которые могут быть извлечены в конце декодирования. В качестве альтернативы это состояние можно использовать в качестве контрольной суммы, запустив кодирование с фиксированного состояния и проверив, является ли конечное состояние декодирования ожидаемым.