Grammar-Based Compression, in depth: straight-line programs, Re-Pair and Sequitur, random access without decompression and honest measurements

A string as a one-word grammar

A straight-line program (SLP) is a grammar in which every nonterminal has exactly one rule and rules refer only to earlier nonterminals, so there is no choice and no recursion: each nonterminal expands to one fixed string. For abababab:

X1 -> a b        # "ab"
X2 -> X1 X1      # "abab"
S  -> X2 X2      # "abababab"

The size of a grammar is the total length of its right-hand sides, here 6 for an 8-character string. The savings compound: k doubling rules generate a string of length 2^k, so an SLP can be exponentially smaller than its text. The same property makes SLPs a decompression-bomb hazard, discussed under failure modes.

Finding the smallest grammar for a string is NP-hard. Charikar and co-authors (2005) showed that, unless P = NP, no polynomial-time algorithm can always come within a factor of 8569/8568 of the optimum, and analysed practical compressors against it. Rytter (2003) linked grammars to LZ77: the smallest grammar is at least as large as the number of phrases in the LZ77 factorisation without self-references, and an LZ77 parse can be turned into a grammar only a logarithmic factor larger. Grammars and LZ77 measure the same kind of repetition; grammars pay a little size for structure.

Re-Pair: replace the most frequent pair

Re-Pair, published by Larsson and Moffat, is a greedy offline algorithm: find the most frequent pair of adjacent symbols, replace every non-overlapping occurrence with a new symbol, record the rule, and repeat until no pair occurs twice. Every rule has exactly two symbols on its right-hand side, which makes the grammar easy to store and navigate.

from collections import Counter

def count_pairs(seq):
    """Count adjacent pairs without double-counting overlaps in runs like x x x."""
    counts, i = Counter(), 0
    while i < len(seq) - 1:
        counts[(seq[i], seq[i + 1])] += 1
        if seq[i] == seq[i + 1] and i + 2 < len(seq) and seq[i + 2] == seq[i]:
            i += 2
        else:
            i += 1
    return counts

def repair(data: bytes):
    seq, rules, next_sym = list(data), {}, 256      # symbols >= 256 are rules
    while True:
        counts = count_pairs(seq)
        if not counts:
            break
        pair, freq = counts.most_common(1)[0]
        if freq < 2:
            break
        rules[next_sym] = pair
        out, i = [], 0
        while i < len(seq):                          # left-to-right replacement
            if i + 1 < len(seq) and (seq[i], seq[i + 1]) == pair:
                out.append(next_sym); i += 2
            else:
                out.append(seq[i]); i += 1
        seq, next_sym = out, next_sym + 1
    return seq, rules

def expand(seq, rules):
    out, stack = [], list(reversed(seq))             # iterative: no recursion limit
    while stack:
        s = stack.pop()
        if s in rules:
            a, b = rules[s]
            stack.append(b); stack.append(a)
        else:
            out.append(s)
    return bytes(out)

This version rescans the whole sequence each round, so it is quadratic in the worst case and only suitable for kilobytes. The published algorithm runs in linear time by keeping occurrence lists for every pair and a priority structure bucketed by frequency, at the cost of several machine words of memory per input symbol. That memory appetite is Re-Pair's main operational limit.

A traced example

Run it on abracadabra abracadabra (23 bytes). The pair ab appears four times; so do br and ra, and ties go to the pair seen first, which is what Counter.most_common returns, so ab becomes R1. Then R1 r becomes R2, R2 a ("abra") becomes R3, and the rules keep absorbing one character at a time because every remaining pair now appears exactly twice: R4 = R3 c, R5 = R4 a, R6 = R5 d, R7 = R6 R3. The final sequence is R7 ' ' R7: 3 symbols plus 7 two-symbol rules, 17 symbols in total for 23 characters.

Two edge cases matter. For aaaaaaa, the pair aa occurs three times without overlap, giving R1 = aa and the sequence R1 R1 R1 a; after that no pair repeats. Counting overlapping occurrences would claim six and pick wrong pairs. For abababab Re-Pair finds R1 = ab, R2 = R1 R1 and ends with R2 R2, the SLP shown earlier.

Sequitur: building the grammar online

Sequitur, by Nevill-Manning and Witten (1997), builds a grammar online, one symbol at a time, by maintaining two invariants. Digram uniqueness: no pair of adjacent symbols appears twice in the grammar; when a repeat appears, it is replaced by a rule. Rule utility: every rule is used at least twice; a rule used once is inlined. It runs in linear time and works on streams, and its rules can be longer than two symbols. Re-Pair sees the whole input before choosing, so in published comparisons it usually produces the smaller grammar; choose Sequitur when input arrives incrementally or you want a hierarchical view of structure, as in its original use for discovering phrases in text and music.

Random access without decompression

Because rules are created bottom-up, one pass computes the expansion length of every rule. To read position i, skip whole symbols of the final sequence by length, then descend: go left if i falls inside the left child's expansion, otherwise go right and subtract that length.

def lengths(rules):
    L = {}
    for s in sorted(rules):                 # children always have smaller ids
        a, b = rules[s]
        L[s] = L.get(a, 1) + L.get(b, 1)
    return L

def access(seq, rules, L, i):
    """Byte at position i of the text, without decompressing it."""
    for s in seq:
        n = L.get(s, 1)
        if i < n:
            break
        i -= n
    else:
        raise IndexError(i)
    while s in rules:
        a, b = rules[s]
        la = L.get(a, 1)
        s, i = (a, i) if i < la else (b, i - la)
    return s

Cost is one step per level of the derivation, so it depends on grammar height. Our trace has height 7 for 23 characters, and Re-Pair grammars of real inputs can be much taller than log n. Production systems store prefix sums over the final sequence for binary search, and either rebalance the grammar or use constructions with guaranteed O(log n) height. The same lengths support substring extraction (find the start, then expand only the needed nodes) and comparison of two substrings by fingerprints computed per rule.

Measured results

We checked the code on four hand strings, every position of each through access, and on 2,000 random binary strings for exact round-trips. Then two inputs that show where grammars help and where they do not:

The first row needs care. Symbols are not bytes: with 256 terminals plus about 1,000 rules, each symbol needs about 11 bits, so stored naively the grammar takes roughly 2.8 KB, more than twice what zlib and xz produce. Re-Pair found the repetition, but a competitive file format needs entropy coding of the rules, for example with arithmetic coding. The reason to choose a grammar here is the random access and compressed-domain operations, not the ratio. The second row is a failure mode: random data has no repeats worth a rule, and every rule costs more than it saves.

Storing the grammar compactly

A Re-Pair grammar has two parts to store: the rule table, where each rule is a pair of smaller symbol ids, and the final sequence. The naive layout writes every symbol in ceil(log2(256 + R)) bits for R rules, which is exactly what made the measured grammar lose to zlib. Three standard improvements close most of the gap.

• Entropy-code the final sequence. Symbol frequencies are skewed, so a canonical Huffman code or an arithmetic coder over the sequence beats fixed-width ids.
• Use growing id widths for rules. Rule k can only reference terminals and the k rules before it, so its two children need only ceil(log2(256 + k)) bits each; early rules are cheap, and nothing is lost, because the decoder knows k as it reads.
• Prune rules used once. After the final round, a rule referenced only once saves nothing; inline it unless you need it as an access shortcut. Inlining leaves rules longer than two symbols, so lengths and access must then loop over children instead of assuming pairs.

Keep the per-rule lengths out of the stored file when space matters, since one pass recomputes them at load time, but keep them in memory for access. For random access over a large final sequence, also store sampled prefix sums, for example every 64th symbol, so a lookup binary-searches the samples and then scans at most 63 symbols.

Operational guidance

Grammars earn their place when data is highly repetitive and you need to query it without unpacking it: versioned documents, source-code histories, collections of genomes from one species, or log streams dominated by a few templates. For one-shot archival of ordinary files, an LZ77 compressor is simpler and usually smaller. Measure on your own data before committing; compression of repetitive collections depends on how far apart the repeats are, and Re-Pair, unlike a windowed LZ77 coder, sees repeats at any distance. Compress in blocks of a size you can afford in memory, record per-block grammar height alongside ratio, and alert if height grows, since access latency follows height.

Failure modes

• Decompression bombs. Sixty-four doubling rules describe a string of 2^64 symbols. Compute expansion lengths first, as lengths does, and refuse anything over a limit before expanding.
• Malformed grammars. A rule that references itself or a later rule creates a cycle and an infinite expansion. When loading, require every rule to reference only smaller ids, and reject unknown symbols.
• Deep recursion. A tall grammar overflows a recursive expander. Use an explicit stack, as expand does.
• Memory blow-up. Linear-time Re-Pair uses several words per input symbol; for gigabytes, compress in blocks or use external-memory variants.
• Incompressible input. Detect it (few rules, long final sequence) and store the block raw.

Trade-offs

What to do next

1. Run the Re-Pair code on your own repetitive data (logs, configs, versions) and record sequence length, rule count and grammar height.
2. Add a loader that validates rule ids and caps expansion length before expanding.
3. Entropy-code the rules and sequence, then compare bytes against zstd and xz fairly.
4. Benchmark access(i) against decompress-then-index, and add prefix sums over the final sequence.
5. Replace the quadratic loop with pair occurrence lists and a frequency-bucket queue.
6. Implement Sequitur for a streaming source and compare grammar sizes.