Re-Pair compression
Re-Pair is an offline grammar compressor that repeatedly replaces a most frequent adjacent symbol pair with a new symbol and records its expansion rule.
Mechanism: After each replacement round, pair frequencies are recomputed on the reduced sequence; new symbols can participate in later pairs. The decoder needs both the remaining sequence and the recursively defined rules. [1]
Overlap: Replacing aa in aaaa produces two A symbols, not three. The teaching model counts disjoint occurrences for each candidate pair and replaces them left to right; aaa alone supplies only one such occurrence. [1] [4]
Ties: Equal-frequency pairs need a selection policy. Different choices can produce different grammar sizes; Re-Pair is not a unique canonical encoding. The finite example aaabaabaab yields 9 versus 8 right-hand-side symbols under the documented minimum/maximum-ID policies. [2] [4]
Storage: In the teaching wire format, abababab becomes two rules and two root symbols: 6 grammar symbols, but 24 encoded bytes including the header. This deliberately simple encoding is not the original paper's compact dictionary and entropy coder. [4]
Relations
Limitations
- The model rescans small inputs and does not implement the papers' efficient data structures or establish their time and memory bounds. [4, 3]
Citations
- Larsson and Moffat: Offline Dictionary-Based Compression, DCC 1999, sections 2-4
- Furuya et al.: Practical Grammar Compression Based on Maximal Repeats, Algorithms 13(4), 103 (2020), sections 2-5
- Bille, Gortz and Prezza: Space-Efficient Re-Pair Compression, arXiv:1611.01479v1 (2016), sections 1-3
- Hesela: Re-Pair rule, stream and encoded-byte accounting, executable teaching model
Sources & caveats
- Source-grounded algorithm explanation and constructed byte examples; no production throughput, fleet metric or benchmark replication.
- Research status identifies the algorithm literature, not an assertion that implementations do not exist.