1978/09/01 by J. Ziv, A. Lempel · 18 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Cellular Automata and Applications #Encoder #Lossless compression #Coding (social sciences) #Information theory #Entropy (arrow of time) #Converse #Computer science #Discrete mathematics #Data compression #Algorithm #Mathematics #Theoretical computer science #Statistics #Physics
paper · doi:10.1109/tit.1978.1055934
openalex publication_date 1978/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Compressibility of individual sequences by the class of generalized finite-state information-lossless encoders is investigated. These encoders can operate in a variable-rate mode as well as a fixed-rate one, and they allow for any finite-state scheme of variable-length-to-variable-length coding. For every individual infinite sequencexa quantityρ(x)is defined, called the compressibility ofx, which is shown to be the asymptotically attainable lower bound on the compression ratio that can be achieved forxby any finite-state encoder. This is demonstrated by means of a constructive coding theorem and its converse that, apart from their asymptotic significance, also provide useful performance criteria for finite and practical data-compression tasks. The proposed concept of compressibility is also shown to play a role analogous to that of entropy in classical information theory where one deals with probabilistic ensembles of sequences rather than with individual sequences. While the definition ofρ(x)allows a different machine for each different sequence to be compressed, the constructive coding theorem leads to a universal algorithm that is asymptotically optimal for all sequences.