# Time-Universal Data Compression +
## 2 The Statement of the Problem and Preliminary Example  
Let there be a set of data compressors \(F=\{\varphi_{1},\varphi_{2},...\}\) and \(x_{1}x_{2}...\) be a sequence of letters from a finite alphabet \(A\), whose initial part \(x_{1}...x_{n}\) should be compressed by some \(\varphi\in F\). Let \(v_{i}\) be the time spent on encoding one letter by the data compressor \(\varphi_{i}\) and suppose that all \(v_{i}\) are upper-bounded by a certain constant \(v_{max}\), i.e. \(\sup_{i=1,2,...}v_{i}\leq v_{max}\). (It is possible that \(v_{i}\) is unknown beforehand.) The considered task is to find a data compressor from \(F\) which compresses \(x_{1}...x_{n}\) in such a way that the total time spent for all calculations and compressions does not exceed \(T(1+\delta)\) for some \(\delta>0\). Note that \(T=v_{max}\,n\) is the minimum time that must be reserved for compression and \(\delta T\) is the additional time that can be used to find the good compressor (among \(\varphi_{1},\varphi_{2},...\)). It is important to note that we can estimate \(\delta\) without knowing the speeds \(v_{1},v_{2},...\). If the number of data compressors \(F\) is finite, say, \(\{\varphi_{1},\varphi_{2},...,\varphi_{m}\}\), \(m\geq 2\), and one chooses \(\varphi_{k}\) to compress the file \(x_{1}x_{2}...x_{n}\), he can use the following two step procedure: encode the file as \(<k>\varphi_{k}(x_{1}x_{2}...x_{n})\), where \(<k>\) is \(\lceil\log m\rceil\)-bit binary presentation of \(k\). (The decoder first reads \(\lceil\log m\rceil\) bits and finds \(k\), then it finds \(x_{1}x_{2}...x_{n}\) decoding \(\varphi_{k}(x_{1}x_{2}...x_{n})\).) Now our goal is to generalize this approach for the case of infinite \(F=\{\varphi_{1},\varphi_{2},...\}\). For this purpose we take a probability distribution \(\omega=\omega_{1},\omega_{2},...\) such that all \(\omega_{i}>0\). The following is an example of such a distribution:  
\[\omega_{k}=\frac{1}{k(k+1)}\,\ k=1,2,3,... \tag{1}\]  
Clearly, it is a probability distribution, because \(\omega_{k}=1/k-1/(k+1)\). Now we should take into account the length of a codeword which presents the number \(k\), because those lengths must be different for different \(k\). So, we should find such \(\varphi_{k}\) that the value  
\[\lceil-\log\omega_{k}\rceil\ +|\varphi_{k}(x_{1}x_{2}...x_{n})|\]  
is close to minimal. As earlier, the first part \(\lceil-\log\omega_{k}\rceil\) is used for encoding number \(k\) (codes achieving this are well-known, e.g., [22].) The decoder first finds \(k\) and then \(x_{1}x_{2}...x_{n}\) using the decoder corresponding to \(\varphi_{k}\). Based on this consideration, we give the following  
**Definition 1**. : _We call any method that encodes a sequence \(x_{1}x_{2}...x_{n}\), \(n\geq 1\), \(x_{i}\in A\), by the binary word of the length \(\lceil-\log\omega_{j}\rceil\ +\ |\varphi_{j}(x_{1}x_{2}...x_{n})|\) for some \(\varphi_{j}\in F\), a time-adaptive code and denote it by \(\hat{\Phi}^{\delta}_{compr}\). The output of \(\hat{\Phi}^{\delta}_{compr}\) is the following word:_  
\[\hat{\Phi}^{\delta}_{compr}(x_{1}x_{2}...x_{n})\ =<\omega_{i}>\ \varphi_{i}(x_{1}x_{2}...x_{n}), \tag{2}\]  
_where \(<\omega_{i}>\) is \(\lceil-\log\omega_{i}\rceil\)-bit word that encodes \(i\), whereas the time of encoding is not grater than \(T(1+\delta)\) (here \(T=v_{max}\ n\))._  
_If for a time-adaptive code \(\hat{\Phi}^{\delta}_{compr}\) the following equation is valid_  
\[\lim_{n\to\infty}\hat{\Phi}^{\delta}_{compr}(x_{1}...x_{n})/n\ =\inf_{1=1,2,...\ n\to\infty} \varphi_{i}(x_{1}...x_{n})/n\,,\]  
_this code is called time-universal._  
**Comment 1** It will be convenient to reckon that the whole sequence is compressed not letter-by-letter, but by sub-words, each of which, say, a few kilobytes in length. More formally, let, as before, there be a sequence \(x_{1}x_{2}\dots\), where \(x_{i}\), \(i=1,2,...\) are sub-words whose length (say, \(L\)) can be a few kilobytes. In this case \(x_{i}\in\{0,1\}^{8L}\).