Parallel Processing of Grammar Compression

Re-pair is a grammar-based compression algorithm. It achieves higher compression rates for text, graph, and tree than other general compression algorithms. While Re-pair is linear-time algorithm, it is slower than other algorithms in practice. In this paper, we present Parallel Re-pair, a novel variant that enables parallel processing of Re-pair. In Parallel Re-pair, Re-pair is executed on CPU cores with a shared dictionary to synchronize allocations of variables. Thus, compressed strings can be simply merged without reallocation of variables. Our experiments show that Parallel Re-Pair significantly reduces compression time with up to 16 or 32 CPU cores.