# Re-Pair in Small Space +
## 2 Sequential Algorithm
### Algorithmic Details  
Suppose that we are in the \(k\)-th round and in the \(i\)-th turn. Let \(t_{k}\) be the lowest frequency in \(F\) computed at the beginning of the \(k\)-th round. We keep \(t_{k}\) as a constant threshold for the invariant that all frequencies in \(F\) are at least \(t_{k}\) during the \(k\)-th round. With this threshold, we can assure in the following that \(F\) is either empty or stores a most frequent bigram. Now suppose that the most frequent bigram of \(T_{i}\) is \(\texttt{bc}\in\Sigma_{i}^{2}\), which is stored in \(F\). To produce \(T_{i+1}\) (and hence advancing to the \((i+1)\)-st turn), we enlarge the space of \(T_{i}\) from \(n_{i}[\lg\sigma_{i}]\) to \(n_{i}[\lg\sigma_{i+1}]\) and replace all occurrences of \(\texttt{bc}\) in \(T_{i}\) with a new non-terminal \(X_{i+1}\). Subsequently, we would like to take the next bigram of \(F\). For that, however, we need to update the stored frequencies in \(F\). To see this necessity, suppose that there is an occurrence of \(\texttt{abcd}\) with two characters \(\texttt{a},\texttt{d}\in\Sigma_{i}\) in \(T_{i}\). By replacing \(\texttt{bc}\) with \(X_{i+1}\),  
1. the frequencies of \(\texttt{ab}\) and \(\texttt{cd}\) decrease by one (for the border case \(\texttt{a}=\texttt{b}=\texttt{c}\) (resp. \(\texttt{b}=\texttt{c}\) = d), there is no need to decrement the frequency of \(\texttt{ab}\) (resp. \(\texttt{cd}\))), and
2. the frequencies of \(\texttt{a}X_{i+1}\) and \(X_{i+1}\texttt{d}\) increase by one. Updating \(F\). We can take care of the former changes (1) by decreasing the respective bigram in \(F\) (in the case that it is present). If the frequency of this bigram drops below the threshold \(t_{k}\), we remove it from \(F\) as there may be bigrams with a higher frequency that are not present in \(F\). To cope with the latter changes (2), we track the characters adjacent to \(X_{i+1}\) after the replacement, count their numbers, and add their respective bigrams to \(F\) if their frequencies are sufficiently high. In detail, suppose that we have substituted be with \(X_{i+1}\) exactly \(h\) times. Consequently, with the new text \(T_{i+1}\) we have additionally \(h\lg\sigma_{i+1}\) bits of free space (the free space is consecutive after shifting all characters to the left), which we call \(D\) in the following. Subsequently, we scan the text and put the characters of \(\Sigma_{i+1}\) appearing to the left of each of the \(h\) occurrences of \(X_{i+1}\) into \(D\). After sorting the characters in \(D\) lexicographically, we can count the frequency of \(\texttt{a}X_{i+1}\) for each character \(\texttt{a}\in\Sigma_{i+1}\) preceding an occurrence of \(X_{i+1}\) in the text \(T_{i+1}\) by scanning \(D\) linearly. If the obtained frequency of such a bigram \(\texttt{a}X_{i+1}\) is at least as high as the threshold \(t_{k}\), we insert \(\texttt{a}X_{i+1}\) into \(F\) and subsequently discard a bigram with the currently lowest frequency in \(F\) if the size of \(F\) has become \(f_{k}+1\). In the case that we visit a run of \(X_{i+1}\)'s during the creation of \(D\), we must take care of not counting the overlapping occurrences of \(X_{i+1}X_{i+1}\). Finally, we can count analogously the occurrences of \(X_{i+1}\texttt{d}\) for all characters \(\texttt{d}\in\Sigma_{i}\) succeeding an occurrence of \(X_{i+1}\). Capacity of \(F\): After the above procedure, we update the frequencies of \(F\). When \(F\) becomes empty, all bigrams stored in \(F\) are replaced or have a frequency that becomes less than \(t_{k}\). Subsequently, we end the \(k\)-th round and continue with the \((k+1)\)-st round by (a) creating a new frequency table \(F\) with capacity \(f_{k+1}\) and (b) setting the new threshold \(t_{k+1}\) to the minimal frequency in \(F\).