# Re-Pair in Small Space +
## 3 Bit-Parallel Algorithm
### Bit-Parallel Adaption  
Similarly to Lemma 2, we present an algorithm computing the \(d\) most frequent bigrams, but now with the word-packed search of Lemma 5. Lemma 6: _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}(n^{2}\lg\lg\lg n/\log_{\sigma}n)\) time using \(d\left\lceil\lg(\sigma^{2}n/2)\right\rceil+\mathcal{O}(\lg n)\) bits._  
Proof. : We allocate a frequency table \(F\) of length \(d\). For each text position \(i\) with \(1\leq i\leq n-1\), we compute the frequency of \(T[i]T[i+1]\) in \(\mathcal{O}(n\lg\lg\lg n/\log_{\sigma}n)\) time with Lemma 5. After computing a frequency, we insert it into \(F\) if it is one of the \(d\) most frequent bigrams among the bigrams we have already computed. We can perform the insertion in \(\mathcal{O}(\lg d)\) time if we sort the entries of \(F\) by their frequencies, obtaining \(\mathcal{O}((n\lg\lg\lg n/\log_{\sigma}n+\lg d)n)\) total time. Studying the final time bounds of Equation (1) for the sequential algorithm of Section 2, we see that we spend \(\mathcal{O}(n^{2})\) time in the first turn, but spend less time in later turns. Hence, we want to run the bit-parallel algorithm only in the first few turns until \(f_{k}\) becomes so large that the benefits of running Lemma 2.1 outweigh the benefits of the bit-parallel approach of Lemma 2.1. In detail, for the \(k\)-th round, we set \(d:=f_{k}\) and run the algorithm of Lemma 2.1 on the current text if \(d\) is sufficiently small, or otherwise the algorithm of Lemma 2.1. In total, we obtain:  
Figure 5: Finding a bigram bb in a string \(S\) of bit length \(q\), where \(q\) is the largest multiple of \(2\lceil\lg\sigma\rceil\) fitting into a computer word, divided by \(\lceil\lg\sigma\rceil\). In the example, we represent the strings \(M\), \(B\), \(E\), and \(X\) as arrays of integers with bit width \(x:=\lceil\lg\sigma\rceil\) and write \(1\) and \(0\) for \(1^{x}\) and \(0^{x}\), respectively. Let \(\text{findBigram}(\text{bc},X):=\text{find}(\text{bc},X)\mid\text{find}(\text {bc},\text{d}X)\) for \(d\
eq b\) be the frequency of a bigram be with \(b\
eq c\) as described in Section 3.1, where the function find returns the output described in Figure 4. Each of the popcount queries gives us one occurrence as a result (after dividing the returned number by \(\lceil\lg\sigma\rceil\)), thus the frequency of bb in \(S\), without looking at the borders of \(S\), is two. As a side note, modern computer architectures allow us to shrink the \(0^{x}\) or \(1^{x}\) blocks to single bits by instructions like _pext_u64 taking a single CPU cycle. \[\mathcal{O}\left(\sum_{k=0}^{\mathcal{O}(\lg n)}\min\left(\frac{n-f_{k }}{f_{k}}n\lg f_{k},\frac{(n-f_{k})^{2}\lg\lg\lg n}{\log_{\tau}n}\right)\right) =\mathcal{O}\left(n^{2}\sum_{k=0}^{\lg n}\min\left(\frac{k}{\gamma^{k}},\frac{ \lg\lg\lg n}{\log_{\tau}n}\right)\right) \tag{3}\] \[=\mathcal{O}\left(\frac{n^{2}\lg\log_{\tau}n\lg\lg\lg n}{\log_{ \tau}n}\right)\text{time in total},\]  
where \(\tau=\sigma_{m}\) is the sum of the alphabet size \(\sigma\) and the number of non-terminals, and \(k/\gamma^{k}>\lg\lg\lg n/\log_{\tau}n\Leftrightarrow k=\mathcal{O}(\lg( \lg n/(\lg\lg\lg n)))\). To obtain the claim of Theorem 3.2, it is left to show that the \(k\)-th round with the bit-parallel approach uses \(\mathcal{O}(n^{2}\lg\lg n/\log_{\tau}n)\) time, as we now want to charge each text position with \(\mathcal{O}(n/\log_{\tau}n)\) time with the same amortized analysis as after Equation (1). We target \(\mathcal{O}(n/\log_{\tau}n)\) time for:  
1. replacing all occurrences of a bigram,
2. shifting freed up text space to the right,
3. finding the bigram with the highest or lowest frequency in \(F\),
4. updating or exchanging an entry in \(F\), and
5. looking up the frequency of a bigram in \(F\). Let \(x:=\left\lceil\lg\sigma_{i+1}\right\rceil\) and \(q\) be the largest multiple of \(x\) fitting into a computer word, divided by \(x\).