  Given a string $T$ of length $N$, the goal of grammar compression is to
construct a small context-free grammar generating only $T$. Among existing
grammar compression methods, RePair (recursive paring) [Larsson and Moffat,
1999] is notable for achieving good compression ratios in practice. Although
the original paper already achieved a time-optimal algorithm to compute the
RePair grammar RePair($T$) in expected $O(N)$ time, the study to reduce its
working space is still active so that it is applicable to large-scale data. In
this paper, we propose the first RePair algorithm working in compressed space,
i.e., potentially $o(N)$ space for highly compressible texts. The key idea is
to give a new way to restructure an arbitrary grammar $S$ for $T$ into
RePair($T$) in compressed space and time. Based on the recompression technique,
we propose an algorithm for RePair($T$) in $O(\min(N, nm \log N))$ space and
expected $O(\min(N, nm \log N) m)$ time or $O(\min(N, nm \log N) \log \log N)$
time, where $n$ is the size of $S$ and $m$ is the number of variables in
RePair($T$). We implemented our algorithm running in $O(\min(N, nm \log N) m)$
time and show it can actually run in compressed space. We also present a new
approach to reduce the peak memory usage of existing RePair algorithms
combining with our algorithms, and show that the new approach outperforms, both
in computation time and space, the most space efficient linear-time RePair
implementation to date.
