Breaking efficiently a binary sequence into given strings

2010-10-06T15:55:22Z

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}).$

Answer by Gerhard Paseman for Breaking efficiently a binary sequence into given strings

2010-10-07T22:18:46Z

Not an answer, but perhaps of some use:

It would help if S, the set of blocks, were finite. In any case, if S contains all words of length k, you know that for sufficiently long words L will have k as a lower bound. (Computing k for a given S closed under consecutive substrings is feasible, but may not be polynomial time in the length of a representation of S.) If S contains almost all words of length k, then the lower bound for L will still be k on those sigma which avoid the missing words, otherwise the lower bound for L will approach the lower bound for L of those missing words which occur more frequently as you read more of sigma. It may then make sense to compute L for short words not in S, or infinite repetitions of such short words, and use this in aiding the computation of L of sigma.

If S has infinitely many finite blocks (and the alphabet is still finite), then there is the potential for L to assume values of infinity. If you don't care about that or if you are focussing on the cases where L will be finite, then you have some mathematics which may touch upon descriptive set theory, and you may encounter a large cardinal or other surprising axiom to consider. S being closed under consecutive substrings will in many cases produce a larger k (k as in the above paragraph), and will have to be pretty special otherwise to avoid any finite substring. There may be other tools in mathematical logic (e.g. filters on finite subsets of the language) that might tell you what properties you want S to have.

Another poster referenced Huffman encoding. Outside of symbolic dynamics (and related fields of automata theory and semigroup theory), that and similar string-processing algorithms is a first choice of where to look for previous work. If you are considering extra-world (surreal? non-real?) applications using infinite S might you then turn to mathematical logic.

Gerhard "Ask Me About System Design" Paseman, 2010.10.07

Breaking efficiently a binary sequence into given strings - MathOverflow

Breaking efficiently a binary sequence into given strings

Answer by Gerhard Paseman for Breaking efficiently a binary sequence into given strings