You can try to compress a string in this way, but the overhead from the compression will always exceed the gain from compression.
In fact, the argument that this will always happen is very similar to the "probabilistic method" lower bounds for many Ramsey-type problems.
For instance, consider Ramsey's theorem: the claim that for any $k$, if $n$ is sufficiently large, any red-blue coloring of the edges of the complete graph $K_n$ will contain a clique $K_k$ whose edges all have one color.
First, a brief aside to prove a lower bound on $n$ for this to happen. The probabilistic construction for the lower bound says that a sufficiently large $n$ must satisfy $\binom nk \ge 2^{\binom{k}{2}-1}$ (which is a bound roughly like $n \ge 2^{k/2}$). To prove this, suppose that $\binom nk < 2^{\binom{k}{2}-1}$, and take a random red-blue coloring of $K_n$. The number of cliques of size $k$ is $\binom nk$, and each is entirely red with probability $2^{-\binom k2}$ and entirely blue with probability $2^{-\binom k2}$. So the average number of monochromatic cliques is $\binom nk 2^{1-\binom k2}$, which is less than $1$ by assumption; therefore it's possible that the random coloring will not have a monochromatic clique.
Now let's go back to the compression idea. If we use Ramsey's theorem to try to compress a coloring of $K_n$, we should specify a particular clique of size $k$ which happens to be monochromatic, and then save space by just specifying the color of that clique - instead of specifying the colors of all $\binom k2$ edges in the clique individually. This saves $\binom k2 - 1$ bits of storage. However, we need $\log_2 \binom nk$ bits of storage to specify which clique we're using. The overall benefit is
$$
\binom k2 - 1 - \log_2 \binom nk = \log_2 \left(2^{\binom k2 - 1} / \binom nk\right)
$$
and by the probabilistic lower bound, the term inside the log is at most $1$, which means that the log is nonpositive. That is, we can never benefit from this compression scheme.
This is not a coincidence: in general, the threshold at which the probabilistic lower bound for the Ramsey-type problem works is exactly the same as the threshold at which we stop being able to compress efficiently, because the calculation for both is the same.
Below that threshold, we can win by spotting the ordered substructure we are looking for - if it exists, which it might not. Above that threshold, the ordered substructure typically exists - but we no longer benefit from using it, because the cost outweighs the gain.
(In cases such as Ramsey's theorem, where there is a gap between the expected-value lower bound and the best known upper bound, there is an interval which is the worst of both worlds. We don't save anything by exploiting the ordered substructure, and we also don't know if one exists.)
