# Finding Patterns in Signals Using Lossy Text Compression
## 3 Algorithms for Exact and Lossy RRLE Compression
### Lossy RRLE Compression  
In this section we solve Problem 3; i.e., compute a lossy good compression of an input string \(Q\). Formally, given such a string \(Q\) of length \(n\), the goal of our algorithm is to compute the minimum \(\operatorname{cost}(Q,P^{\prime})\) over every string \(P^{\prime}\in\Sigma^{n}\); see Section 2.3 for the definition of \(\operatorname{cost}\). Of course, one can simply compute \(\operatorname{cost}(Q,P^{\prime})\) using \(\operatorname{rcost}(P^{\prime})=\operatorname{\mathit{Exact}}(P^{\prime})\) for all possible strings \(P^{\prime}\) and output the one whose \(\operatorname{cost}(Q,P^{\prime})\) is minimized. However, the time complexity of such a solution is \(O(|\Sigma|^{n}n^{3})\). In order to reduce the time complexity, we propose a dynamic programming algorithm, which generalizes Algorithm 1 as follows. In Algorithm 1, if a substring \(Q[i..j]\) is not periodic, we check two possible evaluations of \(D[i][j]\): partitioning \(Q[i..j]\) or leaving it as is. Here, even if \(Q[i..j]\) is not periodic, we may change it to be periodic by finding a periodic string \(Q^{\prime}\) of length \(i-j+1\), and \"paying\" the similarity cost cost between \(Q[i..j]\) and \(Q^{\prime}\) for this change. Hence, the final cost of \(Q[i..j]\) is defined recursively as the minimum between the following three values:  
1. The minimum cost of modifying \(Q\) to be \(r\)-periodic, over every possible period length \(r\). Formally, this is the minimal \(\operatorname{cost}(Q,q^{\#})\)+1, over every string \(q\in\Sigma^{\prime}\) and factor \(r\) of \(n\). 2. The minimum \(\operatorname{rcost}\) over all possible partitioning options of \(Q\). 3. The cost of representing \(Q\) as is, with no compression. To efficiently implement the above algorithm, we define the _r-Parikh Matrix_ of a given string and its factor \(r\), which we use throughout the algorithm. Intuitively, we define the string \(Q_{i,1}\) to be the same as the input string \(Q\) except that we change every \(r\)th letter of \(Q\) to \(\Sigma_{i}\). Hence, we changed at most \(n/r\) letters. More generally, in \(Q_{i,j}\) we do the same where \(j\) denotes the offset or first letter we change (beginning of count). The _r-_Parikh Matrix of \(Q\) contains the corresponding mismatching cost (Hamming distance) \(\text{scost}(Q_{i,j})\) in its \((i,j)\) entry. Examples will follow the definition. **Definition 5** (Parikh Matrix [28]). : _Let \(Q\in\Sigma^{n}\) be a string over an alphabet \(\Sigma=\left\{\Sigma_{1},\cdots,\Sigma_{|\Sigma|}\right\}\). Let \(r\geq 1\) be a factor of \(n\). For every \(i\in[\Sigma]\) and \(j\in[r]\), let \(Q_{i,j}\in\Sigma^{n}\) denote the string whose letters in the entries \(k\in\left\{j,j+r,j+2r,\ldots\right\}\) are replaced by \(\Sigma_{i}\); i.e., for every \(k\in[n]\) we have_  
\[Q_{i,j}^{r}[k]=Q_{i,j}[k]= \begin{cases}\Sigma_{i}&\text{if }(k\mod r)=j\\ Q[k]&\text{otherwise}\end{cases} .\]  
_The \(r\)-_Parikh Matrix_\(M=M^{r}(Q)\in\left\{0,1,\cdots,n/r\right\}^{|\Sigma|\times r}\) of \(Q\) is the matrix such that_  
\[M[i][j]=\text{scost}(Q_{i,j}).\]  
For example, let \(Q=(ababac)\) be a string over \(\Sigma=\left\{a,b,c\right\}\). If \(r=1\), then \(j\in[r]=\left\{1\right\}\), and therefore \(j=1\). That is, the period of changing a letter is \(1\) and thus all the letters will be modified. Indeed, for every \(k\in[n]\) we have \((k\mod r)=(k\mod 1)=0=j-1\). Hence, \(Q_{i,j}=Q_{i,1}=\Sigma_{i}^{n}\) consists of \(n\) copies of the letter \(\Sigma_{i}\). We obtain \(Q_{1,1}=(aaaaaa)\), \(Q_{2,1}=(bbbbbb)\), and \(Q_{3,1}=(ccccc)\). There are \(3\) corresponding mismatches of \(Q_{1,1}=(aaaaaa)\) compared to \(Q=(ababac)\), in indices \(k\in\left\{2,4,6\right\}\). Hence, \(M[1][1]=3\). Similarly, \(M[2][1]=3\) and \(M[3][1]=5\). The 1-Parikh matrix of \(Q\) is, thus, \(M(Q,1)=(3,3,5)^{T}\). If \(r=2\), then \(j\in\left\{1,2\right\}\). That is, we start the count with the first letter \(j=1\), which means in the above example that we change the letters in indices \(k\in\left\{1,3,5\right\}\).