Re-Pair is a dictionary-based compression method invented in 1999 by Larsson
and Moffat. Although its practical performance has been established through
experiments, the method has resisted all attempts of formal analysis. In this
paper we show that Re-Pair compresses a sequence
over an alphabet of
size
and
-th order entropy
, to at most
bits, for any
.