# Re-Pair in Small Space +
## 3 Bit-Parallel Algorithm
### Broadword Search
To obtain the number of occurrences of \(c\) in \(S\), we use the popcount operation returning the number of zero bits in \(X\) and divide the result by \(\lceil\lg\sigma\rceil\). The popcount instruction takes \(\mathcal{O}(\lg\lg\lg n)\) time ([34] Algorithm 1). Having Lemma 4, we show that we can compute the frequency of a bigram in \(T\) in \(\mathcal{O}(n\lg\lg\lg n/\log_{\sigma}n)\) time. For that, we interpret \(T\in\Sigma^{n}\) of length \(n\) as a text \(T\in(\Sigma^{2})^{\lceil n/2\rceil}\) of length \(\lceil n/2\rceil\). Then, we partition \(T\) into strings fitting into a computer word and call each string of this partition a _chunk_. For each chunk, we can apply Lemma 4 by treating a bigram \(c\in\Sigma^{2}\) as a single character. The result is, however, not the frequency of the bigram \(c\) in general. For computing the frequency a bigram \(\texttt{bc}\in\Sigma^{2}\), we distinguish the cases \(\texttt{b}\
eq\texttt{c}\) and \(\texttt{b}=\texttt{c}\). Case \(\texttt{b}\
eq\texttt{c}\): By applying Lemma 4 to find the character \(\texttt{bc}\in\Sigma^{2}\) in a chunk \(S\) (interpreted as a string of length \(\lfloor q/2\rfloor\) on the alphabet \(\Sigma^{2}\)), we obtain the number of occurrences of \(\texttt{bc}\) starting at odd positions in \(S\). To obtain this number for all even positions, we apply the procedure to \(\texttt{dS}\) with \(\texttt{d}\in\Sigma\setminus\{\texttt{b},\texttt{c}\}\). Additional care has to be taken at the borders of each chunk matching the last character of the current chunk and the first character of the subsequent chunk with \(\texttt{b}\) and \(\texttt{c}\), respectively. Case \(\texttt{b}=\texttt{c}\): This case is more involving as overlapping occurrences of \(\texttt{bb}\) can occur in \(S\), which we must not count. To this end, we watch out for _runs_ of \(\texttt{b}\)'s, i.e., substrings of maximal lengths consisting of the character \(\texttt{b}\) (here, we consider also maximal substrings of \(\texttt{b}\) with length one as a run). We separate these runs into runs ending either at even or at odd positions. We do this because the frequency of \(\texttt{bb}\) in a run of \(\texttt{b}\)'s ending at an even (resp. odd) position is the number of occurrences of \(\texttt{bb}\) within this run ending at an even (resp. odd) position. We can compute these positions similarly to the approach for \(\texttt{b}\
eq\texttt{c}\) by first (a) hiding runs ending at even (resp. odd) positions and then (b) counting all bigrams ending at even (resp. odd) positions. Runs of \(\texttt{b}\)'s that are a prefix or a suffix of \(S\) are handled individually if \(S\) is neither the first nor the last chunk of \(T\), respectively. That is because a run passing a chunk border starts and ends in different chunks. To take care of those runs, we remember the number of \(\texttt{b}\)'s of the longest suffix of every chunk and accumulate this number until we find the end of this run, which is a prefix of a subsequent chunk. The procedure for counting the frequency of \(\texttt{bb}\) inside \(S\) is explained with an example in Figure 5. With the aforementioned analysis of the runs crossing chunk borders, we can extend this procedure to count the frequency of \(\texttt{bb}\) in \(T\). We conclude:  
Lemma 5: _We can compute the frequency of a bigram in a string \(T\) of length \(n\) whose characters are drawn from an alphabet of size \(\sigma\) in \(\mathcal{O}(n\lg\lg\lg n/\log_{\sigma}n)\) time._