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

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

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

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

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

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

Литература

• Duda, Jarek. arXiv preprint arXiv:0710.3861 (2007).

• Duda, Jarek. arXiv preprint arXiv:0902.0271 (2009).

• Duda, Jarek, Khalid Tahboub, Neeraj J. Gadgil, and Edward J. Delp. от 22 октября 2017 на Wayback Machine In Picture Coding Symposium (PCS), 2015, pp. 65-69. IEEE, 2015.

• Duda, Jarek. 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.