Recursive pairing grammar compression. Repeatedly replaces the most frequent adjacent symbol pair with a new grammar rule until no pair repeats, producing a straight-line context-free grammar that generates the input exactly once.
| Property | Value |
|---|---|
| Category | Compression Algorithms |
| Sub-category | Grammar-based |
| Security status | Not classified |
| Complexity | Advanced |
| Inventor | N. Jesper Larsson, Alistair Moffat |
| Year | 1999 |
| Origin | 🇸🇪 Sweden |
| Source | algorithms/compression/repair.js |
Status: not classified — treat as unverified.
No vulnerabilities are recorded for this implementation.
4 vectors ship with this algorithm and run in the test suite. Byte values are hexadecimal.
Vector 1 — Empty input
| Field | Value |
|---|---|
input |
(empty) |
expected |
(empty) |
Vector 2 — Single repeated pair - ‘aaaa’ (RePair Wikipedia style example)
| Field | Value |
|---|---|
input |
61616161 |
expected |
(empty) |
Vector 3 — Repetitive text - ‘abcabcabc’
| Field | Value |
|---|---|
input |
616263616263616263 |
expected |
(empty) |
Vector 4 — No repeated pairs - ‘abcdef’
Source: Edge case - grammar reduces to zero rules
| Field | Value |
|---|---|
input |
616263646566 |
expected |
(empty) |