{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T04:18:21Z","timestamp":1770956301731,"version":"3.50.1"},"reference-count":43,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2023,4,17]],"date-time":"2023-04-17T00:00:00Z","timestamp":1681689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Polish National Science Center (NCN)","doi-asserted-by":"publisher","award":["2018\/31\/B\/ST6\/03003"],"award-info":[{"award-number":["2018\/31\/B\/ST6\/03003"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Source coding has a rich and long history. However, a recent explosion of multimedia Internet applications (such as teleconferencing and video streaming, for instance) renews interest in fast compression that also squeezes out as much redundancy as possible. In 2009 Jarek Duda invented his asymmetric numeral system (ANS). Apart from having a beautiful mathematical structure, it is very efficient and offers compression with a very low coding redundancy. ANS works well for any symbol source statistics, and it has become a preferred compression algorithm in the IT industry. However, designing an ANS instance requires a random selection of its symbol spread function. Consequently, each ANS instance offers compression with a slightly different compression ratio. The paper investigates the compression optimality of ANS. It shows that ANS is optimal for any symbol sources whose probability distribution is described by natural powers of 1\/2. We use Markov chains to calculate ANS state probabilities. This allows us to precisely determine the ANS compression rate. We present two algorithms for finding ANS instances with a high compression ratio. The first explores state probability approximations in order to choose ANS instances with better compression ratios. The second algorithm is a probabilistic one. It finds ANS instances whose compression ratios can be made as close to the best ratio as required. This is done at the expense of the number \u03b8 of internal random \u201ccoin\u201d tosses. The algorithm complexity is O(\u03b8L3), where L is the number of ANS states. The complexity can be reduced to O(\u03b8Llog2L) if we use a fast matrix inversion. If the algorithm is implemented on a quantum computer, its complexity becomes O(\u03b8(log2L)3).<\/jats:p>","DOI":"10.3390\/e25040672","type":"journal-article","created":{"date-parts":[[2023,4,18]],"date-time":"2023-04-18T02:30:03Z","timestamp":1681785003000},"page":"672","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["The Compression Optimality of Asymmetric Numeral Systems"],"prefix":"10.3390","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1917-6466","authenticated-orcid":false,"given":"Josef","family":"Pieprzyk","sequence":"first","affiliation":[{"name":"Institute of Computer Science, Polish Academy of Sciences, 01-248 Warsaw, Poland"},{"name":"Data61, CSIRO, Sydney, NSW 2122, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9559-809X","authenticated-orcid":false,"given":"Jarek","family":"Duda","sequence":"additional","affiliation":[{"name":"Institute of Computer Science and Computer Mathematics, Jagiellonian University, 30-348 Cracow, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5145-9220","authenticated-orcid":false,"given":"Marcin","family":"Paw\u0142owski","sequence":"additional","affiliation":[{"name":"Institute of Computer Science and Computer Mathematics, Jagiellonian University, 30-348 Cracow, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6353-8359","authenticated-orcid":false,"given":"Seyit","family":"Camtepe","sequence":"additional","affiliation":[{"name":"Data61, CSIRO, Sydney, NSW 2122, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0487-0615","authenticated-orcid":false,"given":"Arash","family":"Mahboubi","sequence":"additional","affiliation":[{"name":"School of Computing and Mathematics, Charles Sturt University, Port Macquarie, NSW 2444, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3349-8645","authenticated-orcid":false,"given":"Pawe\u0142","family":"Morawiecki","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Polish Academy of Sciences, 01-248 Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,4,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1002\/j.1538-7305.1948.tb00917.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Sys. Tech. J."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1098","DOI":"10.1109\/JRPROC.1952.273898","article-title":"A Method for the Construction of Minimum-Redundancy Codes","volume":"40","author":"Huffman","year":"1952","journal-title":"Proc. IRE"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1109\/T-C.1974.223784","article-title":"Discrete Cosine Transform","volume":"C-23","author":"Ahmed","year":"1974","journal-title":"IEEE Trans. Comput."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1117\/1.JEI.27.4.040901","article-title":"JPEG-1 standard 25 years: Past, present, and future reasons for a success","volume":"27","author":"Hudson","year":"2018","journal-title":"J. Electron. Imaging"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1231","DOI":"10.1109\/TASL.2010.2087755","article-title":"On Properties, Relations, and Simplified Implementation of Filter Banks in the Dolby Digital (Plus) AC-3 Audio Coding Standards","volume":"19","author":"Britanak","year":"2011","journal-title":"IEEE Trans. Audio Speech Lang. Process."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1121\/1.1907853","article-title":"Masking by Tones vs Noise Bands","volume":"31","author":"Ehmer","year":"1959","journal-title":"J. Acoust. Soc. Am."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Kochanek, J., Lansky, J., Uzel, P., and Zemlicka, M. (2008, January 4\u20136). The new statistical compression method: Multistream compression. Proceedings of the 2008 First International Conference on the Applications of Digital Information and Web Technologies (ICADIWT), Ostrava, Czech Republic.","DOI":"10.1109\/ICADIWT.2008.4664366"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1109\/TIT.1982.1056559","article-title":"A simple general binary source code (Corresp.)","volume":"28","author":"Langdon","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1147\/rd.282.0135","article-title":"An Introduction to Arithmetic Coding","volume":"28","author":"Langdon","year":"1984","journal-title":"IBM J. Res. Dev."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1147\/rd.203.0198","article-title":"Generalized Kraft Inequality and Arithmetic Coding","volume":"20","author":"Rissanen","year":"1976","journal-title":"IBM J. Res. Dev."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1145\/322344.322346","article-title":"Data compression via textual substitution","volume":"29","author":"Storer","year":"1982","journal-title":"J. ACM"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Welch (1984). A Technique for High-Performance Data Compression. Computer, 17, 8\u201319.","DOI":"10.1109\/MC.1984.1659158"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable-rate coding","volume":"24","author":"Ziv","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1109\/TCOM.1984.1096090","article-title":"Data Compression Using Adaptive Coding and Partial String Matching","volume":"32","author":"Cleary","year":"1984","journal-title":"IEEE Trans. Commun."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1109\/PROC.1967.5493","article-title":"Results of a prototype television bandwidth compression scheme","volume":"55","author":"Robinson","year":"1967","journal-title":"Proc. IEEE"},{"key":"ref_16","unstructured":"Duda, J. (2009). Asymmetric Numeral Systems. arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Grumbling, E., and Horowitz, M. (2019). Quantum Computing: Progress and Prospects, The National Academies Press.","DOI":"10.17226\/25196"},{"key":"ref_18","unstructured":"Petz, D. (2008). Theoretical and Mathematical Physics, Springer."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/s11128-022-03609-3","article-title":"An improved quantum network communication model based on compressed tensor network states","volume":"21","author":"Zhang","year":"2022","journal-title":"Quantum Inf. Process."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"160504","DOI":"10.1103\/PhysRevLett.113.160504","article-title":"Quantum Data Compression of a Qubit Ensemble","volume":"113","author":"Rozema","year":"2014","journal-title":"Phys. Rev. Lett."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"5841","DOI":"10.1038\/s41598-022-09881-8","article-title":"Implementation of quantum compression on IBM quantum computers","volume":"12","author":"Pivoluska","year":"2022","journal-title":"Sci. Rep."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1051","DOI":"10.1007\/s10207-022-00597-4","article-title":"ANS-based Compression and Encryption with 128-bit Security","volume":"21","author":"Camtepe","year":"2022","journal-title":"Int. J. Inf. Secur."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Dube, D., and Yokoo, H. (2019, January 7\u201312). Fast Construction of Almost Optimal Symbol Distributions for Asymmetric Numeral Systems. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849430"},{"key":"ref_24","unstructured":"Townsend, J., Bird, T., and Barber, D. (2023, April 13). Practical Lossless Compression with Latent Variables Using Bits Back Coding 2019, Available online: http:\/\/xxx.lanl.gov\/abs\/1901.04866."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"01001","DOI":"10.1051\/epjconf\/202024501001","article-title":"Fast and Efficient Entropy Compression of ALICE Data using ANS Coding","volume":"Volume 245","author":"Lettrich","year":"2020","journal-title":"EPJ Web of Conferences"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Ko, H.H. (2021). Enhanced Binary MQ Arithmetic Coder with Look-Up Table. Information, 12.","DOI":"10.3390\/info12040143"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1109\/TCSVT.2003.815173","article-title":"Context-based adaptive binary arithmetic coding in the H.264\/AVC video compression standard","volume":"13","author":"Marpe","year":"2003","journal-title":"IEEE Trans. Circuits Syst. Video Technol."},{"key":"ref_28","unstructured":"Giesen, F. (2023, April 13). Interleaved Entropy Coders, Available online: http:\/\/xxx.lanl.gov\/abs\/1402.3392."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1007\/s11265-018-1421-4","article-title":"An architecture for asymmetric numeral systems entropy decoder-a comparison with a canonical Huffman decoder","volume":"91","author":"Najmabadi","year":"2019","journal-title":"J. Signal Process. Syst."},{"key":"ref_30","unstructured":"Collet, Y., and Kucherawy, M. (2023, April 13). Zstandard Compression and the \u2018application\/zstd\u2019 Media Type. RFC 8878. Available online: https:\/\/www.rfc-editor.org\/info\/rfc8878."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Alakuijala, J., Van Asseldonk, R., Boukortt, S., Bruse, M., Com\u0219a, I.M., Firsching, M., Fischbacher, T., Kliuchnikov, E., Gomez, S., and Obryk, R. (2019, January 12\u201315). JPEG XL next-generation image compression architecture and coding tools. Proceedings of the Applications of Digital Image Processing XLII, San Diego, CA, USA.","DOI":"10.1117\/12.2529237"},{"key":"ref_32","unstructured":"Duda, J. (2013). Asymmetric numeral systems as close to capacity low state entropy coders. CoRR, Available online: http:\/\/xxx.lanl.gov\/abs\/1311.2540."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"3859","DOI":"10.1109\/TIFS.2021.3096026","article-title":"Compcrypt\u2014Lightweight ANS-Based Compression and Encryption","volume":"16","author":"Camtepe","year":"2021","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Br\u00e9maud, P. (2020). Markov Chains, Springer International Publishing.","DOI":"10.1007\/978-3-030-45982-6"},{"key":"ref_35","unstructured":"Seabrook, E., and Wiskott, L. (2023, April 13). A Tutorial on the Spectral Theory of Markov Chains 2022, Available online: http:\/\/xxx.lanl.gov\/abs\/2207.02296."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Haggstrom, O. (2002). Finite Markov Chains and Algorithmic Applications, London Mathematical Society.","DOI":"10.1017\/CBO9780511613586"},{"key":"ref_37","unstructured":"Duda, J. (2021). Encoding of Probability Distributions for Asymmetric Numeral Systems. CoRR, Available online: http:\/\/xxx.lanl.gov\/abs\/2106.06438."},{"key":"ref_38","unstructured":"Casacuberta, S., and Kyng, R. (2021). Faster Sparse Matrix Inversion and Rank Computation in Finite Fields. arXiv, Available online: http:\/\/xxx.lanl.gov\/abs\/2106.09830."},{"key":"ref_39","unstructured":"Duda, J., and Niemiec, M. (2016). Lightweight compression with encryption based on Asymmetric Numeral Systems. arXiv."},{"key":"ref_40","unstructured":"Hsieh, C.J., Sustik, M.A., Dhillon, I.S., and Ravikumar, P. (2023, April 13). Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation. Available online: https:\/\/arxiv.org\/pdf\/1306.3212.pdf."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"150502","DOI":"10.1103\/PhysRevLett.103.150502","article-title":"Quantum algorithm for solving linear systems of equations","volume":"15","author":"Harrow","year":"2009","journal-title":"Phys. Rev. Lett."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Pieprzyk, J., Hardjono, T., and Seberry, J. (2003). Fundamentals of Computer Security, Springer.","DOI":"10.1007\/978-3-662-07324-7"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B. (2001). Random Graphs, Cambridge University Press.","DOI":"10.1017\/CBO9780511814068"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/4\/672\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:17:34Z","timestamp":1760123854000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/4\/672"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,17]]},"references-count":43,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,4]]}},"alternative-id":["e25040672"],"URL":"https:\/\/doi.org\/10.3390\/e25040672","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,17]]}}}