{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T02:35:26Z","timestamp":1773801326873,"version":"3.50.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,7,21]],"date-time":"2020-07-21T00:00:00Z","timestamp":1595289600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006105","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP200103136"],"award-info":[{"award-number":["DP200103136"]}],"id":[{"id":"10.13039\/501100006105","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003816","name":"Huawei Technologies","doi-asserted-by":"publisher","award":["HO2019041002004P103"],"award-info":[{"award-number":["HO2019041002004P103"]}],"id":[{"id":"10.13039\/501100003816","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2020,10,31]]},"abstract":"<jats:p>An entropy coder takes as input a sequence of symbol identifiers over some specified alphabet and represents that sequence as a bitstring using as few bits as possible, typically assuming that the elements of the sequence are independent of each other. Previous entropy coding methods include the well-known Huffman and arithmetic approaches. Here we examine the newer asymmetric numeral systems (ANS) technique for entropy coding and develop mechanisms that allow it to be efficiently used when the size of the source alphabet is large\u2014thousands or millions of symbols. In particular, we examine different ways in which probability distributions over large alphabets can be approximated and in doing so infer techniques that allow the ANS mechanism to be extended to support large-alphabet entropy coding. As well as providing a full description of ANS, we also present detailed experiments using several different types of input, including data streams arising as typical output from the modeling stages of text compression software, and compare theproposed ANS variants with Huffman and arithmetic coding baselines, measuring both compression effectiveness and also encoding and decoding throughput. We demonstrate that in applications in which semi-static compression is appropriate, ANS-based coders can provide an excellent balance between compression effectiveness and speed, even when the alphabet is large.<\/jats:p>","DOI":"10.1145\/3397175","type":"journal-article","created":{"date-parts":[[2020,7,7]],"date-time":"2020-07-07T12:38:50Z","timestamp":1594125530000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Large-Alphabet Semi-Static Entropy Coding Via Asymmetric Numeral Systems"],"prefix":"10.1145","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6638-0232","authenticated-orcid":false,"given":"Alistair","family":"Moffat","sequence":"first","affiliation":[{"name":"The University of Melbourne, Victoria, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Petri","sequence":"additional","affiliation":[{"name":"The University of Melbourne, Victoria, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3231935"},{"key":"e_1_2_1_2_1","unstructured":"T. C. Bell J. G. Cleary and I. H. Witten. 1990. Text Compression. Prentice Hall Englewood Cliffs NJ.  T. C. Bell J. G. Cleary and I. H. Witten. 1990. Text Compression. Prentice Hall Englewood Cliffs NJ."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/76894.76896"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02243872"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the ACM International Conference on Research and Development in Information Retrieval (SIGIR\u201908)","author":"Brisaboa N. R.","unstructured":"N. R. Brisaboa , A. Fari\u00f1a , S. Ladra , and G. Navarro . 2008. Reorganizing compressed text . In Proceedings of the ACM International Conference on Research and Development in Information Retrieval (SIGIR\u201908) . 139--146. N. R. Brisaboa, A. Fari\u00f1a, S. Ladra, and G. Navarro. 2008. Reorganizing compressed text. In Proceedings of the ACM International Conference on Research and Development in Information Retrieval (SIGIR\u201908). 139--146."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Symposium on String Processing and Information Retrieval (SPIRE\u201903)","author":"Brisaboa N. R.","unstructured":"N. R. Brisaboa , A. Fari\u00f1a , G. Navarro , and M. F. Esteller . 2003. -Dense coding: An optimized compression code for natural language text databases . In Proceedings of the Symposium on String Processing and Information Retrieval (SPIRE\u201903) . 122--136. N. R. Brisaboa, A. Fari\u00f1a, G. Navarro, and M. F. Esteller. 2003. -Dense coding: An optimized compression code for natural language text databases. In Proceedings of the Symposium on String Processing and Information Retrieval (SPIRE\u201903). 122--136."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/40.2_and_3.76"},{"key":"e_1_2_1_8_1","volume-title":"Technical Report 124. Digital","author":"Burrows M.","year":"1994","unstructured":"M. Burrows and D. J. Wheeler . 1994 . A Block-sorting Lossless Data Compression Algorithm. Technical Report 124. Digital Equipment Corporation, Palo Alto , California . M. Burrows and D. J. Wheeler. 1994. A Block-sorting Lossless Data Compression Algorithm. Technical Report 124. Digital Equipment Corporation, Palo Alto, California."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1984.1096090"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1973.9200"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/30.6.541"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the Symposium on String Processing and Information Retrieval (SPIRE\u201905)","author":"Culpepper J. S.","unstructured":"J. S. Culpepper and A. Moffat . 2005. Enhanced byte codes with restricted prefix properties . In Proceedings of the Symposium on String Processing and Information Retrieval (SPIRE\u201905) . 1--12. J. S. Culpepper and A. Moffat. 2005. Enhanced byte codes with restricted prefix properties. In Proceedings of the Symposium on String Processing and Information Retrieval (SPIRE\u201905). 1--12."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/348751.348754"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Symposium on Information Theory (ISIT'19)","author":"Dub\u00e9 D.","unstructured":"D. Dub\u00e9 and H. Yokoo . 2019. Fast construction of almost optimal symbol distributions for asymmetric numeral systems . In Proceedings of the International Symposium on Information Theory (ISIT'19) . 1682--1686. D. Dub\u00e9 and H. Yokoo. 2019. Fast construction of almost optimal symbol distributions for asymmetric numeral systems. In Proceedings of the International Symposium on Information Theory (ISIT'19). 1682--1686."},{"key":"e_1_2_1_15_1","volume-title":"Asymmetric numeral systems. CoRR abs\/0902.0271","author":"Duda J.","year":"2009","unstructured":"J. Duda . 2009. Asymmetric numeral systems. CoRR abs\/0902.0271 ( 2009 ). https:\/\/arxiv.org\/abs\/0902.0271. J. Duda. 2009. Asymmetric numeral systems. CoRR abs\/0902.0271 (2009). https:\/\/arxiv.org\/abs\/0902.0271."},{"key":"e_1_2_1_16_1","volume-title":"Asymmetric numeral systems: Entropy coding combining speed of Huffman coding with compression rate of arithmetic coding. CoRR abs\/1311.2540","author":"Duda J.","year":"2013","unstructured":"J. Duda . 2013. Asymmetric numeral systems: Entropy coding combining speed of Huffman coding with compression rate of arithmetic coding. CoRR abs\/1311.2540 ( 2013 ). https:\/\/arxiv.org\/abs\/1311.2540. J. Duda. 2013. Asymmetric numeral systems: Entropy coding combining speed of Huffman coding with compression rate of arithmetic coding. CoRR abs\/1311.2540 (2013). https:\/\/arxiv.org\/abs\/1311.2540."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Picture Coding Symposium. 65--69","author":"Duda J.","unstructured":"J. Duda , K. Tahboub , N. J. Gadgil , and E. J. Delp . 2015. The use of asymmetric numeral systems as an accurate replacement for Huffman coding . In Proceedings of the Picture Coding Symposium. 65--69 . J. Duda, K. Tahboub, N. J. Gadgil, and E. J. Delp. 2015. The use of asymmetric numeral systems as an accurate replacement for Huffman coding. In Proceedings of the Picture Coding Symposium. 65--69."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"e_1_2_1_19_1","volume-title":"Combinatorial Algorithms on Words","volume":"12","author":"Fraenkel A. S.","unstructured":"A. S. Fraenkel and S. T. Klein . 1985. Novel compression of sparse bit-strings: Preliminary report . In Combinatorial Algorithms on Words , Volume 12 (NATO ASI Series F). Springer-Verlag, 169--183. A. S. Fraenkel and S. T. Klein. 1985. Novel compression of sparse bit-strings: Preliminary report. In Combinatorial Algorithms on Words, Volume 12 (NATO ASI Series F). Springer-Verlag, 169--183."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2452252"},{"key":"e_1_2_1_21_1","volume-title":"Interleaved entropy coders. CoRR abs\/1402.3392","author":"Giesen F.","year":"2014","unstructured":"F. Giesen . 2014. Interleaved entropy coders. CoRR abs\/1402.3392 ( 2014 ). F. Giesen. 2014. Interleaved entropy coders. CoRR abs\/1402.3392 (2014)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1966.1053907"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2078331.2078341"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the ACM International Conference on Research and Development in Information Retrieval (SIGIR\u201911)","author":"Hoobin C.","unstructured":"C. Hoobin , S. J. Puglisi , and J. Zobel . 2011. Sample selection for dictionary-based corpus compression . In Proceedings of the ACM International Conference on Research and Development in Information Retrieval (SIGIR\u201911) . 1137--1138. C. Hoobin, S. J. Puglisi, and J. Zobel. 2011. Sample selection for dictionary-based corpus compression. In Proceedings of the ACM International Conference on Research and Development in Information Retrieval (SIGIR\u201911). 1137--1138."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(92)90066-9"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(92)90067-A"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.286189"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/45072.45074"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2203"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the IEEE Data Compression Conference (DCC\u201917)","author":"Martinez M.","unstructured":"M. Martinez , M. Haurilet , R. Stiefelhagen , and J. Serra-Sagrist\u00e0 . 2017. Marlin: A high throughput variable-to-fixed codec using plurally parsable dictionaries . In Proceedings of the IEEE Data Compression Conference (DCC\u201917) . 161--170. M. Martinez, M. Haurilet, R. Stiefelhagen, and J. Serra-Sagrist\u00e0. 2017. Marlin: A high throughput variable-to-fixed codec using plurally parsable dictionaries. In Proceedings of the IEEE Data Compression Conference (DCC\u201917). 161--170."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342555"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/290159.290162"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the ACM International Conference on Information and Knowledge Management (CIKM\u201917)","author":"Moffat A.","unstructured":"A. Moffat and M. Petri . 2017. ANS-based index compression . In Proceedings of the ACM International Conference on Information and Knowledge Management (CIKM\u201917) . 677--686. A. Moffat and M. Petri. 2017. ANS-based index compression. In Proceedings of the ACM International Conference on Information and Knowledge Management (CIKM\u201917). 677--686."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013002601898"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"A. Moffat and A. Turpin. 2002. Compression and Coding Algorithms. Kluwer Boston.  A. Moffat and A. Turpin. 2002. Compression and Coding Algorithms. Kluwer Boston.","DOI":"10.1007\/978-1-4615-0935-6"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11265-018-1421-4"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the Asia Information Retrieval Societies Conference (AIRS\u201915)","author":"Petri M.","unstructured":"M. Petri , A. Moffat , P. C. Nagesh , and A. Wirth . 2015. Access time tradeoffs in archive compression . In Proceedings of the Asia Information Retrieval Societies Conference (AIRS\u201915) . 15--28. M. Petri, A. Moffat, P. C. Nagesh, and A. Wirth. 2015. Access time tradeoffs in archive compression. In Proceedings of the Asia Information Retrieval Societies Conference (AIRS\u201915). 15--28."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the Conference on Web Search and Data Mining (WSDM\u201919)","author":"Pibiri G. E.","unstructured":"G. E. Pibiri , M. Petri , and A. Moffat . 2019. Fast dictionary-based compression for inverted indexes . In Proceedings of the Conference on Web Search and Data Mining (WSDM\u201919) . 6--14. G. E. Pibiri, M. Petri, and A. Moffat. 2019. Fast dictionary-based compression for inverted indexes. In Proceedings of the Conference on Web Search and Data Mining (WSDM\u201919). 6--14."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.1998.672314"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxn030"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022949613039"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.843129"},{"key":"e_1_2_1_44_1","volume-title":"International Colloquium on Automata Languages and Programming (ICALP\u201976)","author":"van Leeuwen J.","unstructured":"J. van Leeuwen . 1976. On the construction of Huffman trees . In International Colloquium on Automata Languages and Programming (ICALP\u201976) . Edinburgh University Press , Edinburgh University , Scotland, 382--410. J. van Leeuwen. 1976. On the construction of Huffman trees. In International Colloquium on Automata Languages and Programming (ICALP\u201976). Edinburgh University Press, Edinburgh University, Scotland, 382--410."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.3.193"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/214762.214771"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the Conference on the World Wide Web (WWW\u201909)","author":"Yan H.","unstructured":"H. Yan , S. Ding , and T. Suel . 2009. Inverted index compression and query processing with optimized document ordering . In Proceedings of the Conference on the World Wide Web (WWW\u201909) . 401--410. H. Yan, S. Ding, and T. Suel. 2009. Inverted index compression and query processing with optimized document ordering. In Proceedings of the Conference on the World Wide Web (WWW\u201909). 401--410."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380250804"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE\u201906)","author":"Zukowski M.","unstructured":"M. Zukowski , S. H\u00e9man , N. Nes , and P. A. Boncz . 2006. Super-scalar RAM-CPU cache compression . In Proceedings of the International Conference on Data Engineering (ICDE\u201906) . 59. M. Zukowski, S. H\u00e9man, N. Nes, and P. A. Boncz. 2006. Super-scalar RAM-CPU cache compression. In Proceedings of the International Conference on Data Engineering (ICDE\u201906). 59."}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397175","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3397175","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:37Z","timestamp":1750195897000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397175"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,21]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,10,31]]}},"alternative-id":["10.1145\/3397175"],"URL":"https:\/\/doi.org\/10.1145\/3397175","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"value":"1046-8188","type":"print"},{"value":"1558-2868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,21]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}