Асиметричні системи числення (англ. Asymmetric numeral systems, ANS) — сімейство методів ентропійного кодування, винайдених Ярославом (Яреком) Дудою в 2006 на основі введеної ним концепції асиметричних систем числення.
З 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
Джерела
Посилання
- 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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Asimetrichni sistemi chislennya angl Asymmetric numeral systems ANS simejstvo metodiv entropijnogo koduvannya vinajdenih Yaroslavom Yarekom Dudoyu v 2006 na osnovi vvedenoyi nim koncepciyi asimetrichnih sistem chislennya Z 2014 go roku vikoristovuyetsya dlya stisnennya danih v ryadi program napriklad zstandard oskilki ci metodi za stupenem stisnennya dayut priblizno nastilki zh garne akuratne nablizhennya do optimalnogo entropijnogo koduvannya yak i arifmetichne koduvannya ale mayut vishu shvidkodiyu ne postupayuchis za shvidkistyu rozpakuvannya algoritmam koduvannya Gaffmana krim togo suttyevim ye te sho ci metodi ne zahisheni patentami i vilni do vikoristannya tomu sho stvorennya i poshirennya vilnoyi alternativi arifmetichnomu koduvannyu bulo metoyu avtora KoncepciyaAsimetrichni sistemi chislennya ye uzagalnennyam pozicijnih sistem chislennya pri yakih rizni simvoli mozhut koduvatisya riznoyu kilkistyu cifr v zalezhnosti vid poperednih cifr simvoliv V obchislyuvalnij tehnici prijnyato predstavlyati informaciyu u viglyadi potoku bitiv i dodavannya novoyi informaciyi simvolu polyagaye u pripisuvanni do chisla v kinci vidpovidnih kodu simvolu cifr novih molodshih rozryadiv Pri pidhodi zi zvichajnimi pozicijnimi sistemami chislennya bud yakomu simvolu vidpovidaye odnakova kilkist cifr Ce dobre pidhodit v razi koli jmovirnist zustriti rizni simvoli odnakova Koli jmovirnosti zustriti rizni simvoli rozriznyayutsya dlya bilsh kompaktnogo zapisu informaciyi vikoristovuyetsya entropijne koduvannya Tak v koduvanni Gaffmana rizni simvoli mozhut zapisuvatisya riznoyu kilkistyu bitiv Odnak pri comu simvoli koduyutsya cilim chislom bit sho zokrema oznachaye sho yak bi chasto ne zustrichavsya simvol dlya jogo koduvannya bude potribno ne menshe odnogo bita Dekoduvannya priklad movoyu C s ceil x 1 p ceil x p 0 if fract x p lt 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 Koduvannya 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 xDzherelaDuda Jarek 2007 Optimal encoding on discrete lattice with translational invariant constrains using statistical algorithms angl arXiv 0710 3861 Duda Jarek 2009 Asymmetric numeral systems angl arXiv 0902 0271 PosilannyaDuda Jarek Khalid Tahboub Neeraj J Gadgil and Edward J Delp The use of asymmetric numeral systems as an accurate replacement for huffman coding 22 zhovtnya 2017 u 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 chervnya 2018 u 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