RePair in Compressed Space and Time

Abstract

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. 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 (context-free) grammar S for T into RePair(T) in compressed space and time. We propose an algorithm for RePair(T) running 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 O(min(N, nm log N) m)-time algorithm 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.