{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T02:59:30Z","timestamp":1791341970271,"version":"4.3.1"},"reference-count":86,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,8,30]],"date-time":"2019-08-30T00:00:00Z","timestamp":1567123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2020,7,31]]},"abstract":"<jats:p>Huffman\u2019s algorithm for computing minimum-redundancy prefix-free codes has almost legendary status in the computing disciplines. Its elegant blend of simplicity and applicability has made it a favorite example in algorithms courses, and as a result it is perhaps one of the most commonly implemented algorithmic techniques. This article presents a tutorial on Huffman coding and surveys some of the developments that have flowed as a consequence of Huffman\u2019s original discovery, including details of code calculation and of encoding and decoding operations. We also survey related mechanisms, covering both arithmetic coding and the recently developed asymmetric numeral systems approach and briefly discuss other Huffman-coding variants, including length-limited codes.<\/jats:p>","DOI":"10.1145\/3342555","type":"journal-article","created":{"date-parts":[[2019,9,3]],"date-time":"2019-09-03T08:47:00Z","timestamp":1567500420000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":129,"title":["Huffman Coding"],"prefix":"10.1145","volume":"52","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6638-0232","authenticated-orcid":false,"given":"Alistair","family":"Moffat","sequence":"first","affiliation":[{"name":"The University of Melbourne, Melbourne, Victoria, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,8,30]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the Symposium on Combinatorial Pattern Matching. LIPIcs Series, Leibniz-Zentrum fuer Informatik, 29:1--29:13","author":"Barbay J.","year":"2016","unstructured":"J. Barbay. 2016. Optimal prefix free codes with partial sorting. In Proceedings of the Symposium on Combinatorial Pattern Matching. LIPIcs Series, Leibniz-Zentrum fuer Informatik, 29:1--29:13."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/208091.208092"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_6"},{"key":"e_1_2_1_4_1","unstructured":"A. A. Belal and A. Elmasry. 2016. Optimal prefix codes with fewer distinct codeword lengths are faster to construct. Retrieved from: CoRR abs\/cs\/0509015 (2016) 23."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","unstructured":"T. C. Bell J. G. Cleary and I. H. Witten. 1990. Text Compression. Prentice-Hall Englewood Cliffs NJ.","DOI":"10.5555\/77753"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/76894.76896"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3264903"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02243872"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/646942.711930"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00002-2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/253495.342777"},{"key":"e_1_2_1_12_1","first-page":"341","article-title":"Faster implementation of canonical minimum redundancy prefix codes","volume":"17","author":"Chung K.-L.","year":"2001","unstructured":"K.-L. Chung and J.-G. Wu. 2001. Faster implementation of canonical minimum redundancy prefix codes. J. Inform. Sci. Eng. 17, 2 (2001), 341--345.","journal-title":"J. Inform. Sci. Eng."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00204-9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1984.1096090"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1973.9200"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90021-8"},{"key":"e_1_2_1_17_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), 1--47. Retrieved from: http:\/\/arxiv.org\/abs\/0902.0271."},{"key":"e_1_2_1_18_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), 1--24. Retrieved from: http:\/\/arxiv.org\/abs\/1311.2540."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Picture Coding Symposium. IEEE, 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. IEEE, 65--69."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 7th Asilomar Conference on Circuits, Systems, and Computers. IEEE, 593--597","author":"Faller N.","year":"1973","unstructured":"N. Faller. 1973. An adaptive system for data compression. In Proceedings of the 7th Asilomar Conference on Circuits, Systems, and Computers. IEEE, 593--597."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2094072.2094073"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.1070"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/36.7.668"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2452252"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055959"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1966.1053907"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1979.1094481"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.469442"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2003.822145"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/77556.77566"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(94)90006-X"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0122024"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00176-2"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2013.49"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/646338.688714"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009910017828"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11786-011-0067-4"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90036-7"},{"key":"e_1_2_1_40_1","volume-title":"A Device for Quantizing, Grouping, and Coding Amplitude Modulated Pulses. Master\u2019s thesis","author":"Kraft L. G.","unstructured":"L. G. Kraft. 1949. A Device for Quantizing, Grouping, and Coding Amplitude Modulated Pulses. Master\u2019s thesis. MIT, Cambridge, MA."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.79150"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/45072.45074"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/882454.875119"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","unstructured":"M. Liddell and A. Moffat. 2006. Decoding prefix codes. Softw.\u2014Practice Exper. 36 15 (2006) 1687--1710.","DOI":"10.5555\/1182995.1182998"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2007.892446"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.223776"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.108260"},{"key":"e_1_2_1_48_1","volume-title":"Two inequalities implied by unique decipherability. Inst. Radio Eng. Trans. Inform. Theor. IT-2","author":"McMillan B.","year":"1956","unstructured":"B. McMillan. 1956. Two inequalities implied by unique decipherability. Inst. Radio Eng. Trans. Inform. Theor. IT-2 (1956), 115--116."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0060-4"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/789088.789854"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1012"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the Symposium on String Processing and Information Retrieval. IEEE Computer Society, 50--59","author":"Milidi\u00fa R. L.","unstructured":"R. L. Milidi\u00fa, A. A. Pessoa, and E. S. Laber. 1998. In-place length-restricted prefix coding. In Proceedings of the Symposium on String Processing and Information Retrieval. IEEE Computer Society, 50--59."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.945242"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.61469"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/317264.317268"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/645930.672864"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/290159.290162"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132888"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159663"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(94)90007-8"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.634683"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.681345"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","unstructured":"A. Moffat and A. Turpin. 2002. Compression and Coding Algorithms. Kluwer Academic Publishers Boston MA.","DOI":"10.5555\/560324"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2000.866669"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2740959"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)E0160-Z"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.5555\/1201915"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.5555\/874052.874917"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/363958.363991"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90146-9"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/971935.972028"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1038\/scientificamerican0991-54"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.5555\/42791"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1987.1057265"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/38.5.339"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00136-7"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.843129"},{"key":"e_1_2_1_79_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming","author":"van Leeuwen J.","year":"1976","unstructured":"J. van Leeuwen. 1976. On the construction of Huffman trees. In Proceedings of the International Colloquium on Automata, Languages, and Programming. Edinburgh University Press, Edinburgh University, Scotland, 382--410."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1974.1055176"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/31846.42227"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/63522.214390"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1109\/AINA.2005.33"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.5555\/323905"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/214762.214771"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","unstructured":"J. Zobel and A. Moffat. 1995. Adding compression to a full-text retrieval system. Softw.\u2014Practice Exper. 25 8 (1995) 891--903. 10.1002\/spe.4380250804","DOI":"10.1002\/spe.4380250804"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3342555","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3342555","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T09:25:11Z","timestamp":1750843511000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3342555"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,30]]},"references-count":86,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,7,31]]}},"alternative-id":["10.1145\/3342555"],"URL":"https:\/\/doi.org\/10.1145\/3342555","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,30]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}