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

Материал данного пособия основан на публикации The use of asymmetric numeral systems as an accurate replacement for Huffman coding | IEEE Conference Publication | IEEE Xplore

Введение

ANS (Asymmetric Numeral Systems) – класс асимметричных систем счисления, которые используются для энтропийного кодирования сообщений с целью их сжатия (компрессии), т.е. снижения избыточности и, соответственно, занимаемого объема. Сжатие при энтропийном кодировании достигается за счет различия в частотах встречаемости символов сообщения (их вероятностей).

Вариантами энтропийного кодирования являются коды Хаффмана, коды Шеннона-Фано, арифметические коды и разного рода префиксные неравномерные коды (Райса, Голомба, Элиаса, …). ANS кодирование было открыто в результате переосмысления арифметического кодирования, и является его изнанкой. В определенном смысле ANS проще арифметического кодирования, как для понимания, так и для реализации, хотя и не свободно от ограничений, как и любой алгоритм…

ANS кодирование устроено так, что символы sis_i экономно кодируются в длинное целое число xx. Экономность достигается за счет знания вероятности pip_i кодируемого символа sis_i, при этом обновление (рост) числа происходит по следующему правилу xx/pi.x \leftarrow x/p_i. При таком правиле менее вероятным символам соответствует больший прирост xx и, соответственно, большее количество добавленных цифр. Наиболее вероятным символам соответствует меньший прирост xx (время от времени xx вообще не изменяется), что вкупе с высокой частотой встречаемости этих символов и обеспечивает экономность кодирования – итоговое сжатие.

Рассмотренное правило трансформации числа xx является идеальным, формирующим выходной поток с нулевой избыточностью, т.е. с наибольшим сжатием. Действительно, логарифмируя отношение двух xx – до и после применения правила, – убеждаемся, что дополнительное количество информации (дельта) аккурат соответствует собственной информации символа ΔI=log1/pi,\Delta I=\log 1/p_i, как она определена Клодом Шенноном. Энтропия (бит/символ) кодированного таким способом сообщения XX равна энтропии источника SS. Избыточность (redundancy) после кодирования определяется как разность этих энтропий R=H(X)H(S)0.R=H(X)-H(S) \geq 0.

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

Добавление информации dd в некоторое число xx, записанное в позиционной системе счисления по основанию bb и имеющее длину nn, может быть сделано двояко xbx+d,x \leftarrow bx + d, xx+dbn. x \leftarrow x + db^n.

Здесь первому случаю соответствует добавление цифры dd в младший разряд, а второму – в старший. Второй случай, как более сложный, соответствует логике арифметического кодирования, а первый – логике ANS.

“Чистый” ANS

Данный тип кодирования очень прост, и легко реализуется на любом языке программирования высокого уровня. Легкость вуалируется встроенной арифметикой целых чисел произвольной точности (big integer arithmetic).

Рассмотрим пример трансформации числа xx двоичным источником, символы которого равновероятные: p0=1/2p_0=1/2 и p1=1/2p_1=1/2.

Используя идеальное преобразование (см. введение), прямое (т.е. кодирующее) преобразование логично оформить следующим образом x=2x+0, для бита 0,x'=2x+0, \text{~для бита~} 0, x=2x+1, для бита 1.x'=2x+1, \text{~для бита~} 1.

Получается, что бит 00 переводит текущее xx в четное число, а бит 11 – в нечетное, что обеспечивает однозначность работы декодера. Видно, что помимо масштабирования вероятностью требуется вводить определенный сдвиг.

Обратное (декодирующее) преобразование выводится довольно-таки просто s=xmod  2,s=x' \mod 2, x=x/2.x=\lfloor x'/2 \rfloor.

Здесь ss – декодированный бит.

Для понимания логики определения величины сдвига рассмотрим двоичный источник с “перекошенными” вероятностями: p0=1/4p_0=1/4 и p1=3/4p_1=3/4. Для бита 00 напрашивается преобразование типа x=4x,x'=4x, а для бита 11 – типа x=4x/3x'=4x/3

Если в первом случае все нормально (для бита 00 числа xx будут кратны 44), то второй случай требует приведения к целому типу x=4x/3,x'=4 \lfloor x/3 \rfloor,

и последующей модификации, обеспечивающей однозначность декодирования. Величина x/3\lfloor x/3 \rfloor имеет период 33, и наращивает 11 только через этот период, т.е. имеет место эффект ограничения, что делает обратное преобразование неоднозначным. Для исключения этого факта вводят корректор x=4x/3+xmod  3,x'=4 \lfloor x/3 \rfloor + x \mod 3,

фактически определяющий уникальный номер элемента в группе, образованной рассмотренным периодом. Таким образом, преобразование линеаризуется, образуя ступенчатую функцию. Однако, подставляя в два преобразования x=0x=0, замечаем, что множества пересекаются. Фактически, требуется ввести сдвиг. Здесь важен порядок символов алфавита. Пусть порядок таков: 00, 11. Первому символу всегда соответствует нулевой сдвиг: c0=0c_0=0. Остается определить сдвиг для второго символа. В рассматриваемом случае вероятности имеют общий знаменатель L=4L=4, поэтому частота бита 00 равна f0=1f_0=1, а бита 11f1=3f_1=3, и для того, чтобы множества кодера и декодера не пересекались, сдвиг для бита 11 следует выбрать равным частоте предыдущего символа с1=f0=1с_1=f_0=1, а в общем случае – накопленной частоте ck=i<kfi.c_k=\sum_{i<k}{f_i}.

Результатом проведенного анализа является следующая пара преобразований x=4x,                                        для бита 0,x'=4x, \text{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~для бита } 0, x=4x/3+(xmod  3)+1, для бита 1.x'=4 \lfloor x/3 \rfloor + (x \mod 3) + 1, \text{ для бита } 1.

Декодированный бит – результат сравнения остатка с нулем s=1, если   (xmod  4)0,s=1, \text{~если~~~} (x' \mod 4) \neq 0, s=0, если   (xmod  4)=0,s=0, \text{~если~~~} (x' \mod 4) = 0, после чего следует обратное преобразование x=x/4,                                       если  s=0,x=x'/4, \text{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~если~~} s=0, x=3x/4+(xmod  4)1, если  s=1.x=3 \lfloor x'/4 \rfloor + (x' \mod 4) -1, \text{~если~~} s=1.

Для вывода обратного преобразования величину xx (например для s=1s=1) следует представить в виде x=3q+r,0r<3,x=3q + r, 0 \leq r<3, и подставить в соответствующее прямое преобразование x=4q+(r+1),x'=4q +(r+1), выразив оттуда qq и (r+1)<4(r+1)<4 и подставив их обратно x=3x/4+(xmod  4)1.x=3 \lfloor x'/4 \rfloor + (x' \mod 4) - 1.

В общем случае пара ANS преобразований выглядит следующим образом x=Lx/fs+(xmod  fs)+cs,x'=L \lfloor x/f_s \rfloor + (x \mod f_s) + c_s, x=fsx/L+(xmod  L)cs.x=f_s \lfloor x'/L \rfloor + (x' \mod L) - c_s.

Видим, что частота fsf_s и нормирующий множитель LL меняются местами, а у накопленной частоты csc_s меняется знак.

Накопленную частоту называют кумулятивной частотой cs=i<sfi,c_s=\sum_{i<s}{f_i}, а нормирующий множитель – базой ifi=L=сM.\sum_{i} {f_i} = L = с_M.

Здесь MM – число символов в алфавите. Напомним, что важен порядок символов в алфавите, который должен быть одним и тем же как в кодере, так и в декодере!

Для лучшего понимания формулы прямого преобразования следует нарисовать схему распределения мест (т.е. величины xx') для некоторого распределения частот fif_i:

f0=3:ooof_0=3:\text{ooo}
f1=5:      ooooof_1=5:~~~~~~\text{ooooo}
f2=2:                oof_2=2:~~~~~~~~~~~~~~~~\text{oo}
f3=6:                    oooooof_3=6:~~~~~~~~~~~~~~~~~~~~\text{oooooo}

Здесь показан один период L=16L=16.

Для частоты f0=3f_0=3 выделено три первоначальных позиции (группа 00), для частоты f1=5f_1=5 следующие 55 позиций (группа 11), для частоты f2=2f_2=2 следующие две (группа 22), и для частоты f3=6f_3=6 следующие 66 (группа 33). Далее эта схема повторяется (копируется) вправо, образуя период L=16L=16. Кумулятивная частота csc_s задает позицию группы, слагаемое (xmod  fs)(x \mod f_s) – позицию в группе, а слагаемое x/fs\lfloor x/f_s \rfloor – индекс периодической компоненты схемы.

Цикл ANS декодирования включает в себя четыре этапа

  1. Вычисление модуля xL=xmod  Lx_L=x' \mod L
  2. Поиск индекса ii, дающего выполнение неравенства cixL<ci+1.c_i \leq x_L < {c}_{i+1}.
  3. Выдача символа sis_i в выходной поток
  4. Применение обратного ANS преобразования xxx' \rightarrow x с присваиванием x=xx'=x и возвратом к первому шагу.

Поиск индекса ii может быть выполнен разными методами

Практика такова, что чаще используют либо табличный метод (тогда обычно L=65536L=65536), либо метод alias; однако, для малых алфавитов (M<8M<8) линейный поиск очень даже неплох, поэтому, в итоге, лучший по скорости декомпрессии результат может дать гибридный кодек. Бинарный же поиск обычно проигрывает остальным, несмотря на логарифмическую сложность. Это вызвано тем, что распределение величины xmod  Lx' \mod L неравномерное, смещенное в область малых величин, что особенно выражено для малых алфавитов MM.

В целом, метод alias устроен так, что формируется прямоугольник шириной MM и площадью LL, в котором максимально плотно упакованы частоты символов. Это требует делимости L/ML/M, но т.к. LL обычно берут как степень 22, то и MM требуется привести к ближайшей степени 22, заполняя алфавит dummy-символами. Степени 22 берутся для ускорения процесса декомпрессии, и это уже является прерогативой range ANS (rANS) кодека, нежели “чистого” ANS.

Упражнение 1

Заполнить таблицу соответствия xxx \Leftrightarrow x' для рассмотренного распределения частот, образуя два периода L=16L=16, т.е. вплоть до x=31x=31.


Упражнение 2

Анализируя рассмотренный случай p0=1/4p_0=1/4 и p1=3/4p_1=3/4, доказать формулу обратного ANS преобразования в общем случае, используя формулу прямого преобразования.


Упражнение 3

Используя рассмотренный случай p0=1/4p_0=1/4 и p1=3/4p_1=3/4, начиная с x=1x=1 определить множество xx для 1616 подряд идущих нулевых битов, а также для 1616 подряд идущих единичных битов. Проанализировать отношение соседних xx.


Алгоритм смотри на nawww83/ans: ANS codec for lossless compression (github.com)

Range ANS – rANS

Данный тип кодирования (интервальный, range ANS, rANS) является результатом оптимизации “чистого” ANS кодирования в плане возможности использования ограниченных по разрядности чисел, что согласуется с требованиями аппаратного обеспечения, где разрядность кратна степеням 22, начиная с 88 бит. Однако, в этом нет особой необходимости, если имеющаяся библиотека целочисленной арифметики произвольной точности устраивает по производительности и потреблению памяти, и, возможно, другим критериям: лицензия и т.п.

Для реализации идеи ограничения разрядности требуется выбрать коэффициент b2b \geq 2, определяющий наибольшее значение xx в процессе кодирования/декодирования x<bL.x < bL.

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

Для понимания rANS выпишем формулы прямого и обратного ANS преобразований x=Lx/fs+(xmod  fs)+cs,x'=L \lfloor x/f_s \rfloor + (x \mod f_s) + c_s, x=fsx/L+(xmod  L)cs.x=f_s \lfloor x'/L \rfloor + (x' \mod L) - c_s.

Если перед прямым преобразованием обеспечить x<bfsx<bf_s, то преобразованный xxx \rightarrow x' будет аккурат ограничен выбранным ранее условием x<bLx'<bL. Действительно, полагая x=bfs1x=bf_s-1, получаем для любого ss x=L(b1)+(fs1)+i<sfibLL+L1<bL.x'=L(b-1)+(f_s-1)+\sum_{i<s}{f_i} \leq bL-L+L-1<bL.

Обеспечение x<bfsx<bf_s делается последовательным делением xx на bb и записью остатка от деления в выходной поток (bb-base digit stream).

Однако, гарантии ограниченности мало: требуется обеспечить однозначность отображения xxx' \rightarrow x для верного декодирования. Для этого следует убедиться в полноте. Здесь лучше рассмотреть пример: f0=7f_0=7, f1=2f_1=2, L=9L=9. При b=2b=2 имеем желаемый диапазон (range) xx[0,2L).x' \geq x \in [0, 2L).

Для кодируемого бита s=0s=0, c0=0c_0=0 отображение таково:
x= 0,1,2,3,4,5,6,7, 8,  9, 10,11,12,13x=~0, 1, 2, 3, 4, 5, 6, 7, ~8, ~~9, ~10, 11, 12, 13
x=0,1,2,3,4,5,6,9,10,11,12,13,14,15x'=0, 1, 2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 14, 15

Для кодируемого бита s=1s=1, c1=7c_1=7 отображение таково:
x= 0,1, 2,  3x=~0, 1, ~2, ~~3
x=7,8,16,17x'=7, 8, 16, 17

Видим, что таблица однозначная, т.е. множества xx' для разных ss не пересекаются.

Упражнение 1

Вычислить xmod  Lx' \mod L и связать эти остатки с номерами позиций символов 00 и 11.


Глядя на рассмотренные отображения, можно заметить, что несколько более выгодным в плане коэффициента сжатия является вариант с сортировкой символов по частоте встречаемости, когда наиболее часто встречающимся символам соответствует малый индекс ss. В этом случае из-за того, что c0=0c_0=0, значение x<f0x<f_0 при кодировании последовательно идущего символа s=0s=0 не изменяется.


На практике минимальное xx' перед применением обратного преобразования выбирают равным LL. Наращивание xx' делается чтением входного потока xbx+next(input)x' \leftarrow bx' + \text{next(input)} до тех пор, пока не выполнится xLx' \geq L. Если входной поток считать бесконечным, то это условие рано или поздно выполнится. В этом случае xfs1x \geq f_s \geq 1 (нулевые частоты недопустимы). Это согласуется с требованием x<bfsx<bf_s, потому что при минимальном нарушении x=bfsx=bf_s деление на bb даст аккурат x=fsx=f_s. Такой режим работы можно назвать установившимся режимом; в нем всегда выполняется биекция [fs,bfs)[L,bL),  s[0,M).[f_s, bf_s) \Leftrightarrow [L, bL), ~~\forall s \in [0, M).

Заметим, что интервалы слева объединяются для всех перечисленных ss, т.е. для каждого интервала найдется свое место в [L,bL)[L, bL), которое не пересекается с местами других интервалов.

Упражнение 2

Для рассмотренного ранее примера, в котором f0=7f_0​=7, f1=2f_1=2, L=9L=9, b=2b=2, расписать [fs,bfs)[L,bL)[f_s, bf_s) \Leftrightarrow [L, bL) в явном виде.


В начале кодирования обычно полагают x=1x=1, чтобы не записывать лишних символов, потому что 11 всегда меньше bfsbf_s.

Если входной поток при декодировании закончился, то текущий символ декодируют в соответствии с числом повторов этого символа, которое, естественно, передается декодеру отдельно, т.е. в заголовке. Заметим, что декодирование делается в обратном порядке, т.е. от последнего символа исходного сообщения к первому, поэтому число повторов определяет количество повторов первого символа; вместо числа повторов можно передавать общую длину сообщения, которая теоретически займет несколько больше места в заголовке.

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

Слабым местом ANS кодирования является медленность операции деления на частоты fsf_s по сравнению с остальными операциями ANS кодирования, поэтому часто используют существенно более быстрый вариант ANS – табличный ANS (tANS).

Частичным недостатком ANS является необходимость хранения достаточно больших частот (часто 44 байта на частоту) в заголовке. Тот же код Хаффмана требует хранения лишь длин кодовых векторов, которые пропорциональны логарифму частоты и могут занимать меньше места; по этой причине в некоторых случаях код Хаффмана с точки зрения коэффициента сжатия предпочтительнее ANS (когда алфавит сравнительно большой и вероятности символов не превышают 1/21/2).

Эти недостатки частично преодолимы, если частоты округлить до степеней 22, однако, это изменит итоговый коэффициент сжатия – в какую сторону – вопрос на самом деле открытый…

Алгоритм смотри на nawww83/rans: Range ANS codec for lossless compression (github.com)

Table ANS – tANS

Упражнение 1

Разобравшись с материалом данного пособия, используя статью The use of asymmetric numeral systems as an accurate replacement for Huffman coding | IEEE Conference Publication | IEEE Xplore, https://arxiv.org/pdf/1311.2540.pdf, разобраться с табличным ANS, реализовав на любом удобном языке программирования tANS кодек.


Упражнение 2

Убедиться в однозначности кодирования-декодирования реализованным tANS кодеком, написав тест, проверяющий кодек с использованием случайных данных с геометрическим распределением. Длину блока NN задавать случайно, равномерно на отрезке [1,65536][1, 65536].

Приложение А – Нормализация частот

Пусть символы 0s<M0 \leq s < M некоторого сообщения длиной NN имеют частоты fs>0f_s>0, т.е. верно sfs=N.\sum_{s} f_s = N. Тогда задавая базу (общий знаменатель) LL и полагая кумулятивную частоту для первого символа в алфавите равной нулю, т.е. c0=0c_0=0, процедуру нормализации можно осуществить так. Для 1sM1 \leq s \leq M последовательно выполнить:

Сформированные частоты wsw_s и будут искомыми нормированными частотами, причем верно sws=qM=L.\sum_{s} w_s = q_M = L.

Если в процессе нормализации хотя бы одна частота wsw_s обнулилась, то процесс следует остановить с ошибкой нормализации.

Чтобы гарантированно избежать ошибок нормализации, базу LL следует выбирать исходя из следующего неравенства L>Nminfs.{L} > {\left \lfloor { {N} \over {\min f_s} } \right \rfloor}.

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

Упражнение 1

Добавить процедуру нормализации частот в ANS (rANS, tANS) кодек.

Novikov Anatolii, updated 17/05/2021

Written with StackEdit.