# Breaking efficiently a binary sequence into given strings

Suppose we are given a finite collection of finite binary strings $\mathcal{S}$, of various lengths. Our task is to express any binary sequence $x\in 2^\mathbb{N}$ as juxtaposition of strings taken from $\mathcal{S}:$ $$x=\sigma_1\sigma_2\sigma_3\dots$$ For any such sequence of "bricks", $\sigma\in\mathcal{S}^\mathbb{N},$ we consider $$L^*(\sigma):=\limsup_{n\to\infty}\frac{1}{n}\sum_{k=1}^n \mathrm{length}(\sigma_k)$$ as a kind of parameter of quality of the factorization: we appreciate a factorization if the mean length of the composing pieces is frequently high.

Question:

Given the set $\mathcal{S},$ how to compute the best $L^*(\sigma)$ which is always attainable, whatever is $x\in 2^\mathbb{N}?$ That is, the quantity (depending on $\mathcal{S}$ only)

$$\lambda(\mathcal{S}):=\inf_{x\in2^\mathbb{N}} \max \{L^*(\sigma) : \sigma\in\mathcal{S}^\mathbb{N}, x=\sigma_1 \sigma_2 \sigma_3\dots \}.$$

Also, are there special assumptions on the collection $\mathcal{S}$ that may simplify the analysis?

Example. Let $\mathcal{S}:=\{ 0,\ 1,\ 00,\ 01,\ 11 \}.$ Then, any binary sequence $x$ can be broken into a sequence of strings in $\mathcal{S}$, with average length larger than or equal to $3/2$.

Remark. For my purposes, we can assume that the collection $\mathcal{S}$ always enjoys the property of being "stable for extraction of sub-strings", that is, if $\sigma=\epsilon_1 \epsilon_2 \dots \epsilon_n\in\mathcal{S}$, then also $\epsilon_p \epsilon_{p+1} \dots \epsilon_q\in\mathcal{S},$ for any $1\leq p < q\leq n.$ If I am not wrong, this allows quite a simple inductive procedure for a canonical optimal factorization $\sigma$ of a binary sequence $x$: having chosen $\sigma_1,\dots,\sigma_k,$ take $\sigma_{k+1}$ as the longest admissible element of $\mathcal{S}$: by the above property of $\mathcal{S}$ any other factorization $\tau$ of $x$ can be easily compared with $\sigma$, showing $L^ *(\sigma) \geq L^ *(\tau)$. So in this case I'd expect there is some hope of being able of computing the quantity $\lambda(\mathcal{S}).$

-
Just for context: en.wikipedia.org/wiki/Huffman_coding –  Steve Huntsman Oct 6 '10 at 16:53
thanks a lot! (I came to this problem from a completely different origin so a context where to look is a very useful starting point). –  Pietro Majer Oct 6 '10 at 17:45

Thank you, that's of use indeed. Note that my S is a finite collection of strings of finite length. So, following somehow the hints in the first part of your answer I think I see how to compute that L(S), assuming the property I wrote in the remark. Let $A$ be a string in S of minimal length among those starting with $0,$ and such that $A0\notin S.$ Also, let $B,$ $C,$ $D$ defined analogously: $A$ and $B$ start with $0,$ $C$ and $D$ start with 1; $A0$ $B1$ $C0$ $D1$ are not in $S$. Then the constant L(S) is realized either by the sequence AAA.., or by DDD, or by BCBC... –  Pietro Majer Oct 8 '10 at 17:23