See Descriptional complexity, Data compression
Some measures of descriptional complexity are based on Data compression techniques, like the Lempel-Ziv complexity.
Related to Entropy-based complexity measures by Brudno's theorem
Relations to Grammar-based compressions used in Data compression
Application of Lempel–Ziv factorization to the approximation of grammar-based compression Relations between LZ-factorizations and grammar-based factorizations (G-factorization). The G-factorization gives an upper bound for the LZ complexity.
See this book too (same article), and this: Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input.