Keywords
entropy
Lempel-Ziv
How to Cite
Abstract
The library Lzcomplexity is presented, developed for complexity analysis using entropic metrics. The algorithms used to estimate the metrics by means of Lempel–Ziv factorization are described. To face the computational challenges associated with the analysis of large volumes of data, Lzcomplexity implements algorithms that enable parallel processing of the sequences. The experiments carried out and its practical use demonstrate that Lzcomplexity can analyze long sequences in reasonable times and that the included entropic measures are reliable indicators for describing complex systems.
References
[1] C. Shannon, Bell Syst Tech J 30, 379 (1951).
[2] C. Shannon, Bell Syst Tech J 30, 50 (1951).
[3] R. Nagarayama, IEEE Trans Biomed Eng 49, 1371 (2002).
[4] A. Lesne, J. l. Blanc and L. Pezard, Phys Rev E 79, 046208 (2009).
[5] E. Estevez-Rams, R. Lora-Serrano, C. A. J. Nunes and B. Aragón-Fernández, Chaos 25, 123106 (2015).
[6] L. M. Alonso, Chaos DOI: 10.1063/1.4984800 (2017).
[7] H. Y. D. Sigaki, M. Perc and H. V. Ribeiro, PNAS 115, E8585 (2018).
[8] E. Estevez-Rams, A. Mesa-Rodriguez and D. Estevez-Moya, PLoS ONE 14, e0214863 (2019).
[9] M. Li and P. Vitányi, An Introduction to Kolmogorov Complexity and Its Applications. (Springer Verlag, 1993).
[10] A. Lempel and J. Ziv, IEEE Trans Inf Th IT-22, 75 (1976).
[11] J. Ziv, IEEE Trans Inf Th IT-24, 405 (1978).
[12] M. Li, X. Chen, X. Li, B. Ma and P. M. B. Vitanyi, IEEE Trans Inf Th 50, 3250 (2004).
[13] P. Li, BioMed Eng OnLine 18, 30 (2019).
[14] L. E. V. Silva, R. Fazan and J. A. Marin-Neto, Computer Methods and Programs in Biomedicine 197, 105718 (2020).
[15] M. W. Flood and B. Grimm, PLoS ONE 16, e0259448 (2021).
[16] D. Mayor, D. Panday, H. K. Kandel, T. Steffert and D. Banks, Entropy 23, 321 (2021).
[17] M. Crochemore, L. Ilie and W. F. Smyth, Data Compression Conference (DCC 2008), 482 (IEEE, 2008).
[18] P. Grassberger, Int J Theor Phys 25, 907 (1986).
[19] T. M. Cover and J. A. Thomas, Elements of information theory. Second edition (Wiley Interscience, New Jersey, 2006).
[20] J. P. Crutchfield and K. Young, Phys Rev Lett 63, 105 (1989).
[21] J. P. Crutchfield, Nature 8, 17 (2012).
[22] O. Melchert and A. K. Hartmann, Phys Rev E 91, 023306 (2015).
[23] I. Corporation, IntelR oneapi threading building blocks (onetbb) (2024).
[24] B. Stroustrup, The C++ Programming Language (Addison-Wesley, Reading, Mass, 2000), special ed edition.
[25] Welcome to Python.org (2025). URL https://www.python.org/.
[26] Pybind11 documentation (2025). URL https://pybind11.readthedocs.io/en/stable/index.html.
[27] D. K. Kim, J. S. Sim, H. Park and K. Park, J. Discrete Algorithms 3, 126 (2005).
[28] J. Kärkkäinen, P. Sanders and S. Burkhardt, J ACM 53, 918 (2006).
[29] M. Salson, T. Lecroq, M. L´eonard and L. Mouchard, J. Discrete Algorithms 8, 241 (2010).
[30] G. Nong, S. Zhang and W. H. Chan, IEEE Trans Comput 60, 1471 (2011).
[31] U. Baier, 27th Annual Symposium on Combinatorial Pattern Matching, 12 (Dagstuhl Publishing, 2016).
[32] F. Kulla and P. Sanders, Parallel Computing 33, 605–612 (2007).
[33] J. Labeit, J. Shun and G. E. Blelloch, Journal of Discrete Algorithms 43, 2 (2017).
[34] J. Khan, T. Rubel, E. Molloy, L. Dhulipala and R. Patro, Algorithms for Molecular Biology 19, 16 (2024).
[35] W. D. Frazer and A. C. McKellar, J ACM 17, 496 (1970), ISSN 0004-5411, 1557-735X.
[36] G. Nong, S. Zhang and W. H. Chan, 2009 data compression conference, 193–202 (IEEE, 2009).
[37] Numba: A high performance python compiler (2025). URL: https://numba.pydata.org/.
[38] M. A. Montemurro and D. H. Zanette, PLoS One 6, e19875 (2011).
[39] C. Christodouloupoulos and M. Steedman, Lang Resources and Evaluation 49, 375 (2015).
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Copyright (c) 2025 Cuban Physical Society & Faculty of Physics of the University of Havana