In run length encoding (RLE) the code stream consists of pairs $(c_i,\ell_i)$, which is understood as writing the character $c_i$ repeatedly $\ell_i$ times.

Consider the following "improvement" of the run length encoding. In run length eXtreme (RLX), the code stream consists of tuples $(c_i, p_i,l_i)$, where now $p_i$ specifies a position. Given a code stream $(c_1,p_1,l_1)\cdots(c_K,p_K,l_K)$ we start with an infinite all 0 string and for $k=1,\ldots,K$ write the character $c_k$ to positions $[p_k,p_k+l_k-1)$ overwriting whatever may have been written in these positions before. At the end we output the length $$n=\max_k (p_k + l_k -1)$$ prefix of this string.

For simplicity let us not worry about the bit length of the code words and take each code word as unit cost. Given a string $s$, let RLX(s) denote minimum number of code words that produce $s$ when decoded as described above.

How fast can we calculate RLX(s)?

Let us fix a string $s$ which does not contain any 0s and denote by $r(i,j)=\mathrm{RLX}(s[i..j])$. We can write a recurrence for $r$ as so: \begin{align} r(i,j) &= \min\begin{cases} 1 + r(i+1,j)\\ \min_{i<k\le j: s[i]=s[k]}r(i+1,k-1)+r(k, j) \end{cases} \end{align} To see this, consider the optimal encoding $E$ of $s[i..j]$. Either $s[i]$ has a dedicated code word or multiple characters in the final string $s$ are produced by the code word which produced $s[i]$.

If $s[i]$ has a dedicated code word in E, clearly $r(i,j) = 1+r(i+1,j)$. Otherwise, let $k$ be the index of the leftmost character produced by the same code word. Then we have $r(i,j) = r(i+1,k-1) + r(k,j)$.

Taking this recurrence literally leads to an obvious $O(n^3)$ dynamic programming algorithm.

Is there a faster algorithm for calculating RLX via a custom algorithm or a dynamic programming optimization?

Submodular interval functions:

An interval function maps two integers $i\le j$ to a real. An interval function is called submodular (aka concave, Inverse-QI, Inverse-Monge, etc.) if for $i\le i'\le j\le j'$ we have $$f(i,j') + f(i',j) \le f(i,j) + f(i',j').$$

Note that the $r$ we have defined above satisfies $r(i,j)\le r(i,k) + r(k+1,j)$ so one may hope r is submodular, at least when restricted to indices of the same character. But even such restricted forms of submodularity is false. Consider:

/*       5
 *      111
 *     44444
 *    3333333
 *   222222222 234
 *  111111111111111

s = 123415143212341

We have r(1,11) + r(7,15) = 6+5 but r(7,11) + r(1,15) = 4 + 9. Further the $r(\cdot,\cdot)$ is not a totally monotone matrix either. Are there other dynamic programming optimization that may still apply to this problem?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.