Asymmetric numeral systems

Asymmetric numeral systems (ANS, от «асимметричные системы счисления») — семейство методов энтропийного кодирования, изобретённых Ярославом (Яреком) Дудой в 2006 на основе введённой им концепции асимметричных систем счисления. С 2014 года используется для сжатия данных в ряде программ, так как эти методы по степени сжатия дают примерно столь же хорошее аккуратное приближение к оптимальному энтропийному кодированию, как и арифметическое кодирование, но обладают более высоким быстродействием, не уступая по скорости распаковки алгоритмам кодирования Хаффмана; кроме того, существенным является то, что эти методы не защищены патентами и свободны к использованию, так как создание и распространение свободной альтернативы арифметическому кодированию являлось целью автора.

Концепция асимметричных систем счисления

Асимметричные системы счисления являются обобщением позиционных систем счисления, при которых разные символы могут кодироваться разным количеством цифр в зависимости от предшествующих цифр (символов).

В вычислительной технике принято представлять информацию в виде потока битов, и добавление новой информации — символа — происходит путём приписывания к числу в конце соответствующих коду символа цифр — новых младших разрядов. При подходе с обычными позиционными системами счисления любому символу соответствует одинаковое количество цифр. Это хорошо подходит в случае, когда вероятность встретить разные символы одинакова.

Когда вероятности встретить разные символы различаются, для более компактной записи информации используется энтропийное кодирование. Так, в кодировании Хаффмана разные символы могут записываться разным количеством битов. Однако при этом символы кодируются целым количеством битов — что, в частности, означает, что как бы часто ни встречался бы символ, для его кодирования потребуется не менее одного бита.

В асимметричных системах счисления кодирование символа зависит не только от того, что это за символ, но и от предшествующего контекста, отражаемого состоянием. Количество требующихся цифр остаётся целым, но оно меняется и может быть даже нулевым.

Литература

• Duda, Jarek. «Optimal encoding on discrete lattice with translational invariant constrains using statistical algorithms.» arXiv preprint arXiv:0710.3861 (2007).

• Duda, Jarek. «Asymmetric numeral systems» arXiv preprint arXiv:0902.0271 (2009).

• Duda, Jarek, Khalid Tahboub, Neeraj J. Gadgil, and Edward J. Delp. «The use of asymmetric numeral systems as an accurate replacement for huffman coding.» Архивная копия от 22 октября 2017 на Wayback Machine In Picture Coding Symposium (PCS), 2015, pp. 65-69. IEEE, 2015.

• Duda, Jarek. «Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding.» arXiv preprint arXiv:1311.2540 (2013).

• Najmabadi, Seyyed Mahdi, Zhe Wang, Yousef Baroud, and Sven Simon. «High throughput hardware architectures for asymmetric numeral systems entropy coding.» In Image and Signal Processing and Analysis (ISPA), 2015 9th International Symposium on, pp. 256—259. IEEE, 2015.