Data Compression/grammar-based compression

grammar-based compression ... give more details on grammar-based compression ... Grammar-based compression was proposed in 2000.En-hui Yang and John C. Kieffer. "Efficient Universal Lossless Data Compression Algorithms Based on a Greedy Sequential Grammar Transform—Part One: Without Context Models". 2000. Several data compression methods can be viewed as grammar-based compression: The Sequitur data compression algorithm uses a context-free grammar to represent a string such as a data file. It is relatively fast (linear-time encoding and linear-time decoding).Richard Ladner. "Sequitur" p. 56. 2007. Longest Match Most frequent digram The Sequential data compression algorithm is an improvement on Sequitur.Eric Lehman and Abhi Shelat. "Approximation Algorithms for Grammar-Based Compression". "Approximation Algorithms for Grammar-Based Compression". 2002. Although it pre-dates grammar-based compression, LZ78 and LZW (but not LZ77) can be interpreted as a kind of grammar. It has been shown that "a structured grammar" gives better compression than "an irreducible grammar".John Kieffer and En-hui Yang. "Structured grammar-based codes for universal lossless data compression". 2002. When the output of the grammar transform is compressed with a zero-order entropy coder (such as a zero-order arithmetic coder), grammar compression outperforms the Unix Compress and Gzip algorithms. The Re-Pair algorithm is a grammar based compression algorithm. Its decoder operates as follows:Matej Mežik. "Compression Using Context Free Grammars". 2011. FIXME: fill in details. Further reading grammar-based code Re-Store is a phrase browsing system based on the Re-Pair compression algorithm. Wan R. Re-Store Software http://www.cbrc.jp/~rwan/en/restore.html https://web.archive.org/web/20150721202007/http://cbrc3.cbrc.jp:80/~rwan/en/restore.html 2015-07-21