# Re-Pair in Small Space +
## 6 Computing Re-Pair in External Memory  
This part is devoted to the first external memory (EM) algorithms computing Re-Pair, which is another way to overcome the memory limitation problem. We start with the definition of the EM model, present an approach using a sophisticated heap data structure, and another approach adapting our in-place techniques.  
For the following, we use the EM model of [PERSON] [38]. It features fast internal memory (IM) holding up to \(M\) data words and slow EM of unbounded size. The measure of the performance of an algorithm is the number of input and output operations (I/Os) required, where each I/O transfers a block of \(B\) consecutive words between memory levels. Reading or writing \(n\) contiguous words from or to disk requires \(\text{scan}(n)=\Theta(n/B)\) I/Os. Sorting \(n\) contiguous words requires \(\text{sort}(n)=\mathcal{O}((n/B)\cdot\log_{M/B}(n/B))\) I/Os. For realistic values of \(n\), \(B\), and \(M\), we stipulate that \(\text{scan}(n)<\text{sort}(n)\ll n\).  
A simple approach is based on an EM heap maintaining the frequencies of all bigrams in the text. A state-of-the-art heap is due to [PERSON] and [PERSON] [39] providing insertion, deletion, and the retrieval of the maximum element in \(\mathcal{O}(B^{-1}\log_{M/B}(N/B))\) I/Os, where \(N\) is the size of the heap. Since \(N\leq n\), inserting all bigrams takes at most \(\text{sort}(n)\) I/Os. As there are at most \(n\) additional insertions, deletions, and maximum element retrievals, this sums to at most \(4\,\text{sort}(n)\) I/Os. Given Re-Pair has \(m\) turns, we need to scan the text \(m\) times to replace the occurrences of all \(m\) retrieved bigrams, triggering \(m\sum_{i=1}^{m}\text{scan}(|T_{i}|)\leq m\,\text{scan}(n)\) I/Os.  
In the following, we show an EM Re-Pair algorithm that evades the use of complicated data structures and prioritizes scans over sorting. This algorithm is based on our Re-Pair algorithm. It uses Lemma 2 with \(d:=\Theta(M)\) such that \(F\) and \(F^{\prime}\) can be kept in RAM.  
This allows us to perform all sorting steps and binary searches in IM without additional I/O. We only trigger I/O operations for scanning the text, which is done \(\lceil n/d\rceil\) times, since we partition \(T\) into \(d\) substrings. In total, we spend at most \(mn/M\) scans for the algorithm of Lemma 2. For the actual algorithm having \(m\) turns, we update \(F\)\(m\) times, during which we replace all occurrences of a chosen bigram in the text. This gives us \(m\) scans in total. Finally, we need to reason about \(D\), which we create \(m\) times. However, \(D\) may be larger than \(M\), such that we may need to store it in EM. Given that \(D_{i}\) is \(D\) in the \(i\)-th turn, we sort \(D\) in EM, triggering \(\operatorname{sort}(D_{i})\) I/Os. With the converse of [PERSON]'s inequality ([40], Theorem B) (set there \(f(x):=n\lg n\)), we obtain \(\sum_{i=1}^{m}\operatorname{sort}(|D_{i}|)\leq\operatorname{sort}(n)+ \mathcal{O}(n\log_{M/B}2)\) total I/Os for all instances of \(D\). We finally obtain:  
Theorem 4.1: _We can compute Re-Pair with \(\min(4\operatorname{sort}(n),(mn/M)\operatorname{scan}(n)+\operatorname{sort} (n)+\mathcal{O}(n\log_{M/B}2))+m\operatorname{scan}(n)\) I/Os in external memory._  
The latter approach can be practically favorable to the heap based approach if \(m=o(\lg n)\) and \(mn/M=o(\lg n)\), or if the EM space is also of major concern.