# Re-Pair in Small Space +
## 5 Parallel Algorithm  
Suppose that we have \(p\) processors on a concurrent read concurrent write (CRCW) machine, supporting in particular parallel insertions of elements and frequency updates in a frequency table. In the parallel setting, we allow us to spend \(\mathcal{O}(p\lg n)\) bits of additional working space such that each processor has an extra budget of \(\mathcal{O}(\lg n)\) bits. In our computational model, we assume that the text is stored in \(p\) parts of equal lengths, which we can achieve by padding up the last part with dummy characters to have \(n/p\) characters for each processor, such that we can enlarge a text stored in \(n\lg\sigma\) bits to \(n(\lg\sigma+1)\) bits in \(\max(1,n/p)\) time without extra memory. For our parallel variant computing Re-Pair, our working horse is a parallel sorting algorithm:  
**Lemma 7** ([37]). : _We can sort an array of length \(n\) in \(\mathcal{O}(\max(n/p,1)\lg^{2}n)\) parallel time with \(\mathcal{O}(p\lg n)\) bits of working space. The work is \(\mathcal{O}(n\lg^{2}n)\)._  
The parallel sorting allows us to state Lemma 2 in the following way:  
**Lemma 8**. : _Given an integer \(d\) with \(d\geq 1\), we can compute the frequencies of the \(d\) most frequent bigrams in a text of length \(n\) whose characters are drawn from an alphabet of size \(\sigma\) in \(\mathcal{O}(\max(n,d)\max(n/p,1)\lg^{2}d/d)\) time using \(2d\)\(\lceil\lg(\sigma^{2}n/2)\rceil+\mathcal{O}(p\lg n)\) bits. The work is \(\mathcal{O}(\max(n,d)n\lg^{2}d/d)\)._  
Proof. : We follow the computational steps of Lemma 2, but (a) divide a scan into \(p\) parts, (b) conduct a scan in parallel but a binary search sequentially, and (c) use Lemma 7 for the sorting. This gives us the following time bounds for each operation: \begin{tabular}{l l l} \hline \hline Operation & Lemma 2 & Parallel \\ \hline fill \(F^{\prime}\) with bigrams & \(\mathcal{O}(d)\) & \(\mathcal{O}(\max(d/p,1))\) \\ sort \(F^{\prime}\) lexicographically & \(\mathcal{O}(d\lg d)\) & \(\mathcal{O}(\max(d/p,1)\lg^{2}d)\) \\ compute frequencies of \(F^{\prime}\) & \(\mathcal{O}(n\lg d)\) & \(\mathcal{O}(n/p\lg d)\) \\ merge \(F^{\prime}\) with \(F\) & \(\mathcal{O}(d\lg d)\) & \(\mathcal{O}(\max(d/p,1)\lg^{2}d)\) \\ \hline \hline \end{tabular}   
The \(\mathcal{O}(n/d)\) merge steps are conducted in the same way, yielding the bounds of this lemma. In our sequential model, we produce \(T_{i+1}\) by performing a left shift of the gained space after replacing all occurrences of a most frequent bigram with a new non-terminal \(X_{i+1}\) such that we accumulate all free space at the end of the text. As described in our computational model, our text is stored as a partition of \(p\) substrings, each assigned to one processor. Instead of gathering the entire free space at \(T\)'s end, we gather free space at the end of each of these substrings. We bookkeep the size and location of each such free space (there are at most \(p\) many) such that we can work on the remaining text \(T_{i+1}\) like it would be a single continuous array (and not fragmented into \(p\) substrings). This shape allows us to perform the left shift in \(\mathcal{O}(n/p)\) time, while spending \(\mathcal{O}(p\lg n)\) bits of space for maintaining the locations of the free space fragments. For \(p\leq n\), exchanging Lemma 2 with Lemma 8 in Equation (1) gives:  
\[\mathcal{O}\!\left(\sum_{k=0}^{\mathcal{O}(\lg n)}\frac{n-f_{k}}{f_{k}}\frac{n}{p }\lg^{2}f_{k}\right)=\mathcal{O}\!\left(\frac{n^{2}}{p}\sum_{k}^{\lg n}\frac{k ^{2}}{\gamma^{k}}\right)=\mathcal{O}\!\left(\frac{n^{2}}{p}\right)\text{ time in total}.\]  
It is left to provide an amortized analysis for updating the frequencies in \(F\) during the \(i\)-th turn. Here, we can charge each text position with \(\mathcal{O}(n/p)\) time, as we have the following time bounds for each operation: