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

Асиметричні системи числення (англ. Asymmetric numeral systems, ANS) — сімейство методів ентропійного кодування, винайдених Ярославом (Яреком) Дудою в 2006^[1] на основі введеної ним концепції асиметричних систем числення.^[2]

З 2014-го року використовується для стиснення даних в ряді програм (наприклад, zstandard), оскільки ці методи за ступенем стиснення дають приблизно настільки ж гарне акуратне наближення до оптимального ентропійного кодування, як і арифметичне кодування, але мають вищу швидкодію, не поступаючись за швидкістю розпакування алгоритмам кодування Гаффмана; крім того, суттєвим є те, що ці методи не захищені патентами і вільні до використання, тому що створення і поширення вільної альтернативи арифметичному кодуванню було метою автора.

Концепція

Асиметричні системи числення є узагальненням позиційних систем числення, при яких різні символи можуть кодуватися різною кількістю цифр в залежності від попередніх цифр (символів).

В обчислювальній техніці прийнято представляти інформацію у вигляді потоку бітів, і додавання нової інформації — символу — полягає у приписуванні до числа в кінці відповідних коду символу цифр — нових молодших розрядів. При підході зі звичайними позиційними системами числення, будь-якому символу відповідає однакова кількість цифр. Це добре підходить в разі, коли ймовірність зустріти різні символи однакова.

Коли ймовірності зустріти різні символи розрізняються, для більш компактного запису інформації використовується ентропійне кодування. Так, в кодуванні Гаффмана різні символи можуть записуватися різною кількістю бітів. Однак при цьому символи кодуються цілим числом біт — що, зокрема, означає, що як би часто не зустрічався символ, для його кодування буде потрібно не менше одного біта.

Декодування (приклад мовою C#):

s = ceil((x+1)*p) - ceil(x*p)  // 0 if fract(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)

Кодування:

if s = 0 then new_x = ceil((x+1)/(1-p)) - 1 // C(x,0) = new_x
if s = 1 then new_x = floor(x/p)  // C(x,1) = new_x

Джерела

1. Duda, Jarek (2007). Optimal encoding on discrete lattice with translational invariant constrains using statistical algorithms (англ.). arXiv:0710.3861.
2. Duda, Jarek (2009). Asymmetric numeral systems (англ.). arXiv:0902.0271.

Посилання

• 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.» [Архівовано 25 червня 2018 у Wayback Machine.] 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.