# Finding Patterns in Signals Using Lossy Text Compression
## 3 Algorithms for Exact and Lossy RRLE Compression
### Lossy RRLE Compression
The second case means add \(k\) new children which represent the partition of the string. In this case, all \(k\) new edges are marked with \(1\). And the third case means the string itself is a leaf. For computing the first value, we need to compute the \(r\)-Parikh matrix \(M^{r}\), for every possible period length \(r\), and then recursively fill it. However, we bound this recursion by a constant number \(\ell\), which is the maximal levels in the RLE tree, by keeping for each call to Algorithm 2 its level in the recursion, and if we reach \(\ell\) we only compute the third value. The algorithm also stops when the input Parikh matrix is of size \(|\Sigma|\times 1\), and returns \(Mmin(1)\). The time complexity of computing \(D[1..n][1..n]\), is \(n^{2}\) times (for each \(i,j\)) the following:  
* Computing \(M^{r}\) for every possible \(r\) takes \(O(|\Sigma|n^{2})\) + the time for computing \(D\) for \(M^{r}\). * Computing the second value in the equation takes \(O(n)\). * Computing the third value in the equation takes \(O(|\Sigma|n)\). Each call takes \(O(|\Sigma|n^{4})\)-time, and since we bound the recursive calls to \(\ell\), the total time complexity is \(O(|\Sigma|n^{4\ell})\). The pseudocode of the algorithm is presented in Algorithm 2. For simplicity, the algorithm output is \(\operatorname{cost}(Q,P)\); however, it can be easily modified to include the string \(P\) as well. Theorem 4.1: _Let \(Q\) be a string of length \(n\) over \(\Sigma\), and let \(x\) be the output of a call to \(\textsc{Lossy}(M,\ell)\), where \(M\) is the \(n\)-Parikh matrix of \(Q\). Then \(x\) is the minimum \(\operatorname{cost}(Q,P^{\prime})\) over every string \(P^{\prime}\in\Sigma^{n}\) whose recursive depth is \(\ell\)._  
Proof: To prove the correctness of the algorithm recall that there are two options for a string \(Q\): it is either periodic or not. If \(Q\) is not periodic we can partition it to smaller consecutive substrings and compress them, or we can leave it as is. These options are covered by the algorithm in the second and third values, respective of the equation of computing \(D[i][j]\). If \(Q\) is periodic, or modified to be periodic, the algorithm checks all possible period lengths \(r\). For each such period length \(r\) it computes the \(r\)-Parikh matrix \(M^{r}\). The only thing we need to prove is that \(M^{r}\) represents all possible substrings \(q\in\Sigma^{r}\), and the corresponding value of \(\operatorname{cost}(Q[1..r],q)\). If this is true, it means that the algorithm considers all possible solution strings. Let us look at the string \(Q\) of size \(n\), and its \(n\)-Parikh matrix \(M[1..|\Sigma|][1..n]\). By definition, the cell \(M[\sigma][j]\) equals \(0\), if \(Q[j]=\sigma\), and \(1\), otherwise. Hence, computing \(\sum_{j=1}^{n}Mmin(j)\) gives us the minimum \(\operatorname{cost}(Q,P)\) over all strings \(P\in\Sigma^{n}\). The last thing left to prove is that computing the minimum \(\operatorname{cost}(Q,P)\) is sufficient in order to get \(\operatorname{cost}(Q,P)\) in the case of periodicity. If \(Q\) is periodic in \(r\), then, by definition, \(\operatorname{cost}(Q,P)=r+1+\operatorname{\mathit{scost}}(Q,P)\). Hence, minimizing \(\operatorname{cost}(Q,P)\) for a specific \(r\) is sufficient to compute the minimum \(\operatorname{cost}(Q,P)\) for this \(r\). Since the algorithm computes this value for every possible \(1\leq r\leq\frac{n}{2}\), it will find the correct solution string \(P\).