# Finding Patterns in Signals Using Lossy Text Compression
## 3 Algorithms for Exact and Lossy RRLE Compression
### Warm Up: Exact RRLE Compression  
We now describe Algorithm 1 for computing the smallest RLE of an input string \(Q\) and proves its correctness. For simplicity, the algorithm only computes the length of the smallest RLE but the RLE itself can be easily extracted by following the chosen indices during the recursive calls. This solves Problem 2. ```
Input : A string \(Q=(q_{1},..,q_{n})\) Output :\(\operatorname{rcost}(Q)\)
1 Define an \(n\times n\) matrix \(D[1..n][1..n]\) for every \(i\) in \(1..n\)do
2\(D[i][i]:=2\)
3 for\(\ell\) in \(2..n-1\) // length of evaluated substring
4 do
5 for\(i\) in \(1..n-\ell\) // starting index
6 do
7\(j=i+\ell-1\) Compute the smallest \(r\in[1..\ell]\) such that \(Q[i..j]\) is \(r\)-periodic \[D[i][j]=\min \begin{cases}D[i]\,[i+r-1],\text{ if }r<\ell\text{ // non-trivial period}\\ j-i+2,\\ \min_{k\in[(i+1)..j]}D[i][k-1]+D[k][j]\end{cases} \]
8 return\(D[1][n]\)
```  
**Algorithm 1**Exact(\(Q\)); see Theorem 4  
Overview of Algorithm 1:Given a string \(Q\) of length \(n\), the algorithm computes a matrix \(D[1..n][1..n]\), such that \(D[i][j]=\operatorname{rcost}(Q[i..j])\). In particular, \(D[1][n]=\operatorname{rcost}(Q)\). The matrix \(D\) is computed for substrings of increasing length; i.e., we first compute all substrings of length one, then all substrings of length two, and so on until the full string of length \(n\) is evaluated. We initialize the matrix on the main diagonal \(D[i][i]=2\) for \(1\leq i\leq n\). Then we compute \(\operatorname{rcost}(Q[i..j])\) for all \(1\leq i<j\leq n\) using a recursive definition of \(D[i][j]=\operatorname{rcost}(Q[i..j])\). This is the minimum between the followingthree values: (i) \(\operatorname{rocst}(Q[i..i+r-1])\) if \(Q[i..j]\) is \(r\)-periodic, where \(r\) is as small as possible, (ii) leaving \(Q[i..j]\) as a whole which takes 1 counter and \(j-i+1\) letters, and (iii) the smallest \(\operatorname{rcst}\) that can be obtained by partitioning \(Q[i..j]\) into two consecutive substrings \(Q[i..k-1]\) and \(Q[k..j]\), over every integer \(k\in[i+1,j-i+1]\). We now prove that the output of Algorithm 1 is indeed the optimal compression \(\operatorname{rcost}(Q)\) of its input \(Q\), which solves Problem 2. Let \(Q\) be a string of length \(n\). Let \(D[1][n]\) be the output of a call to \(\operatorname{\mathit{Exact}}(Q)\); see Algorithm 1. Then \(D[1][n]=\operatorname{\operatorname{rcst}}(Q)\) is the size of the smallest \(RRLE\) of \(Q\) and can be computed in \(O(n^{3})\) time. Proof. : We prove a more general claim, that the theorem holds for any substring \(Q[i..j]\) of \(Q\). The proof is by induction on the length \(\ell=j-i+1\) of \(Q[i..j]\). For \(\ell=1\), we have \(D[i][i]=\operatorname{\operatorname{rcst}}(Q[i])=2\), for storing the letter \(Q[i]\) and its length counter 1. For \(\ell\geq 2\), inductively assume that the theorem holds for any substring of \(Q[i..j]\). Let \(s=(t_{1},s_{1},\cdots,t_{m},s_{m})\) be the smallest \(\operatorname{RRLE}\) of \(Q[i..j]\). The rest of the proof corresponds to the three possible evaluations of \(D[i][j]\) in Algorithm 1. If \(m=1\) and \(Q[i..j]\) are \(r\)-periodic for \(r<|Q[i..j]|=j-i+1\), then \(t_{1}\geq 2\) denotes the number of periodic runs. Hence, \(s_{1}=Q[i..i+r-1]\) is the \(\operatorname{RRLE}\) of each run and \(|s|=1+|Q[i..i+r-1]|=D[i][i+r-1]\). If \(m=1\) and \(t_{1}=1\), then \(s_{1}=Q[i..j]\) and \(Q[i..j]\) are \(r=j-i+1\) periodic (otherwise we could have better compression rate for \(t_{1}>1\) and shorter string \(s_{1}\)). In this case, \(D[i][j]=1+|Q[i..j]|=1+(j-i+1)=j-i+2\). If \(m\geq 2\), then we can split it into a pair of \(\operatorname{RRLE}\)s \(Q[i..k-1]=S(t_{1},s_{1},\cdots,t_{j},s_{j})\) and \(Q[k..j]=S(t_{j+1},s_{j+1},\cdots,t_{m},s_{m})\). By the inductive assumption and the definition of the size \(|s|\) of \(s\),  
\[|s|=|(t_{1},s_{1},\cdots,t_{j},s_{j})|+|(t_{j+1},s_{j+1},\cdots,t_{m},s_{m})| =D[i][k-1]+D[k][j].\]  
**Time Complexity:** the algorithm runs \(O(n^{2})\) iterations over the pair of \"for\" loops.