re-pair · research · also RePair, Recursive pairing

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

related
Grammar compression, Compression dictionary, Byte-pair encoding

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

  1. Larsson and Moffat: Offline Dictionary-Based Compression, DCC 1999, sections 2-4 (accessed 2026-11-17)
  2. Furuya et al.: Practical Grammar Compression Based on Maximal Repeats, Algorithms 13(4), 103 (2020), sections 2-5 (accessed 2026-11-17)
  3. Bille, Gortz and Prezza: Space-Efficient Re-Pair Compression, arXiv:1611.01479v1 (2016), sections 1-3 (accessed 2026-11-17)
  4. Hesela: Re-Pair rule, stream and encoded-byte accounting, executable teaching model (accessed 2026-11-17)
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.

JSON: /data/terms/re-pair.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Re-Pair compression. Hesela. 2026-11-17. https://hesela.dev/terms/re-pair/