Re-pair is a grammar-based compression algorithm. In the poster session of the Data Compression Conference 2021, we propose the basic concepts of Parallel Re-pair, a parallel variant of Re-pair that achieves shorter compression time with multi-core CPUs. However, our experimental results show it achieves only 1.6 to 2.4 times faster with 32 processors. In this poster session, we propose practical implementation of Parallel Re-pair with Intel Threading Building Blocks.

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.