We study abstract complexity measures that relate both to theoretical data compression and Diophantine approximation. We extract a group of axioms that aim to capture the core aspects of both. We illustrate this by numerical examples and theoretical properties, notably the analysis of the gzip compression algorithm and Liouville's theorem in Diophantine approximation.