{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T11:28:17Z","timestamp":1778758097169,"version":"3.51.4"},"reference-count":27,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T00:00:00Z","timestamp":1665446400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In this paper, we address the problem of m-gram entropy variable-to-variable coding, extending the classical Huffman algorithm to the case of coding m-element (i.e., m-grams) sequences of symbols taken from the stream of input data for m&gt;1. We propose a procedure to enable the determination of the frequencies of the occurrence of m-grams in the input data; we formulate the optimal coding algorithm and estimate its computational complexity as O(mn2), where n is the size of the input data. Since such complexity is high in terms of practical applications, we also propose an approximate approach with linear complexity, which is based on a greedy heuristic used in solving backpack problems. In order to verify the practical effectiveness of the proposed approximate approach, experiments involving different sets of input data were conducted. The experimental study shows that the results obtained with the approximate approach were, first, close to the optimal results and, second, better than the results obtained using the popular DEFLATE and PPM algorithms in the case of data that can be characterized by highly invariable and easy to estimate statistics.<\/jats:p>","DOI":"10.3390\/e24101447","type":"journal-article","created":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T22:18:13Z","timestamp":1665526693000},"page":"1447","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Variable-to-Variable Huffman Coding: Optimal and Greedy Approaches"],"prefix":"10.3390","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6197-0372","authenticated-orcid":false,"given":"Kun","family":"Tu","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, Yangzhou University, 88 South Daxue Road, Yangzhou 225002, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9070-8042","authenticated-orcid":false,"given":"Dariusz","family":"Puchala","sequence":"additional","affiliation":[{"name":"Institute of Information Technology, Lodz University of Technology, 8 Politechniki Avenue, 93-590 Lodz, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,10,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Sayood, K. (2018). Introduction to Data Compression, Morgan Kaufmann Publishers.","DOI":"10.1016\/B978-0-12-809474-7.00019-7"},{"key":"ref_2","unstructured":"Bell, T.C., Cleary, J.G., and Witten, I.H. (1990). Text Compression, Prentice Hall."},{"key":"ref_3","unstructured":"Fano, R.M. (1949). The Transmission of Information, Massachusetts Institute of Technology, Research Laboratory of Electronics."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A Mathematical Theory of Communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Syst. Tech. J."},{"key":"ref_5","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_6","doi-asserted-by":"crossref","unstructured":"Navarro, G., and Ord\u00f3\u00f1ez, A. (2013, January 20\u201322). Compressing Huffman Models on Large Alphabets. Proceedings of the Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC.2013.46"},{"key":"ref_7","unstructured":"Tunstall, B.P. (1967). Synthesis of Noiseless Compression Codes. [Ph.D. Dissertation, Georgia Institute of Technology]."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Bille, P., Berggren Ettienne, M., Gagie, T., Li G\u00f8rtz, I., and Prezza, N. (2020, January 24\u201327). Decompressing Lempel-Ziv Compressed Text. Proceedings of the Data Compression Conference, Snowbird, UT, USA.","DOI":"10.1109\/DCC47342.2020.00022"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for data compression","volume":"IT-23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable-rate coding","volume":"IT-24","author":"Ziv","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/MC.1984.1659158","article-title":"A technique for high-performance data compression","volume":"17","author":"Welch","year":"1984","journal-title":"Computer"},{"key":"ref_12","unstructured":"Nelson, M., and Gailly, J.L. (1996). The Data Compression Book, M&T Books."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Deutsch, P.L. (1996). DEFLATE Compressed Data Format Specification Version 1.3, IETF.","DOI":"10.17487\/rfc1951"},{"key":"ref_14","unstructured":"Chandra, A., and Chakrabarty, K. (May, January 29). Frequency-directed run-length codes with application to system-on-chip test data compression. Proceedings of the 19th IEEE VLSI Test Symposium, Marina Del Rey, CA, USA."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1109\/TCAD.2003.811451","article-title":"Variable-length input Huffman coding for system-on-chip test","volume":"22","author":"Gonciari","year":"2003","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1109\/TCAD.2003.811452","article-title":"An efficient test vector compression scheme using selective Huffman coding","volume":"22","author":"Jas","year":"2003","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1146","DOI":"10.1109\/TC.2007.1057","article-title":"Optimal selective Huffman coding for Test-Data compression","volume":"56","author":"Kavousianos","year":"2007","journal-title":"IEEE Trans. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1109\/TCAD.2008.923100","article-title":"Test Data Compression Based on Variable-to-Variable Huffman Encoding With Codeword Reusabilit","volume":"27","author":"Kavousianos","year":"2008","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"ref_19","unstructured":"Freeman, G.H. (1991, January 8\u201311). Asymptotic Convergence of Dual-Tree Entropy Codes. Proceedings of the Data Compression Conference, Snowbird, UT, USA."},{"key":"ref_20","unstructured":"Freeman, G.H. (April, January 30). Divergence and the Construction of Variable-to-Variable-Length Lossless Codes by Source-Word Extensions. Proceedings of the Data Compression Conference, Snowbird, UT, USA."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Salomon, D. (2007). Variable-Length Codes for Data Compression, Springer.","DOI":"10.1007\/978-1-84628-959-0"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1109\/TIT.1978.1055959","article-title":"Variations on a Theme by Huffman","volume":"24","author":"Gallager","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF02243872","article-title":"Is Huffman Coding Dead?","volume":"50","author":"Bookstein","year":"1993","journal-title":"Computing"},{"key":"ref_24","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1016\/j.future.2019.08.021","article-title":"A new chain coding mechanism for compression stimulated by a virtual environment of a predator-prey ecosystem","volume":"102","author":"Dhou","year":"2020","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1109\/TEC.1961.5219197","article-title":"On the encoding of arbitrary geometric configurations","volume":"2","author":"Freeman","year":"1961","journal-title":"IRE Trans. Electron. Comput."},{"key":"ref_27","unstructured":"Hollos, S., and Hollos, J.R. (2015). Information Theory. A Concise Introduction, Abrazol Publishing."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/10\/1447\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:49:48Z","timestamp":1760143788000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/10\/1447"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,11]]},"references-count":27,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2022,10]]}},"alternative-id":["e24101447"],"URL":"https:\/\/doi.org\/10.3390\/e24101447","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,11]]}}}