# Re-Pair in Small Space +
## 2 Sequential Algorithm
### Implementation  
At [[https://github.com/koeppl/repair-inplace](https://github.com/koeppl/repair-inplace)]([https://github.com/koeppl/repair-inplace](https://github.com/koeppl/repair-inplace)), we provide a simplified implementation in C++17. The simplification is that we (a) fix the bit width of the text space to 16 bit  
Figure 1: Step-by-step execution of the first turn of our algorithm on the string \(T=\texttt{cabaacabcabaacaaabcbabacaaabcb}\). The turn starts with the memory configuration given in Row 1. Positions 1 to 21 are text positions, and Positions 22 to 24 belong to \(F\) (\(f_{0}=3\), and it is assumed that a frequency fits into a text entry). Subsequent rows depict the memory configuration during Turn 1. A comment on each row is given in Section 2.5.  
and (b) assume that \(\Sigma\) is the byte alphabet. We further skip the step increasing the bit width of the text from \(\lg\sigma_{i}\) to \(\lg\sigma_{i+1}\). This means that the program works as long as the characters of \(\Sigma_{m}\) fit into 16 bits. The benchmark, whose results are displayed in Table 1, was conducted on a Mac Pro Server with an Intel Xeon CPU X5670 clocked at 2.93 GHz running Arch Linux. The implementation was compiled with gcc-8.2.1 in the highest optimization mode -03. Looking at Table 1, we observe that the running time is super-linear to the input size on all text instances, which we obtained from the Pizzaf&Chili corpus ([[http://pizzachili.dcc.uchile.cl/](http://pizzachili.dcc.uchile.cl/)]([http://pizzachili.dcc.uchile.cl/](http://pizzachili.dcc.uchile.cl/))). We conducted the same experiments with an implementation of [PERSON] ([[https://users.dcc.uchile.cl/~gnavarro/software/repair.tgz](https://users.dcc.uchile.cl/~gnavarro/software/repair.tgz)]([https://users.dcc.uchile.cl/~gnavarro/software/repair.tgz](https://users.dcc.uchile.cl/~gnavarro/software/repair.tgz))) in Table 2 with considerably better running times while restricting the algorithm to use 1 MB of RAM during execution. Table 3 gives some characteristics about the used data sets. We see that the number of rounds is the number of turns plus one for every unary string a\({}^{2k}\) with an integer \(k\geq 1\) since the text contains only one bigram with a frequency larger than two in each round. Replacing this bigram in the text makes \(F\) empty such that the algorithm recomputes \(F\) after each turn. Note that the number of rounds can drop while scaling the prefix length based on the choice of the bigrams stored in \(F\). \begin{table}
\begin{tabular}{l c c c c c c c c c} \hline \hline  & \multicolumn{6}{c}{**Our Implementation**} & \multicolumn{6}{c}{**Implementation of Navarro**} \\ \cline{2-10}
**Data Set** & \multicolumn{6}{c}{**Prefix Size in KiB**} \\ \cline{2-10}  & **64** & **128** & **256** & **512** & **1024** & **64** & **128** & **256** & **512** & **1024** \\ \hline Escherichia\_Coli & 20.68 & 130.47 & 516.67 & 1708.02 & 10,112.47 & 0.01 & 0.02 & 0.07 & 0.18 & 0.29 \\ cere & 13.69 & 90.83 & 443.17 & 2125.17 & 9185.58 & 0.01 & 0.02 & 0.04 & 0.16 & 0.22 \\ COREutils & 12.88 & 75.64 & 325.51 & 1502.89 & 5144.18 & 0.01 & 0.05 & 0.05 & 0.14 & 0.29 \\ EINSTEIN.DE.TXT & 19.55 & 88.34 & 181.84 & 805.81 & 4559.79 & 0.01 & 0.04 & 0.08 & 0.10 & 0.25 \\ EINSTEIN.EN.TXT & 21.11 & 78.57 & 160.41 & 900.79 & 4353.81 & 0.01 & 0.02 & 0.05 & 0.21 & 0.51 \\ INFLUENZA & 41.01 & 160.68 & 667.58 & 2630.65 & 10,526.23 & 0.03 & 0.02 & 0.05 & 0.11 & 0.36 \\ KERNEL & 20.53 & 101.84 & 208.08 & 1575.48 & 5067.80 & 0.01 & 0.04 & 0.09 & 0.18 & 0.27 \\ PARA & 20.90 & 175.93 & 370.72 & 2826.76 & 9462.74 & 0.01 & 0.01 & 0.08 & 0.12 & 0.35 \\ WORLD\_Leaders & 11.92 & 21.82 & 167.52 & 661.52 & 1718.36 & 0.01 & 0.01 & 0.06 & 0.11 & 0.25 \\ \hline aa\(\cdots\)a & 0.35 & 0.92 & 3.90 & 14.16 & 61.74 & 0.01 & 0.01 & 0.05 & 0.05 & 0.12 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Experimental evaluation of our implementation and the implementation of Navarro described in Section 2.6. Table entries are running times in seconds.