Grammar compression
Grammar compression represents an input string by a restricted grammar whose start sequence expands to exactly that string.
Representation: Nonterminal rules name reusable fragments, including fragments built from other rules. For the acyclic teaching grammar, each rule refers only to byte terminals or earlier rules, so expansion is deterministic and terminates. [2] [4]
Accounting: A grammar-size measure counts symbols on rule right-hand sides, not encoded bytes. With r binary rules and a root of c symbols, this model counts 2r+c symbols; its 16-bit symbol encoding occupies 12+4r+2c bytes. It uses the fixed byte alphabet and no separate terminal productions. State conventions before comparing grammar sizes. [2] [4]
Construction: Bille and colleagues' space bounds count machine words beyond a rewritable n-word input; generated rules are streamed out rather than retained in the measured working memory. These bounds are neither total process bytes nor compressed-file sizes. [3]
Example: Repeating ab 1024 times gives 2048 input bytes, 10 binary rules and 2 root symbols: 56 bytes in the teaching format. This is one constructed repetitive input, not an expected compression ratio for real data. [4]
Relations
Limitations
- A small grammar does not by itself specify a file format, integrity protection, random-access index or minimum encoded size. [4, 1]
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
- The model measures logical representation lengths with explicit headers; filesystem allocation, replication and runtime object overhead are excluded.
- No raw experimental corpora or third-party paper figures are redistributed.