n} |s_\ell| /
$ and so [$\mathsf{occ}\left( {a}, {s} \right)$]{} (by fixing $a$ and summing over all those $b$ replaced by $\ell$). Since $$\sum_{\lceil \lg (n / {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}) \lg n \rceil = \ell} {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}
= |s_\ell|
\hspace{5ex} \mbox{and} \hspace{5ex}
\sum_a {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}
= \sum_\ell |s_\ell|
= n\,,$$ we have $$\begin{aligned}
& & \lefteqn{n H_0 (t) + \sum_\ell |s_\ell| \lg \sigma_\ell} \\[1ex]
& < & \sum_\ell |s_\ell| \lg (n / |s_\ell|) + \sum_\ell \sum_{\lceil \lg (n
/ {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}) \lg n \rceil = \ell} {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}} \lg \left( 2^\frac{1}
{\lg n} |s_\ell| / {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}} \right)\\[1ex]
& = & \sum_a {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}} \lg (n / {\ensuremath{\mathsf{occ}\left( {a}, {s} \right)}}) + n / \lg n \\[1ex]
& = & n H_0 (s) + o(n)\,.
$$

In other words, if we represent $t$ with $H_0 (t)$ bits per symbol and each $s_\ell$ with $\lg \sigma_\ell$ bits per symbol, then we achieve a good overall compression. Thus we can obtain a very compact representation of a string $s$ by storing a compact representation of $t$ and storing each $s_{\ell}$ as an “uncompressed” string over an alphabet of size 