Асимметричные системы счисления ( ANS ) [1] - это семейство методов энтропийного кодирования, введенных Ярославом (Jarek) Дудой [2] из Ягеллонского университета , которые используются для сжатия данных с 2014 года [3] из-за улучшенной производительности по сравнению с ранее используемыми методами, будучи до 30 раз быстрее. [4] ANS сочетает степень сжатия арифметического кодирования (которое использует почти точное распределение вероятностей) со стоимостью обработки, аналогичной стоимости кодирования Хаффмана . В табличном варианте ANS (tANS) это достигается путем построения конечного автомата. работать с большим алфавитом без умножения.
Среди прочего, ANS используется в компрессоре Facebook Zstandard [5] [6] (также используется, например, в ядре Linux, [7 ] операционной системе Android [8] , был опубликован как RFC 8478 для MIME [9] и HTTP [10]) ), в компрессоре Apple LZFSE [11], компрессоре Google Draco 3D [12] (используется, например, в формате универсального описания сцены Pixar [13] ) и компрессоре изображений PIK, [14] в компрессоре CRAM DNA [15] из утилит SAMtools , Компрессор Dropbox DivANS [16] и стандарт сжатия изображений следующего поколения JPEG XL [17] .
Основная идея - закодировать информацию в одно натуральное число. . В стандартной двоичной системе счисления мы можем добавить немного информации для добавив в конце что дает нам . Для энтропийного кодировщика это оптимально, если. ANS обобщает этот процесс для произвольных наборов символов. с сопутствующим распределением вероятностей . В ANS, если является результатом добавления информации из к , тогда . Эквивалентно,, где это количество бит информации, хранящейся в числе а также это количество битов, содержащихся в символе .
Для правила кодирования набор натуральных чисел разбивается на непересекающиеся подмножества, соответствующие различным символам - например, на четные и нечетные числа, но с плотностями, соответствующими распределению вероятностей символов для кодирования. Затем добавить информацию из символа в информацию, уже сохраненную в текущем номере , идем к номеру позиция -й выход из -е подмножество.
Есть альтернативные способы применения на практике - прямые математические формулы для шагов кодирования и декодирования (варианты uABS и rANS), или можно поместить все поведение в таблицу (вариант tANS). Ренормализация используется для предотвращения переход к бесконечности - передача накопленных битов в поток битов или из него.
Энтропийное кодирование
Предположим, что будет закодирована последовательность из 1000 нулей и единиц, что потребует 1000 бит для непосредственного сохранения. Однако, если каким-то образом известно, что он содержит только 1 ноль и 999 единиц, было бы достаточно кодировать позицию нуля, что требует только бит здесь вместо исходных 1000 бит.
Обычно такая длина последовательности, содержащие нули и те, с некоторой вероятностью , называются комбинациями . Используя приближение Стирлинга, получаем их асимптотическое число, равное
называется энтропией Шеннона .
Следовательно, чтобы выбрать одну такую последовательность, нам потребуется примерно биты. Это все еще биты, если однако он может быть и намного меньше. Например нам нужно только биты для .
Энтропийный кодер позволяет кодирование последовательности символов с использованием приблизительно энтропии Шеннона битов на символ. Например, ANS можно напрямую использовать для перечисления комбинаций: назначать разные натуральные числа каждой последовательности символов, имеющих фиксированные пропорции, почти оптимальным образом.
В отличие от комбинаций кодирования, это распределение вероятностей обычно варьируется в компрессорах данных. Для этого энтропию Шеннона можно рассматривать как средневзвешенное значение: символ вероятности. содержит биты информации. ANS кодирует информацию в одно натуральное число, интерпретируется как содержащий биты информации. Добавление информации из символа вероятности увеличивает это информационное содержание до . Следовательно, новый номер, содержащий обе данные, должен быть.
Основные понятия ВНС
Представьте, что есть некоторая информация, хранящаяся в натуральном числе. , например, как битовая последовательность его двоичного расширения. Чтобы добавить информацию из двоичной переменной, мы можем использовать функцию кодирования , который сдвигает все биты на одну позицию вверх и помещает новый бит в наименее значимую позицию. Теперь функция декодирования позволяет восстановить предыдущий и этот добавленный бит: . Мы можем начать с начальное состояние, затем используйте функция на последовательных битах конечной битовой последовательности для получения окончательного число, хранящее всю эту последовательность. Затем, используя функционировать несколько раз, пока позволяет получить битовую последовательность в обратном порядке.
Описанная выше процедура оптимальна для равномерного (симметричного) распределения вероятностей символов . ANS обобщает его, чтобы сделать его оптимальным для любого выбранного (асимметричного) распределения вероятностей символов:. Пока в приведенном выше примере был выбор между четным и нечетным , в ANS это четное / нечетное деление натуральных чисел заменено делением на подмножества с плотностями, соответствующими предполагаемому распределению вероятностей : до позиции , примерно вхождения символа .
Функция кодирования возвращает -й образ из такого подмножества, соответствующий символу . Предположение о плотности эквивалентно условию. Предполагая, что натуральное число содержит битовая информация, . Следовательно, символ вероятности кодируется как содержащий биты информации, как это требуется от энтропийных кодеров .
Единый двоичный вариант (uABS)
Начнем с двоичного алфавита и распределения вероятностей , . До позиции мы хотим примерно аналоги нечетных чисел (для ). Мы можем выбрать это количество появлений как, получающий . Этот вариант называется uABS и приводит к следующим функциям декодирования и кодирования: [18]
Расшифровка:
s = ceil (( x + 1 ) * p ) - ceil ( x * p ) // 0, если фракт (x * p) <1-p, иначе 1, если s = 0, то new_x = x - ceil ( x * p ) // D (x) = (new_x, 0), это то же самое, что new_x = floor (x * (1-p)), если s = 1, то new_x = ceil ( x * p ) // D (x) = (новый_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', начиная с . Первый приводит нас к , тогда к , тогда к , тогда к . Используя функцию декодирования на этом финале , мы можем получить последовательность символов. Используя для этого таблицу, в первой строке определяет столбец, затем непустая строка и записанное значение определяют соответствующий а также .
Варианты диапазона (rANS) и потоковая передача
Вариант диапазона также использует арифметические формулы, но позволяет работать с большим алфавитом. Интуитивно он делит набор натуральных чисел на размер. диапазонов и разделить каждый из них идентичным образом на поддиапазоны пропорций, заданных предполагаемым распределением вероятностей.
Начнем с квантования распределения вероятностей до знаменатель, где выбрано n (обычно 8-12 бит): для некоторых естественных числа (размеры поддиапазонов).
Обозначить , кумулятивная функция распределения:
Для обозначают функцию (обычно в таблице)
символ ( y ) = s такой, что 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 & маска ) - CDF [ s ], s )
Таким образом, мы можем закодировать последовательность символов в большое натуральное число x . Чтобы избежать использования арифметики с большими числами, на практике используются варианты потоков:путем перенормировки: отправка младших битов x в поток битов или из него (обычно L и b - степени двойки).
В варианте rANS x, например, 32-битный. Для 16-битной перенормировки, декодер при необходимости перезаполняет младшие значащие биты из потока битов:
если ( x < ( 1 << 16 )) x = ( x << 16 ) + read16bits ()
Табличный вариант (tANS)
Вариант tANS помещает все поведение (включая перенормировку) для в таблицу, которая дает конечный автомат без необходимости умножения.
Наконец, шаг цикла декодирования можно записать как:
t = таблица декодирования ( x ); х = т . newX + readBits ( т . nbBits ); // переход состояния writeSymbol ( т . символ ); // декодированный символ
Шаг цикла кодирования:
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 относительно дорого, поэтому оно в основном используется в статических ситуациях, обычно с некоторой схемой Лемпеля – Зива (например, ZSTD, LZFSE). В этом случае файл разбивается на блоки - для каждого из них независимо подсчитываются частоты символов, которые после аппроксимации (квантования) записываются в заголовок блока и используются как статическое распределение вероятностей для tANS.
Напротив, rANS обычно используется как более быстрая замена кодированию диапазона (например, CRAM , LZNA, Draco, [12] AV1 ). Он требует умножения, но более эффективен с точки зрения памяти и подходит для динамической адаптации распределений вероятностей.
Кодирование и декодирование ANS выполняются в противоположных направлениях, что делает его стеком для символов. Это неудобство обычно устраняется путем кодирования в обратном направлении, после чего декодирование может выполняться в прямом направлении. Для зависимости от контекста, как в модели Маркова , кодировщику необходимо использовать контекст с точки зрения последующего декодирования. Для адаптивности кодер должен сначала пойти вперед, чтобы найти вероятности, которые будут использоваться (спрогнозированы) декодером, и сохранить их в буфере, а затем закодировать в обратном направлении, используя буферизованные вероятности.
Конечное состояние кодирования требуется для начала декодирования, поэтому его необходимо сохранить в сжатом файле. Эти затраты могут быть компенсированы сохранением некоторой информации в исходном состоянии кодировщика. Например, вместо того, чтобы начинать с состояния «10000», начните с состояния «1 ****», где «*» - это некоторые дополнительные сохраненные биты, которые могут быть извлечены в конце декодирования. В качестве альтернативы это состояние можно использовать в качестве контрольной суммы, запустив кодирование с фиксированного состояния и проверив, является ли конечное состояние декодирования ожидаемым.
Патентный спор
Автор нового алгоритма ANS и его вариантов tANS и rANS специально намеревался сделать свою работу доступной в открытом доступе по альтруистическим причинам. Он не стремился получить от них прибыль и предпринял шаги, чтобы гарантировать, что они не станут «законным минным полем», не будут ограничиваться или извлекаться из других. В 2015 году Google опубликовал американский, а затем и мировой патент на «Кодирование смешанных логических токенов и коэффициентов». [19] В то время Google попросил профессора Дуду помочь ему со сжатием видео, поэтому он был хорошо осведомлен об этом домене, поскольку им помогал оригинальный автор.
Дуда не был доволен (случайно) обнаружением патентных намерений Google, учитывая, что он четко понимал, что хочет, чтобы это стало общественным достоянием, и помогал Google именно на этом основании. Впоследствии Дуда подал заявку от третьей стороны [20] в Патентное ведомство США с просьбой об отклонении. ВПТЗ США отклонило его заявку в 2018 году, и Google впоследствии отказался от патента. [21]
В июне 2019 года Microsoft подала заявку на патент под названием «Особенности кодирования и декодирования асимметричной системы счисления по диапазонам». [22] ВПТЗ США окончательно отклонило заявку 27 октября 2020 г. Однако 2 марта 2021 г. Microsoft подала пояснительную заявку ВПТЗ США, в которой говорилось: «Заявитель с уважением не согласен с отклонениями». [23] , стремясь отменить окончательный отказ в рамках программы «Пилотный проект 2.0 после окончательного рассмотрения». [24] Заявка в настоящее время все еще находится на рассмотрении, [25] поскольку ВПТЗ США не подтвердило, разрешит ли она подать апелляцию на отказ.
Смотрите также
- Энтропийное кодирование
- Кодирование Хаффмана
- Арифметическое кодирование
- Кодирование диапазона
- Компрессор Zstandard Facebook
- Компрессор LZFSE Apple
Рекомендации
- ^ Дж. Дуда, К. Тахбуб, Н. Дж. Гадил, Э. Дж. Делп, Использование асимметричных систем счисления в качестве точной замены кодирования Хаффмана , Симпозиум по кодированию изображений, 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 Compression For Btrfs & Squashfs Set for Linux 4.14, уже используется в Facebook , Phoronix, сентябрь 2017 г.
- ^ «Zstd в выпуске Android P» .
- ^ Стандартное сжатие Z и тип носителя приложения / zstd (стандарт электронной почты)
- ^ Параметры протокола передачи гипертекста (HTTP) , IANA
- ^ Apple открывает исходный код своего нового алгоритма сжатия LZFSE , InfoQ , июль 2016 г.
- ^ a b Библиотека сжатия Google Draco 3D
- ^ Google и Pixar добавляют сжатие Draco в универсальный формат описания сцены (USD).
- ^ Google PIK: новый формат изображений с потерями для Интернета
- ^ Спецификация формата CRAM (версия 3.0)
- ^ Создание лучшего сжатия вместе с DivANS
- ^ Ратушняк Александр; Вассенберг, Ян; Снейерс, Джон; Алакуйяла, Юрки; Вандевенн, Лоде; Версари, Лука; Обрик, Роберт; Забадка, Золтан; Ключников, Евгений; Комса, Юлия-Мария; Потемпа, Кшиштоф; Брюс, Мартин; Фиршинг, Мориц; Хасанова, Рената; Рууд ван Асселдонк; Букортт, Сами; Гомес, Себастьян; Фишбахер, Томас (2019). «Проект комитета системы кодирования изображений JPEG XL». arXiv : 1908.03565 [ eess.IV ].
- ^ Объяснение сжатия данных , Мэтт Махони
- ^ «Смешанное кодирование логических лексем и коэффициентов» . Google . Проверено 14 июня 2021 года .
- ^ «Протест Google» (PDF) . Институт теоретической физики - Ягеллонский университет в Кракове, Польша . Профессор Ярослав Дуда.
- ^ «После отказа Патентного ведомства Google пора отказаться от попытки патентного использования алгоритма общественного достояния» . ЭФФ.
- ^ «Особенности кодирования и декодирования диапазонов асимметричной системы счисления» . Проверено 14 июня 2021 года .
- ^ «Третий раз - вред? Microsoft пытается пройти дважды отвергнутый патент на сжатие через скептически настроенных экспертов» . Регистр . Проверено 14 июня 2021 года .
- ^ «Пилот 2.0 после окончательного рассмотрения» . Ведомство США по патентам и товарным знакам . Ведомство США по патентам и товарным знакам . Проверено 14 июня 2021 года .
- ^ «Особенности кодирования и декодирования диапазонов асимметричной системы счисления» . Проверено 14 июня 2021 года .
Внешние ссылки
- Аппаратные архитектуры с высокой пропускной способностью для энтропийного кодирования асимметричных систем счисления С. М. Наджмабади, З. Ван, Ю. Баруд, С. Саймон, 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/ Компрессор Zstandard в Facebook, автор Ян Колле (автор LZ4 )
- https://github.com/lzfse/lzfse Компрессор LZFSE (LZ + FSE) Apple Inc.
- Компрессор ДНК CRAM 3.0 (заказ 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 реализация Alliance for Open Media
- http://demonstrations.wolfram.com/DataCompressionUsingAsymmetricNumeralSystems/ Демонстрационный проект Wolfram
- http://gamma.cs.unc.edu/GST/ GST: декодируемые с помощью графического процессора сверхсжатые текстуры
- Книга A. Haecky, C. McAnlis " Понимание сжатия"