{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:12:25Z","timestamp":1760242345503,"version":"build-2065373602"},"reference-count":26,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2017,5,13]],"date-time":"2017-05-13T00:00:00Z","timestamp":1494633600000},"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>The change of zero order entropy is studied over different strategies of grammar production rule selection. The two major rules are distinguished: transformations leaving the message size intact and substitution functions changing the message size. Relations for zero order entropy changes were derived for both cases and conditions under which the entropy decreases were described. In this article, several different greedy strategies reducing zero order entropy, as well as message sizes are summarized, and the new strategy MinEnt is proposed. The resulting evolution of the zero order entropy is compared with a strategy of selecting the most frequent digram used in the Re-Pair algorithm.<\/jats:p>","DOI":"10.3390\/e19050223","type":"journal-article","created":{"date-parts":[[2017,5,15]],"date-time":"2017-05-15T12:16:12Z","timestamp":1494850572000},"page":"223","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Prediction and Evaluation of Zero Order Entropy Changes in Grammar-Based Codes"],"prefix":"10.3390","volume":"19","author":[{"given":"Michal","family":"Vasinek","sequence":"first","affiliation":[{"name":"Department of Computer Science, FEECS, VSB-Technical University of Ostrava, 17. listopadu 15\/12172, Ostrava 708 33, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8481-0136","authenticated-orcid":false,"given":"Jan","family":"Platos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, FEECS, VSB-Technical University of Ostrava, 17. listopadu 15\/12172, Ostrava 708 33, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,5,13]]},"reference":[{"unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing), Wiley-Interscience.","key":"ref_1"},{"key":"ref_2","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_3","first-page":"1098","article-title":"A Method for the Construction of Minimum-Redundancy Codes","volume":"40","author":"Huffman","year":"1952","journal-title":"Proc. Inst. Radio Eng."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1145\/214762.214771","article-title":"Arithmetic Coding for Data Compression","volume":"30","author":"Witten","year":"1987","journal-title":"Commun. ACM"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","article-title":"The Smallest Grammar Problem","volume":"51","author":"Charikar","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"unstructured":"Nevill-Manning, C.G. (1996). Inferring Sequential Structure. [Ph.D. Thesis, University of Waikato].","key":"ref_6"},{"key":"ref_7","first-page":"67","article-title":"Identifying Hierarchical Structure in Sequences: A Linear-time Algorithm","volume":"7","author":"Witten","year":"1997","journal-title":"J. Artif. Int. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1109\/18.841160","article-title":"Grammar Based Codes: A New Class of Universal Lossless Source Codes","volume":"46","author":"Kieffer","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","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_10","doi-asserted-by":"crossref","first-page":"2874","DOI":"10.1109\/TIT.2003.818411","article-title":"Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform 2. With context models","volume":"49","author":"Yang","year":"2003","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","first-page":"23","article-title":"A New Algorithm for Data Compression","volume":"12","author":"Gage","year":"1994","journal-title":"C Users J."},{"unstructured":"Nakamura, H., and Marushima, S. (1996, January 13\u201317). Data Compression by Concatenation of Symbol Pairs. Proceedings of the IEEE International Symposium on Information Theory and Its Applications, Paris, France.","key":"ref_12"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1722","DOI":"10.1109\/5.892708","article-title":"Off-line dictionary-based compression","volume":"88","author":"Larsson","year":"2000","journal-title":"Proc. IEEE"},{"unstructured":"Claude, F., Farina, A., and Navarro, G. (2009). Re-Pair Compression of Inverted Lists. arXiv.","key":"ref_14"},{"unstructured":"Masaki, T., and Kida, T. (April, January 29). Online Grammar Transformation Based on Re-Pair Algorithm. Proceedings of the Data Compression Conference (DCC), Snowbird, UT, USA.","key":"ref_15"},{"unstructured":"Grassberger, P. (2002). Data Compression and Entropy Estimates by Non-sequential Recursive Pair Substitution. Physics.","key":"ref_16"},{"unstructured":"Calcagnile, L.M., Galatolo, S., and Menconi, G. (2008). Non-sequential recursive pair substitutions and numerical entropy estimates in symbolic dynamical systems. arXiv.","key":"ref_17"},{"doi-asserted-by":"crossref","unstructured":"Navarro, G., and Russo, L. (2008, January 25\u201327). Re-pair Achieves High-Order Entropy. Proceedings of the Data Compression Conference, DCC 2008, Snowbird, UT, USA.","key":"ref_18","DOI":"10.1109\/DCC.2008.79"},{"doi-asserted-by":"crossref","unstructured":"Vasinek, M., and Platos, J. (2014, January 26\u201328). Entropy Reduction Using Context Transformations. Proceedings of the Data Compression Conference (DCC), Snowbird, UT, USA.","key":"ref_19","DOI":"10.1109\/DCC.2014.65"},{"doi-asserted-by":"crossref","unstructured":"Vasinek, M., and Platos, J. (2015, January 7\u20139). Generalized Context Transformations\u2014Enhanced Entropy Reduction. Proceedings of the Data Compression Conference (DCC), Snowbird, UT, USA.","key":"ref_20","DOI":"10.1109\/DCC.2015.56"},{"unstructured":"Vasinek, M., and Platos, J. (2017). Higher Order Context Transformations. arXiv.","key":"ref_21"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/S0304-3975(02)00426-7","article-title":"Collage System: A Unifying Framework for Compressed Pattern Matching","volume":"298","author":"Kida","year":"2003","journal-title":"Theor. Comput. Sci."},{"unstructured":"Gonz\u00e1lez, R., and Navarro, G. (2007, January 9\u201311). Compressed Text Indexes with Fast Locate. Proceedings of the 18th Annual Conference on Combinatorial Pattern Matching, CPM\u201907, London, ON, Canada.","key":"ref_23"},{"unstructured":"Claude, F., Farina, A., and Navarro, G. (2009). Re-Pair compression of inverted lists. arXiv.","key":"ref_24"},{"unstructured":"Vasinek, M. (2013). Kontextove Mapy a Jejich Aplikace. [Master\u2019s Thesis, Vysoka Skola Banska\u2014Technicka Univerzita Ostrava].","key":"ref_25"},{"unstructured":"Vasinek, M., and Platos, J. (2017, May 11). Parallel Approach to Context Transformations. Available online: http:\/\/ceur-ws.org\/Vol-1343\/paper4.pdf.","key":"ref_26"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/19\/5\/223\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:35:45Z","timestamp":1760207745000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/19\/5\/223"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,13]]},"references-count":26,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2017,5]]}},"alternative-id":["e19050223"],"URL":"https:\/\/doi.org\/10.3390\/e19050223","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2017,5,13]]}}}