0.6 Compression of nonparametric sources  (Page 2/3)

To do so, we outline an approach by Elias  [link] . Let $n$ be a natural number, and let $b\left(n\right)$ be the binary form for $n$ . For example, $b\left(0\right)=0,b\left(1\right)=1,b\left(2\right)=10,b\left(3\right)=11$ , and so on. Another challenge is that the length of this representation, $\left|b\right(n\left)\right|$ , is unknown. Let $u\left(k\right)=0^{k-1}1$ , for example $u\left(4\right)=0001$ . We can now define $e\left(n\right)=u\left(\right|b\left(\right|b\left(n\right)\left|\right)\left|\right)b\left(\right|b\left(n\right)\left|\right)b\left(n\right)$ . For example, for n=5, we have $b\left(n\right)=101$ . Therefore, $\left|b\right(n\left)\right|=3,b\left(\right|b\left(n\right)\left|\right)=11,\left|b\right(\left|b\right(n\left)\right|\left)\right|=2,u\left(\right|b\left(\right|b\left(n\right)\left|\right)\left|\right)=01,$ and $e\left(n\right)=0111101$ . We note in passing that the first 2 bits of $e\left(n\right)$ describe the length of $b\left(\right|b\left(n\right)\left|\right)$ , which is 2, the middle 2 bits describe $b\left(\right|b\left(n\right)\left|\right)$ , which is 3, and the last 3 bits describe $b\left(n\right)$ , giving the actual number 5. It is easily seen that

Sliding window universal coding

Having described an efficient way to encode an index, in particular a large one, we can employ this technique in sliding window codingas developed by Wyner and Ziv  [link] .

Take a fixed window of length $n_w$ and a source that generates characters. Define the history as $x_1^{n_w}$ , this is the portion of the data $x$ that we have already processed and thus know.Our goal is to encode the phrase $y_1=x_{n_w+1}^{n_w+L_1}$ , where $L_1$ is not fixed. The length $L_1$ is chosen such that there exists

for some $m\in \{0,1,...,n_w-1\}$ . For example, if $x=abcbababc$ and we have processed the first 5 symbols $abcba$ , then $L_1=3$ and $m_1=1$ , where $abcba$ is the history and we begin encoding after that part.

The actual encoding of the phrase $y_1$ sends $\left|f\right(y_1\left)\right|$ bits, where

First we encode $L_1$ ; then either the index $m$ into history is encoded or $y_1$ is encoded uncompressed; finally, the first $L_1$ characters $x_1^{L_1}$ are removed from the history database, and $y_1$ is appended to its end. The latter process gives this algorithm a sliding window flavor.

This rather simple algorithm turns out to be asymptotically optimal in the limit of large $n_w$ . That is, it achieves the entropy rate.To see this, let us compute the compression factor. Consider $x_1^N$ where $N>>n_w$ , $\overline{R}\left(N\right)=\frac{E\left(l\left(x_1^N\right)\right)}{N}$ , $N={\sum }_{i=1}^C\left|y_i\right|$ , and $|y_i|=L_1$ , where $C$ is the number of phrases required to encode $x_1^N$ . The number of bits $l\left(x_1^N\right)$ needed to encoded $x_1^N$ using the sliding window algorithm is

Therefore, the compression factor $\overline{R}\left(N\right)$ satisfies

Claim 3 [link] As ${lim}_{n_w\to \infty }$ and ${lim}_{N\to \infty }$ , the compression factor $\overline{R}\left(N\right)$ converges to the entropy rate $H$ .

A direct proof is complicated, because the location of phrases is a random variable, making a detailed analysis complicated. Let us try to simplify the problem.

Take $l_0$ that divides $n_w+N$ to create $\frac{n_w+N}{l_0}$ intervals, where $l_0=\frac{log\left(n_w\right)}{H+2ϵ}$ , which is related to the window size in the algorithm from [link] . This partition into blocks appears in [link] . Denote by $w_{l_0}\left(x\right)>0$ the smallest value for which $x_1^{l_0}=x_{-w_{l_0}-l_0+1}^{-w_{l_0}}$ . Using Kac's lemma  [link] ,

Claim 4 [link] We have the following convergence as $l$ increases,