# Re-Pair in Small Space +
## 2 Sequential Algorithm
### Algorithmic Details
In what follows, we (a) analyze in detail when \(F\) becomes empty (as this determines the sizes \(f_{k}\) and \(f_{k+1}\)) and (b) show that we can compensate the number of discarded bigrams with an enlargement of \(F\)'s capacity from \(f_{k}\) bigrams to \(f_{k+1}\) bigrams for the sake of our aimed total running time. Next, we analyze how many characters we have to free up (i.e., how many bigram occurrences we have to replace) to gain enough space for storing an additional frequency. Let \(\delta_{i}:=\lg(\sigma_{i+1}^{2}n_{i}/2)\) be the number of bits needed to store one entry in \(F\), and let \(\beta_{i}:=\min(\delta_{i}/\lg\sigma_{i+1},c\delta_{i}/\lg n)\) be the minimum number of characters that need to be freed to store one frequency in this space. To understand the value of \(\beta_{i}\), we look at the arguments of the minimum function in the definition of \(\beta_{i}\) and simultaneously at the maximum function in our aimed working space of \(\max(n\lceil\lg\sigma_{m}\rceil,(n/c)\lg n)+\mathcal{O}(\lg n)\) bits (cf. Theorem 1):  
1. The first item in this maximum function allows us to spend \(\lg\sigma_{i+1}\) bits for each freed character such that we obtain space for one additional entry in \(F\) after freeing \(\delta_{i}/\lg\sigma_{i+1}\) characters. 2. The second item allows us to use \(\lg n\) additional bits after freeing up \(c\) characters. This additional treatment helps us to let \(f_{k}\) grow sufficiently fast in the first steps to save our \(\mathcal{O}(n^{2})\) time bound, as for sufficiently small alphabets and large text sizes, \(\lg(\sigma^{2}n/2)/\lg\sigma=\mathcal{O}(\lg n)\), which means that we might run the first \(\mathcal{O}(\lg n)\) turns with \(f_{k}=\mathcal{O}(1)\) and, therefore, already spend \(\mathcal{O}(n^{2}\lg n)\) time. Hence, after freeing up \(c\delta_{i}/\lg n\) characters, we have space to store one additional entry in \(F\). With \(\beta_{i}=\min(\delta_{i}/\lg\sigma_{i+1},c\delta_{i}/\lg n)=\mathcal{O}(\log _{o}n)\cap\mathcal{O}(\log_{n}\sigma)=\mathcal{O}(1)\), we have the sufficient condition that replacing a constant number of characters gives us enough space for storing an additional frequency. If we assume that replacing the occurrences of a bigram stored in \(F\) does not decrease the other frequencies stored in \(F\), the analysis is now simple: Since each bigram in \(F\) has a frequency of at least two, \(f_{k+1}\geq f_{k}+f_{k}/\beta_{i}\). Since \(\beta_{i}=\mathcal{O}(1)\), this lets \(f_{k}\) grow exponentially, meaning that we need \(\mathcal{O}(\lg n)\) rounds. In what follows, we show that this is also true in the general case. Lemma 3: _Given that the frequency of all bigrams in \(F\) drops below the threshold \(t_{k}\) after replacing the most frequent bigram bc, then its frequency has to be at least \(\max(2,|F|-1/2)\), where \(|F|\leq f_{k}\) is the number of frequencies stored in \(F\)._  
Proof: If the frequency of bc in \(T_{i}\) is \(x\), then we can reduce at most \(2x\) frequencies of other bigrams (both the left character and the right character of each occurrence of bc can contribute to an occurrence of another bigram). Since a bigram must occur at least twice in \(T_{i}\) to be present in \(F\), the frequency of bc has to be at least \(\max(2,(f_{k}-1)/2)\) for discarding all bigrams of \(F\). Suppose that we have enough space available for storing the frequencies of \(\alpha_{i}f_{k}\) bigrams, where \(\alpha_{i}\) is a constant (depending on \(\sigma_{i}\) and \(n_{i}\)) such that \(F\) and the working space of Lemma 2 with \(d=f_{k}\) can be stored within this space.