# Re-Pair in Small Space +
## 2 Sequential Algorithm
### Algorithmic Ideas  
With Lemma 2, we can compute \(T_{m}\) in \(\mathcal{O}(mn^{2}\lg d/d)\) time with additional \(2d\left[\lg(\sigma_{m}^{2}n/2)\right]\) bits of working space on top of the text for a parameter \(d\) with \(1\leq d\leq n\). (The variable \(\tau\)used in the abstract and in the introduction is interchangeable with \(\sigma_{m}\), i.e., \(\tau=\sigma_{m}\).) In the following, we show how this leads us to our first algorithm computing Re-Pair:  
Theorem 1: _We can compute Re-Pair on a string of length \(n\) in \(\mathcal{O}(n^{2})\) time with \(\max((n/c)\lg n,\allowbreak n\lceil\lg\tau\rceil)+\mathcal{O}(\lg n)\) bits of working space including the text space as a rewritable part in the working space, where \(c\geq 1\) is a fixed constant and \(\tau=\sigma_{m}\) is the sum of the alphabet size \(\sigma\) and the number of non-terminal symbols._  
In our model, we assume that we can enlarge the text \(T_{i}\) from \(n_{i}\lceil\lg\sigma_{i}\rceil\) bits to \(n_{i}\lceil\lg\sigma_{i+1}\rceil\) bits without additional extra memory. Our main idea is to store a growing frequency table using the space freed up by replacing bigrams with non-terminals. In detail, we maintain a frequency table \(F\) in \(T_{i}\) of length \(f_{k}\) for a growing variable \(f_{k}\), which is set to \(f_{0}:=\mathcal{O}(1)\) in the beginning. The table \(F\) takes \(f_{k}\lceil\lg(\sigma_{i}^{2}n/2)\rceil\) bits, which is \(\mathcal{O}(\lg(\sigma^{2}n))=\mathcal{O}(\lg n)\) bits for \(k=0\). When we want to query it for a most frequent bigram, we linearly scan \(F\) in \(\mathcal{O}(f_{k})=\mathcal{O}(n)\) time, which is not a problem since (a) the number of queries is \(m\leq n\) and (b) we aim for \(\mathcal{O}(n^{2})\) as the overall running time. A consequence is that there is no need to sort the bigrams in \(F\) according to their frequencies, which simplifies the following discussion. Frequency table \(F\): With Lemma 2, we can compute \(F\) in \(\mathcal{O}(n\max(n,f_{k})\lg f_{k}/f_{k})\) time. Instead of recomputing \(F\) on every turn \(i\), we want to recompute it only when it no longer stores a most frequent bigram. However, it is not obvious when this happens as replacing a most frequent bigram during a turn (a) removes this entry in \(F\) and (b) can reduce the frequencies of other bigrams in \(F\), making them possibly less frequent than other bigrams not tracked by \(F\). Hence, the variable \(i\) for the \(i\)-th turn (creating the \(i\)-th non-terminal) and the variable \(k\) for recomputing the frequency table \(F\) the \((k+1)\)-st time are loosely connected. We group together all turns with the same \(f_{k}\) and call this group the _\(k\)-th round_ of the algorithm. At the beginning of each round, we enlarge \(f_{k}\) and create a new \(F\) with a capacity for \(f_{k}\) bigrams. Since a recomputation of \(F\) takes much time, we want to end a round only if \(F\) is no longer useful, i.e., when we no longer can guarantee that \(F\) stores a most frequent bigram. To achieve our claimed time bounds, we want to assign all \(m\) turns to \(\mathcal{O}(\lg n)\) different rounds, which can only be done if \(f_{k}\) grows sufficiently fast. Algorithm outline: At the beginning of the \(k\)-th round and the \(i\)-th turn, we compute the frequency table \(F\) storing \(f_{k}\) bigrams and keep additionally the lowest frequency of \(F\) as a threshold \(t_{k}\), which is treated as a constant during this round. During the computation of the \(i\)-th turn, we replace the most frequent bigram (say, \(\texttt{bc}\in\Sigma_{i}^{2}\)) in the text \(T_{i}\) with a non-terminal \(X_{i+1}\) to produce \(T_{i+1}\). Thereafter, we remove \(\texttt{bc}\) from \(F\) and update those frequencies in \(F\), which were decreased by the replacement of \(\texttt{bc}\) with \(X_{i+1}\) and add each bigram containing the new character \(X_{i+1}\) into \(F\) if its frequency is at least \(t_{k}\). Whenever a frequency in \(F\) drops below \(t_{k}\), we discard it.