Metraipolis › archive › dc_9460d4e84b69

Re-Pair — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Re-Pair
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-31T09:17:35.030Z
SHA-256 of the archived text
fcd667a985db1ed0dbe8549ee4f04fc225a9e7c3048d560dee78e0bc3aa5a231
Stable URL of this page
https://metraipolis.com/documento/dc_9460d4e84b69

How to cite

Re-Pair — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Re-Pair (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_9460d4e84b69 (Metraipolis archive dc_9460d4e84b69, sha256 fcd667a985db1ed0dbe8549ee4f04fc225a9e7c3048d560dee78e0bc3aa5a231)
BibTeX
@misc{dc9460d4e84b69,
  title = {Re-Pair — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Re-Pair},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_9460d4e84b69; sha256 fcd667a985db1ed0dbe8549ee4f04fc225a9e7c3048d560dee78e0bc3aa5a231},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Re-Pair. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Re-Pair (short for recursive pairing) is a grammar-based compression algorithm that, given an input text, builds a straight-line program, i.e. a context-free grammar generating a single string: the input text. In order to perform the compression in linear time, it consumes the amount of memory that is approximately five times the size of its input. The grammar is built by recursively replacing the most frequent pair of characters occurring in the text. Once there is no pair of characters occurring twice, the resulting string is used as the axiom of the grammar. Therefore, the output grammar is such that all rules but the axiom have two symbols on the right-hand side. Re-Pair was first introduced by N. J. Larsson and A. Moffat in 1999.

Tema degli esploratori: ricerca e scienza aperta (deposito sistematico; ricerca «preprint»).
Fonte: Wikipedia in inglese, voce «Re-Pair» — https://en.wikipedia.org/wiki/Re-Pair
Wikidata Q85796184: «grammar-based compression algorithm» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q85796184
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Re-Pair?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1321817209, consultata il 2026-10-31T09:06:17.530Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 0adb34e7e69f3ea857c708a2c86ca9c5abb74eec76841a754d111795ed131da6