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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Асиметричні системи числення (англ. 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.

Посилання

[ред. | ред. код]