A. Lempel

A universal algorithm for sequential data compression is presented. Its performance is investigated with respect to a nonprobabilistic model of constrained sources. The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable-to-block codes designed to match a completely specified source.

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 sequence <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</tex> a quantity <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\rho(x)</tex> is defined, called the compressibility of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</tex> , which is shown to be the asymptotically attainable lower bound on the compression ratio that can be achieved for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</tex> by 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">\rho(x)</tex> 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.

A new approach to the problem of evaluating the complexity ("randomness") of finite sequences is presented. The proposed complexity measure is related to the number of steps in a self-delimiting production process by which a given sequence is presumed to be generated. It is further related to the number of distinct substrings and the rate of their occurrence along the sequence. The derived properties of the proposed measure are discussed and motivated in conjunction with other well-established complexity criteria.

The unnormalized Hamming correlation between two sequences of equal length is the number of positions in which these sequences have identical symbols. In this paper, lower bounds on the out-of-phase autocorrelation and on the cross correlation of sequences of given length and alphabet size are derived. A method of constructing families of sequences that uniformly realize these hounds is presented.

The graphs considered in this paper are assumed to be finite, with no edge joining a vertex to itself and with no two distinct edges joining the same pair of vertices. An undirected graph will be denoted by G or ( V, E ), where V is the set of vertices and E is the set of edges. An edge joining the vertices i,j ∊ V will be denoted by the unordered pair ( i,j ). An orientation of G = ( V, E ) is an assignment of a unique direction i → j or j → i to every edge ( i,j ) ∊ E . The resulting directed image of G will be denoted by G → or ( V , E→ ), where E→ is now a set of ordered pairs E→ = {[ i,j ]| ( i,j ) ∊ E and i → j }. Notice the difference in notation (brackets versus parentheses) for ordered and unordered pairs.