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

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

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

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

Концепція[ред. | ред. код]

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

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

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

Decoding:

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)

Encoding:

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

Джерела[ред. | ред. код]