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

редактировать

Методы энтропийного кодирования

Асимметричные системы счисления (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.

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

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

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

Содержание

1 Энтропийное кодирование
2 Основные концепции ANS
3 Унифицированный двоичный вариант (uABS)
4 Варианты диапазона (rANS) и потоковая передача
5 Табличный вариант (tANS)
6 Примечания
7 См. Также
8 Ссылки
9 Внешние ссылки

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

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

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

(npn) ≈ 2 nh (p) для больших n и h (p) = - p log 2 ⁡ (p) - (1 - p) журнал 2 ⁡ (1 - p), {\ displaystyle {n \ choose pn} \ приблизительно 2 ^ {nh (p)} {\ text {для больших}} n {\ text {и}} h (p) = - p \ log _ {2} (p) - (1-p) \ log _ {2} (1-p),}

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

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

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

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

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

Основные концепции ANS

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

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

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

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

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

Начнем с двоичного алфавита и распределение вероятностей $Pr (1) = p {\ displaystyle \ Pr (1) = p}$ ${\ displaystyle \ Pr (1) = p}$ , $Pr (0) = 1 - p {\ displaystyle \ Pr (0) = 1-p}$ ${\ displaystyle \ Pr (0) = 1-p}$ . До позиции $x {\ displaystyle x}$ $x$ нам нужно приблизительно $p ⋅ x {\ displaystyle p \ cdot x}$ ${\ displaystyle p \ cdot x}$ аналоги нечетных чисел (для $s = 1 {\ displaystyle s = 1}$ $s = 1$ ). Мы можем выбрать это количество появлений как $⌈ x ⋅ p ⌉ {\ displaystyle \ lceil x \ cdot p \ rceil}$ ${\ displaystyle \ lceil x \ cdot p \ rceil}$ , получив $s = ⌈ (x + 1) ⋅ p ⌉ - ⌈ Икс ⋅ п ⌉ {\ Displaystyle s = \ lceil (x + 1) \ cdot p \ rceil - \ lceil x \ cdot p \ rceil}$ ${ \ Displaystyle s = \ lceil (x + 1) \ cdot p \ rceil - \ lceil x \ cdot p \ rceil}$ . Этот вариант называется 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

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

$C (x, s) {\ displaystyle C (x, s)}$ ${\ displaystyle 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 {\ displaystyle s = 0}$ ${\ displaystyle s = 0}$		0	1		2	3		4	5	6		7	8		9	10		11	12	13
$s = 1 {\ displaystyle s = 1}$ ${\ displaystyle s = 1}$	0			1			2				3			4			5				6

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

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

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

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

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

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

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

CDF ⁡ [s] = ∑ я < s f [ i ] = f [ 0 ] + ⋯ + f [ s − 1 ]. {\displaystyle \operatorname {CDF} [s]=\sum _{i

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

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

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)

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

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

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

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

Простой пример 4-х состояний ANS-автомата для 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 ∈ [L, 2 L - 1] {\ displaystyle x \ in [L, 2L-1]}$ ${\ displaystyle x \ in [L, 2L-1]}$ в таблицу, которая дает конечный автомат, избегая необходимости умножения.

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

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 определяется путем присвоения символа каждой позиции $[L, 2 L - 1] {\ displaystyle [L, 2L-1]}$ ${\ 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, LZNA, Draco, AV1). Он требует умножения, но более эффективен с точки зрения памяти и подходит для динамической адаптации распределений вероятностей.

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

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

См. Также

Ссылки

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

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

Аппаратные архитектуры с высокой пропускной способностью для асимметричных систем счисления энтропийное кодирование S. М. Наджмабади, З. Ван, Я. Баруд, С. Саймон, ISPA 2015
https://github.com/Cyan4973/FiniteStateEntropy Реализация tANS с конечной энтропией (FSE) Янн Колле
https://github.com/rygorous/ryg_rans Реализация rANS Фабианом Гизеном
https://github.com/jkbonfield/rans_static Быстрая реализация rANS и арифметического кодирования Джеймсом К. Бонфилдом
https://github.com/facebook/zstd/ Facebook Zstandard компрессор, автор Ян Колле (автор LZ4 )
https: // github.com / lzfse / lzfse LZFSE компрессор (LZ + FSE) Apple Inc.
компрессор CRAM 3.0 DNA (rANS заказа 1) (часть 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 rary
https://aomedia.googlesource.com/aom/+/master/aom_dsp реализация Alliance for Open Media
http://demonstrations.wolfram.com/DataCompressionUsingAsymmetricNumeralSystems/ Wolfram Demonstrations Project
http://gamma.cs.unc.edu/GST/ GST: GPU-декодируемые сверхсжатые текстуры
Понимание сжатия книга А. Хэки, К. МакАнлис