{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:36:43Z","timestamp":1760236603664,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2021,12,10]],"date-time":"2021-12-10T00:00:00Z","timestamp":1639094400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100012190","name":"Ministry of Science and Higher Education of the Russian Federation","doi-asserted-by":"publisher","award":["075-02-2021-1387"],"award-info":[{"award-number":["075-02-2021-1387"]}],"id":[{"id":"10.13039\/501100012190","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The Lempel-Ziv parsing (LZ77) is a widely popular construction lying at the heart of many compression algorithms. These algorithms usually treat the data as a sequence of bytes, i.e., blocks of fixed length 8. Another common option is to view the data as a sequence of bits. We investigate the following natural question: what is the relationship between the LZ77 parsings of the same data interpreted as a sequence of fixed-length blocks and as a sequence of bits (or other \u201celementary\u201d letters)? In this paper, we prove that, for any integer b&gt;1, the number z of phrases in the LZ77 parsing of a string of length n and the number zb of phrases in the LZ77 parsing of the same string in which blocks of length b are interpreted as separate letters (e.g., b=8 in case of bytes) are related as zb=O(bzlognz). The bound holds for both \u201coverlapping\u201d and \u201cnon-overlapping\u201d versions of LZ77. Further, we establish a tight bound zb=O(bz) for the special case when each phrase in the LZ77 parsing of the string has a \u201cphrase-aligned\u201d earlier occurrence (an occurrence equal to the concatenation of consecutive phrases). The latter is an important particular case of parsing produced, for instance, by grammar-based compression methods.<\/jats:p>","DOI":"10.3390\/a14120359","type":"journal-article","created":{"date-parts":[[2021,12,13]],"date-time":"2021-12-13T01:28:11Z","timestamp":1639358891000},"page":"359","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Lempel-Ziv Parsing for Sequences of Blocks"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2909-2952","authenticated-orcid":false,"given":"Dmitry","family":"Kosolobov","sequence":"first","affiliation":[{"name":"Department of Physical and Mathematical Sciences, Ural Federal University, 620000 Ekaterinburg, Russia"}]},{"given":"Daniel","family":"Valenzuela","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, FI-00014 Helsinki, Finland"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,10]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","article-title":"On the complexity of finite sequences","volume":"22","author":"Ziv","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","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_4","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","article-title":"Application of Lempel-Ziv factorization to the approximation of grammar-based compression","volume":"302","author":"Rytter","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Kempa, D., and Prezza, N. (2018, January 25\u201329). At the roots of dictionary compression: String attractors. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), Los Angeles, CA, USA.","DOI":"10.1145\/3188745.3188814"},{"key":"ref_6","first-page":"207","article-title":"Towards a definitive measure of repetitiveness","volume":"Volume 12118","author":"Kociumaka","year":"2021","journal-title":"Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN)"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Navarro, G., and Urbina, C. (2021). On Stricter Reachable Repetitiveness Measures. arXiv.","DOI":"10.1007\/978-3-030-86692-1_16"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1109\/TIT.2020.3038147","article-title":"The smallest grammar problem revisited","volume":"67","author":"Bannai","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.jda.2018.09.002","article-title":"A separation between RLSLPs and LZ77","volume":"50","author":"Bille","year":"2018","journal-title":"J. Discret. Algorithms"},{"key":"ref_10","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"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"3195","DOI":"10.1007\/s00453-020-00722-6","article-title":"Lempel-Ziv-like parsing in small space","volume":"82","author":"Kosolobov","year":"2020","journal-title":"Algorithmica"},{"key":"ref_12","first-page":"201","article-title":"Relative Lempel\u2013Ziv compression of genomes for large-scale storage and retrieval","volume":"Volume 6393","author":"Kuruppu","year":"2010","journal-title":"Proceedings of the SPIRE 2010"},{"key":"ref_13","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_14","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.ipl.2018.09.005","article-title":"Comparison of LZ77-type parsings","volume":"141","author":"Kosolobov","year":"2019","journal-title":"Inf. Process. Lett."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/978-3-319-77313-1_3","article-title":"Underlying principles and recurring ideas of formal grammars","volume":"Volume 10792","author":"Okhotin","year":"2018","journal-title":"Proceedings of the 12th International Conference on Language and Automata Theory and Applications (LATA)"},{"key":"ref_16","first-page":"35","article-title":"The smallest grammar problem revisited","volume":"Volume 9954","author":"Hucke","year":"2016","journal-title":"Proceedings of the 23rd International Symposium on String Processing and Information Retrieval (SPIRE)"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1137\/0209022","article-title":"On the evaluation of powers and monomials","volume":"9","author":"Pippenger","year":"1980","journal-title":"SIAM J. Comput."},{"key":"ref_18","first-page":"421","article-title":"Pattern matching in Lempel-Ziv compressed strings: Fast, simple, and deterministic","volume":"Volume 6942","author":"Gawrychowski","year":"2011","journal-title":"Proceedings of the 19th Annual European Symposium on Algorithms (ESA)"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.tcs.2015.12.032","article-title":"A really simple approximation of smallest grammar","volume":"616","year":"2016","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/12\/359\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:45:17Z","timestamp":1760168717000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/12\/359"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,10]]},"references-count":19,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["a14120359"],"URL":"https:\/\/doi.org\/10.3390\/a14120359","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,12,10]]}}}