  Data compression is a powerful tool for managing massive but repetitive
datasets, especially schemes such as grammar-based compression that support
computation over the data without decompressing it. In the best case such a
scheme takes a dataset so big that it must be stored on disk and shrinks it
enough that it can be stored and processed in internal memory. Even then,
however, the scheme is essentially useless unless it can be built on the
original dataset reasonably quickly while keeping the dataset on disk. In this
paper we show how we can preprocess such datasets with context-triggered
piecewise hashing such that afterwards we can apply RePair and other
grammar-based compressors more easily. We first give our algorithm, then show
how a variant of it can be used to approximate the LZ77 parse, then leverage
that to prove theoretical bounds on compression, and finally give experimental
evidence that our approach is competitive in practice.
