# Finding Patterns in Signals Using Lossy Text Compression
## 3 Algorithms for Exact and Lossy RRLE Compression
### Lossy RRLE Compression
We obtain \(Q_{1,1}=(\mathbf{ababac})\), \(Q_{2,1}=(\mathbf{b}b\mathbf{b}b\mathbf{b}c)\), and \(Q_{3,1}=(\mathbf{c}bcbc)\). Counting the corresponding mismatches compared to \(Q=(ababac)\), we get that \(M[1][1]=0\), \(M[2][1]=3\), and \(M[3][1]=3\). In a similar way, for \(j=2\), we obtain \(Q_{1,2}=(a\mathbf{aaaaa})\), \(Q_{2,2}=(a\mathbf{b}a\mathbf{b}a\mathbf{b})\), and \(Q_{3,2}=(acacac)\). Hence, \(M[1][2]=3\), \(M[2][2]=1\), and \(M[3][2]=2\). The 2-Parikh Matrix of \(Q\) is then \(\left( \begin{smallmatrix}0&3\\ 3&1\\ 3&2\end{smallmatrix} \right)\). Finally, if \(r=n\) then \(M[i][j]=0\) if the \(j\)th letter of \(Q\) equals \(\Sigma_{i}\), and \(M[i][j]=1\) otherwise. Hence, the 6-Parikh Matrix of \(Q=(ababac)\) is \(\left( \begin{smallmatrix}0&1&0&1&0&1\\ 1&0&1&0&1&1\\ 1&1&1&1&1&0\end{smallmatrix} \right)\). For the \(r\)-Parikh matrix \(M^{r}\) of a string \(Q\), we it denote by \(M^{r}_{min}(j)=\min_{i\in|\Sigma|}M^{r}[i][j]\), the smallest entry in the \(j\)th column of \(M^{r}\). Suppose that its row is \(i^{*}\); i.e., \(M^{r}_{min}(j)=M^{r}[i^{*}][j]\). Therefore, if we wish to fix \(Q\) to be \(r\)-periodic with an offset \(j\), by paying the smallest Hamming distance cost, then we should change the corresponding letters \(Q[j],Q[j+r],\cdots\) to the letter \(\sigma_{i^{*}}\). This is also the motivation for using this matrix in Algorithm 2. ```
input : The \(n\)-_Parikh Matrix_\(M[1..|\Sigma|][1..n]\) of a string \(Q\in\Sigma^{n}\), and an integer \(\ell\geq 0\). output : cost\((Q,P)\), where \(P\) is a string of length \(n\) that minimizes this cost. if\(n=1\) or \(\ell=0\)then return\(\sum_{j=1}^{n}Mmin(j)+n\) \(F:=\left\{r\in\left[\frac{n}{2}\right]\mid(r\mod n)=0\right\}\) // The factors of \(n\) for every \(r\in F\)do \(M^{r}:=\) the \(r\)-Parikh Matrix of \(Q\). for\(i\) in \(1..n\)do \(D[i][i]=1+M^{r}min(i)\) for\(m\) in \(2..n\)do // length of sub-string for\(i\) in \(1..(n-m)\)do // starting index \(j:=i+m-1\) // ending index // compute the smallest cost \(D[i..j]\) for \(Q[i..j]\) \(D[i][j]=\min\begin{cases}1+\min\limits_{r\in F}\textsc{Lossy}(M^{r},\ell-1) \\ \min\limits_{i<k\leq j}\left(D[i][k-1]+D[k][j]\right)\) // partition into two \(m+\sum_{c=i}^{j}Mmin(c)\) // leave as is return\(D[1][n]\)
```  
**Algorithm 2**\(\textsc{Lossy}(M,\ell)\); See Theorem 6. Overview of Algorithm 2:The input to the algorithm is a \(n\)-Parikh matrix \(M\) of a string \(Q\) of size \(n\) over \(\Sigma\), and an integer \(\ell\) that denotes the maximum RRLE tree level of the compression, as explained below. Note that both \(Q\) and \(n\) can extracted from this Parikh matrix. We use dynamic programming to compute the matrix \(D[1..n][1..n]\), in which \(D[i][j]=\text{cost}(Q[i..j],P^{\prime})\) is the (optimal) compression cost of the sub string \(Q[i..j]\). The loops are over the length \(m\) of the substring (from \(1\) to \(n\)), and then from the starting index \(i\). The last index is denoted by \(j=i+m-1\). We first compute the optimal cost of modifying a substring of length \(1\) in the \(i\)th index. This is \(Mmin(i)\) by definition, so \(D[i][i]=1+Mmin(i)\) for \(1\leq i\leq n\). Next, we compute \(D[i][j]=\text{cost}(Q[i..j],P^{\prime})\) for every \(1\leq i<j\leq n\) using recursive exhaustive search over the following three options. The first option is to modify the substring \(Q[i..j]\) in order to get \(r\)-periodic substring for some factor \(r\). This costs \(1\) for the number of reputations and the total compression of the first \(r\) letters of \(Q\). The second option is to partition the substring into a pair of substrings: the left and right side of the original string. The overall cost is then the sum of these two costs. The last option is simply to keep the substring as is. This takes \(m\) letters which is the size of the substring. Looking at the resulting RLE tree, the first case means we can compress the string by adding the node new single child which represents a period of length \(r\). The edge to this new child is marked with \(\frac{n}{r}\).