# Re-Pair in Small Space +
## 3 Bit-Parallel Algorithm
### Broadword Search  
First, we deal with accelerating the computation of the frequency of a bigram in \(T\) by exploiting broadword search thanks to the word RAM model. We start with the search of single characters and subsequently extend this result to bigrams: \begin{table}
\begin{tabular}{l c c c c c c c c c c c} \hline \hline  & & & \multicolumn{6}{c}{**Turns/1000**} & \multicolumn{6}{c}{**Rounds**} \\
**Data Set** & \(\sigma\) & \multicolumn{6}{c}{**Prefix Size in KiB**} & \multicolumn{6}{c}{**Prefix Size in KiB**} \\ \cline{3-11}  & & **26** & **27** & **28** & **29** & **210** & **26** & **27** & **28** & **29** & **210** \\ \hline Escherichia\_Coli & 4 & 1.8 & 3.2 & 5.6 & 10.3 & 18.1 & 6 & 9 & 9 & 12 & 12 \\ cere & 5 & 1.4 & 2.8 & 5.0 & 9.2 & 15.1 & 13 & 14 & 14 & 14 & 14 \\ coreutils & 113 & 4.7 & 6.7 & 10.2 & 16.1 & 26.5 & 15 & 15 & 15 & 14 & 14 \\ Einstein\_DE\_txt & 95 & 1.7 & 2.8 & 3.7 & 5.2 & 9.7 & 14 & 14 & 15 & 16 & 16 \\ Einstein\_EN\_TXT & 87 & 3.3 & 3.5 & 3.8 & 4.5 & 8.6 & 16 & 15 & 15 & 15 & 17 \\ influenza & 7 & 2.5 & 3.7 & 9.5 & 13.4 & 22.1 & 11 & 12 & 14 & 13 & 15 \\ kernel & 160 & 4.5 & 8.0 & 13.9 & 24.5 & 43.7 & 10 & 11 & 14 & 14 & 13 \\ para & 5 & 1.8 & 3.2 & 5.8 & 10.1 & 17.6 & 12 & 12 & 13 & 13 & 14 \\ world\_DE\_leaders & 87 & 2.6 & 4.3 & 6.1 & 10.0 & 42.1 & 11 & 11 & 11 & 14 \\ \hline aa\(\cdots\)a & 1 & 15 & 16 & 17 & 18 & 19 & 16 & 17 & 18 & 19 & 20 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Characteristics of our data sets used in Section 2.6. The number of turns and rounds are given for each of the prefix sizes 128, 256, 512, and 1024 KiB of the respective data sets. The number of turns reflecting the number of non-terminals is given in units of thousands. The turns of the unary string aa\(\cdots\)a are in plain units (not divided by thousand). Figure 2: Operations used in Figures 4 and 5 for two bit vectors \(X\) and \(Y\). All operations can be computed in constant time. See Figure 3 for an example of rmSufRun and rmPreRun. **Lemma 4**. : _We can count the occurrences of a character \(c\in\Sigma\) in a string of length \(\mathcal{O}(\log_{w}n)\) in \(\mathcal{O}(\log\lg\lg n)\) time._  
Proof. : Let \(q\) be the largest multiple of \(\lceil\lg\sigma\rceil\) fitting into a computer word, divided by \(\lceil\lg\sigma\rceil\). Let \(S\in\Sigma^{*}\) be a string of length \(q\). Our first task is to compute a bit mask of length \(q\lceil\lg\sigma\rceil\) marking the occurrences of a character \(c\in\Sigma\) in \(S\) with a '1'. For that, we follow the constant time broadword pattern matching of [PERSON] (1976) (Section 7.1.3); see [[https://github.com/koeppl/broadwordsearch](https://github.com/koeppl/broadwordsearch)]([https://github.com/koeppl/broadwordsearch](https://github.com/koeppl/broadwordsearch)) for a practical implementation. Let \(H\) and \(L\) be two bit vectors of length \(\lceil\lg\sigma\rceil\) having marked only the most significant or the least significant bit, respectively. Let \(H^{q}\) and \(L^{q}\) denote the \(q\) times concatenation of \(H\) and \(L\), respectively. Then, the operations in Figure 4 yield an array \(X\) of length \(q\) with:  
\[X[i]= \begin{cases}2^{\lceil\lg\sigma\rceil}-1&\text{ if }S[i]=c,\\ 0&\text{ otherwise,}\end{cases}  \tag{2}\]  
where each entry of \(X\) has \(\lceil\lg\sigma\rceil\) bits. Figure 4: Matching all occurrences of a character in a string \(S\) fitting into a computer word in constant time by using bit-parallel instructions. For the last step, special care has to be taken when the last character of \(S\) is a match, as shifting \(X\)\(\lceil\lg\sigma\rceil\) bits to the right might erase a ’1’ bit witnessing the rightmost match. In the description column, \(X\) is treated as an array of integers with bit width \(\lceil\lg\sigma\rceil\). In this example, \(S=\texttt{101010000}\), \(c\) has the bit representation \(\texttt{010}\) with \(\lg\sigma=3\), and \(q=3\). Figure 3: Step-by-step execution of \(\text{rmPreRun}(X)\) and \(\text{rmSuffRun}(X)\) introduced in Figure 2 on a bit vector \(X\).