# Time-Universal Data Compression +
## 4 The Time-Universal Code for Stationary Ergodic Sources  
In this section we describe a time-universal code for stationary sources. It is based on optimal universal codes for Markov chains, developed by [PERSON] [4; 24] and the twice-universal code [25]. Denote by \(M_{i}\), \(i=1,2,...\) the set of Markov chains with memory (connectivity) \(i\), and let \(M_{0}\) be the set of Bernoulli sources. For stationary ergodic \(\mu\) and an integer \(r\) we denote by \(h_{r}(\mu)\) the \(r\)-order entropy (per letter) and let \(h_{\infty}(\mu)\) be the limit entropy; see for definitions [22]. [PERSON] [4; 24] described the codes \(\psi_{0},\psi_{1},...\) which are asymptotically optimal for \(M_{0},M_{1},...\), correspondingly. If the sequence \(x_{1}x_{2}...x_{n}\), \(x_{i}\in A\), is generated by a source \(\mu\in M_{i}\), the following inequalities are valid almost surely (a.s.):  
\[h_{i}(\mu)\leq|\psi_{i}(x_{1}...x_{t})|/t\,\leq h_{i}(\mu)+((|A|-1)|A|^{i}+C)/t, \tag{8}\]  
where \(t\) grows. (Here \(C\) is a constant.) The length of a codeword of the twice-universal code \(\rho\) is defined as the following \"mixture\":  
\[|\rho(x_{1}...x_{t})|=-\log\,\sum_{i=0}^{\infty}\omega_{i+1}\,2^{-|\psi_{i}(x _{1}...x_{t})|}. \tag{9}\]  
(It is well-known in information theory [22] that there exists a code with such codeword lengths, because \(\sum_{x_{1}...x_{t}\in A^{t}}\,2^{-|\rho(x_{1}...x_{t})|}=1\).) This code is called twice-universal because for any \(M_{i}\), \(i=0,1,...\), and \(\mu\in M_{i}\) the equality (8) is valid (with different \(C\)). Besides, for any stationary ergodic source \(\mu\) a.s.  
\[\lim_{t\to\infty}|\rho_{i}(x_{1}...x_{t})|/t\,=h_{\infty}(\mu). \tag{10}\]  
Let us estimate the time of calculations necessary when using \(\rho\). First, note that it suffices to sum a finite number of terms in (9), because all the terms \(2^{-|\psi_{i}(x_{1}...x_{t})|}\) are equal for \(i\geq t\). On the other hand, the number of different terms grows, where \(t\to\infty\) and, hence, the encoder should calculate \(2^{-|\psi_{i}(x_{1}...x_{t})|}\) for growing number \(i\)'s. It is known [24] that the time spent on coding one letter is close for different codes \(\psi_{i}\), \(i=0,1,2,...\). Hence, the time spent for encoding one letter by the code \(\rho\) grows to infinity, when \(t\) grows. The described below time-universal code \(\Psi^{\delta}\) has the same asymptotic performance, but the time spent for encoding one letter is a constant. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Length of File (byte)** & **Number of Files** & **Ratio “Chosen Best”** & **Average “Worst/Best”** & **Average “Chosen/Best”** \\ \hline \(\leq 10^{5}\) & 1496 & 10\% & 112.87\% & 103.12\% \\ \(10^{5}\)–\(10^{6}\) & 1122 & 44.69\% & 131.22\% & 102.54\% \\ \(10^{6}\)–\(10^{8}\) & 384 & 72\% & 147.95\% & 100.88\% \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Four-step compression. Extra-time \(20\times 0.01+5\times 0.02\) \(+3\times 0.05=0.45\). In order to describe the time-universal code \(\Psi^{\delta}\) we give some definitions. Let, as before, \(v\) be an upper-bound of the time spent for encoding one letter by any \(\psi_{i}\), \(x_{1}...x_{t}\) be the generated word,  
\[T=t\,v,\,N(t)=\delta T/v=\delta\,t,\]  
\[m(t)=\lfloor\log\log N(t)\rfloor,\,s(t)=\lfloor N(t)/(m(t)+1)\rfloor. \tag{11}\]  
Denote by \(\Psi^{\delta}\) the following method:  
Step 1. Calculate \(m(t),s(t)\) and  
\[|\psi_{0}(x_{1}...x_{s(t)})|,|\psi_{1}(x_{1}...x_{s(t)})|,...,|\psi_{m(t)}(x_{1 }...x_{s(t)})|.\]  
Step 2. Find such a \(j\) that  
\[|\psi_{j}(x_{1}...x_{s(t)})|=\min_{i=0,...,m(t)}|\psi_{i}(x_{1}...x_{s(t)})|.\]  
Step 3. Calculate the codeword \(\psi_{j}(x_{1}...x_{t})\) and output  
\[\Psi^{\delta}(x_{1}...x_{t})=\,<j>\psi_{j}(x_{1}...x_{t}),\]  
where \(<j>\) is the \(\lceil-\log\omega_{j+1}\rceil\)-bit codeword of \(j\). The decoding is obvious. Theorem 3.2: _Let \(x_{1}x_{2}...\) be a sequence generated by a stationary source and the code \(\Psi^{\delta}\) be applied.