Асимметричные системы счисления - Asymmetric numeral systems

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Май 2017 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Асимметричные системы счисления (ANS)^[1] это семья энтропийное кодирование методы, введенные Ярославом (Ярек) Дудой^[2] из Ягеллонский университет, используется в Сжатие данных с 2014 года^[3] благодаря улучшенной производительности по сравнению с ранее используемыми методами, которая работает до 30 раз быстрее.^[4] ANS сочетает в себе степень сжатия арифметическое кодирование (который использует почти точное распределение вероятностей), со стоимостью обработки, аналогичной стоимости Кодирование Хаффмана. В табличном варианте ANS (tANS) это достигается путем построения конечный автомат работать с большим алфавитом без умножения.

Среди прочего, ANS используется в Facebook Zстандарт компрессор^[5][6] (также используется, например, в Linux ядро^[7] Android^[8] операционная система, была опубликована как RFC 8478 за MIME^[9] и HTTP^[10]), в яблоко LZFSE компрессор^[11] Google Компрессор Draco 3D^[12](используется, например, в Pixar Универсальное описание сцены формат^[13]) и компрессор изображений ПИК,^[14] в CRAM Компрессор ДНК^[15] из SAMtools коммунальные услуги, Dropbox Компрессор ДивАНС,^[16] И в JPEG XL^[17] стандарт сжатия изображений нового поколения.

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

Для правила кодирования набор натуральных чисел разбивается на непересекающиеся подмножества, соответствующие разным символам - например, на четные и нечетные числа, но с плотностями, соответствующими распределению вероятностей символов для кодирования. Затем добавить информацию из символа ${ displaystyle s}$ в информацию, уже сохраненную в текущем номере ${ displaystyle x}$, идем к номеру ${ Displaystyle х '= С (х, s) приблизительно х / р}$ позиция ${ displaystyle x}$-й выход из ${ displaystyle s}$-е подмножество.

Есть альтернативные способы его применения на практике - прямые математические формулы для шагов кодирования и декодирования (варианты uABS и rANS) или можно поместить все поведение в таблицу (вариант tANS). Ренормализация используется для предотвращения ${ displaystyle x}$ переход к бесконечности - передача накопленных битов в поток битов или из него.

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

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

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

${ displaystyle {n choose pn} приблизительно 2 ^ {nh (p)} { text {for large}} n { text {and}} h (p) = - p log _ {2} (p ) - (1-р) log _ {2} (1-р),}$

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

Следовательно, чтобы выбрать одну такую ​​последовательность, нам потребуется примерно ${ displaystyle nh (p)}$ биты. Это все еще ${ displaystyle n}$ биты, если ${ displaystyle p = 1/2}$однако он также может быть намного меньше. Например нам нужно только ${ Displaystyle приблизительно п / 2}$ биты для ${ displaystyle p = 0.11}$.

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

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

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

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

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

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

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

Единый двоичный вариант (uABS)

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

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

s = потолок((Икс+1)*п) - потолок(Икс*п)  // 0, если фракт (x * p) <1-p, иначе 1если s = 0 тогда new_x = Икс - потолок(Икс*п)   // D (x) = (new_x, 0)если s = 1 тогда new_x = потолок(Икс*п)  // D (x) = (new_x, 1)

Кодировка:

если s = 0 тогда new_x = потолок((Икс+1)/(1-п)) - 1 // C (x, 0) = new_xесли s = 1 тогда new_x = этаж(Икс/п)  // C (x, 1) = new_x

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

${ Displaystyle С (х, s)}$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
${ displaystyle s = 0}$		0	1		2	3		4	5	6		7	8		9	10		11	12	13
${ displaystyle s = 1}$	0			1			2				3			4			5				6

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

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

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

Варианты диапазона (rANS) и потоковая передача

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

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

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

${ displaystyle operatorname {CDF} [s] = sum _ {i$

За ${ displaystyle y in [0,2 ^ {n} -1]}$ обозначают функцию (обычно в таблице)

символ (y) = s такой, что CDF [s] <= y .

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

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)

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

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

если (x <(1 << 16)) x = (x << 16) + read16bits ()

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

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

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

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

т = decodingTable(Икс);  Икс = т.newX + readBits(т.nbBits); // переход состоянияwriteSymbol(т.символ); // декодированный символ

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

s = ReadSymbol();nbBits = (Икс + нс[s]) >> р;  // # бит для перенормировкиwriteBits(Икс, nbBits);  // отправляем младшие биты в битовый потокИкс = encodingTable[Начните[s] + (Икс >> nbBits)];

Конкретное кодирование tANS определяется путем присвоения символа каждому ${ displaystyle [L, 2L-1]}$ позиции, их количество появлений должно быть пропорционально предполагаемой вероятности. Например, можно выбрать присвоение "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, ЛЗНА, Драко, АВ1). Он требует умножения, но более эффективен с точки зрения памяти и подходит для динамической адаптации распределений вероятностей.

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

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

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

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

Рекомендации

1. ^ Дж. Дуда, К. Тахбуб, Н. Дж. Гадил, Э. Дж. Делп, Использование асимметричных систем счисления как точная замена кодирования Хаффмана, Симпозиум по кодированию изображений, 2015.
2. ^ http://th.if.uj.edu.pl/~dudaj/
3. ^ Дуда, Ярек (6 октября 2019 г.). «Список компрессоров, использующих ANS, реализации и другие материалы». Получено 6 октября, 2019.
4. ^ "Google обвиняется в попытке запатентовать технологию общественного достояния". Пищевой компьютер. 11 сентября 2017 года.
5. ^ Меньшее и быстрое сжатие данных с Zstandard, Facebook, август 2016 г.
6. ^ 5 способов, которыми Facebook улучшил масштабирование с помощью Zstandard, Facebook, декабрь 2018 г.
7. ^ Сжатие Zstd для Btrfs и Squashfs, установленное для Linux 4.14, уже используется в Facebook, Phoronix, сентябрь 2017
8. ^ «Zstd в выпуске Android P».
9. ^ Zstandard Compression и тип носителя application / zstd (стандарт электронной почты)
10. ^ Параметры протокола передачи гипертекста (HTTP), IANA
11. ^ Apple открывает исходный код своего нового алгоритма сжатия LZFSE, InfoQ, июль 2016 г.
12. ^ Библиотека сжатия Google Draco 3D
13. ^ Google и Pixar добавляют сжатие Draco в универсальный формат описания сцены (USD)
14. ^ Google PIK: новый формат изображений с потерями для Интернета
15. ^ Спецификация формата CRAM (версия 3.0)
16. ^ Улучшение сжатия вместе с DivANS
17. ^ Ратушняк Александр; Вассенберг, Ян; Снейерс, Джон; Алакуйяла, Юрки; Вандевенн, Лоде; Версари, Лука; Обрик, Роберт; Забадка, Золтан; Ключников, Евгений; Комса, Юлия-Мария; Потемпа, Кшиштоф; Брюс, Мартин; Фиршинг, Мориц; Хасанова, Рената; Рууд ван Асселдонк; Букортт, Сами; Гомес, Себастьян; Фишбахер, Томас (2019). «Проект комитета системы кодирования изображений JPEG XL». arXiv:1908.03565 [eess.IV ].
18. ^ Объяснение сжатия данных, Мэтт Махони

внешняя ссылка

• Аппаратные архитектуры с высокой пропускной способностью для энтропийного кодирования асимметричных систем счисления С. М. Наджмабади, З. Ван, Ю. Баруд, С. Саймон, ISPA 2015
• https://github.com/Cyan4973/FiniteStateEntropy Конечная энтропия (FSE) реализации tANS Янн Колле
• https://github.com/rygorous/ryg_rans Внедрение rANS Фабианом Гизеном
• https://github.com/jkbonfield/rans_static Быстрая реализация rANS и аритметического кодирования Джеймсом К. Бонфилдом
• https://github.com/facebook/zstd/ Facebook Zстандарт компрессор Янн Колле (автор LZ4 )
• https://github.com/lzfse/lzfse LZFSE компрессор (LZ + FSE) Apple Inc.
• Компрессор CRAM 3.0 DNA (заказ 1 rANS) (часть SAMtools ) к Европейский институт биоинформатики
• https://chromium-review.googlesource.com/#/c/318743 реализация для Google VP10
• https://chromium-review.googlesource.com/#/c/338781/ реализация для Google WebP
• https://github.com/google/draco/tree/master/core Google Библиотека сжатия Draco 3D
• https://aomedia.googlesource.com/aom/+/master/aom_dsp реализация Альянс открытых СМИ
• http://demonstrations.wolfram.com/DataCompressionUsingAsymmetricNumeralSystems/ Вольфрам Демонстрационный проект
• http://gamma.cs.unc.edu/GST/ GST: суперсжатый с возможностью декодирования с помощью графического процессора Текстуры
• Что такое сжатие книга А. Хэки, К. Маканлиса