Grammar-based code

Straight-line grammar (with start symbol ß) for the second sentence of the United States Declaration of Independence. Each blue character denotes a nonterminal symbol; they were obtained from a gzip-compression of the sentence.

Grammar-based codes or grammar-based compression are compression algorithms based on the idea of constructing a context-free grammar (CFG) for the string to be compressed. Examples include universal lossless data compression algorithms.[1] To compress a data sequence , a grammar-based code transforms into a context-free grammar . The problem of finding a smallest grammar for an input sequence (smallest grammar problem) is known to be NP-hard,[2] so many grammar-transform algorithms are proposed from theoretical and practical viewpoints. Generally, the produced grammar is further compressed by statistical encoders like arithmetic coding.

Examples and characteristics

The class of grammar-based codes is very broad. It includes block codes, the multilevel pattern matching (MPM) algorithm,[3] variations of the incremental parsing Lempel-Ziv code,[4] and many other new universal lossless compression algorithms. Grammar-based codes are universal in the sense that they can achieve asymptotically the entropy rate of any stationary, ergodic source with a finite alphabet.

Practical algorithms

The compression programs of the following are available from external links.

  • Sequitur[5] is a classical grammar compression algorithm that sequentially translates an input text into a CFG, and then the produced CFG is encoded by an arithmetic coder.
  • Re-Pair[6] is a greedy algorithm using the strategy of most-frequent-first substitution. The compressive performance is powerful, although the main memory space requirement is very large.
  • GLZA,[7] which constructs a grammar that may be reducible, i.e., contain repeats, where the entropy-coding cost of "spelling out" the repeats is less than the cost creating and entropy-coding a rule to capture them. (In general, the compression-optimal SLG is not irreducible, and the Smallest Grammar Problem is different from the actual SLG compression problem.)

See also

References

  1. ^ Kieffer, J. C.; Yang, E.-H. (2000), "Grammar-based codes: A new class of universal lossless source codes", IEEE Trans. Inf. Theory, 46 (3): 737–754, Bibcode:2000ITIT...46..737K, doi:10.1109/18.841160
  2. ^ Charikar, M.; Lehman, E.; Liu, D.; Panigrahy, R.; Prabharakan, M.; Sahai, A.; Shelat, A. (2005), "The Smallest Grammar Problem", IEEE Trans. Inf. Theory, 51 (7): 2554–2576, Bibcode:2005ITIT...51.2554C, doi:10.1109/tit.2005.850116, S2CID 6900082
  3. ^ Kieffer, J. C.; Yang, E.-H.; Nelson, G.; Cosman, P. (2000), "Universal lossless compression via multilevel pattern matching", IEEE Trans. Inf. Theory, 46 (4): 1227–1245, Bibcode:2000ITIT...46.1227K, doi:10.1109/18.850665, S2CID 8191526
  4. ^ Ziv, J.; Lempel, A. (1978), "Compression of individual sequences via variable rate coding", IEEE Trans. Inf. Theory, 24 (5): 530–536, Bibcode:1978ITIT...24..530Z, doi:10.1109/TIT.1978.1055934, hdl:10338.dmlcz/142945
  5. ^ Nevill-Manning, C. G.; Witten, I. H. (1997), "Identifying Hierarchical Structure in Sequences: A linear-time algorithm", Journal of Artificial Intelligence Research, 7 (4): 67–82, arXiv:cs/9709102, doi:10.1613/jair.374, hdl:10289/1186, S2CID 2957960
  6. ^ Larsson, N. J.; Moffat, A. (2000), "Offline Dictionary-Based Compression" (PDF), Proceedings of the IEEE, 88 (11): 1722–1732, Bibcode:2000IEEEP..88.1722L, doi:10.1109/5.892708
  7. ^ Conrad, Kennon J.; Wilson, Paul R. (2016). "Grammatical Ziv-Lempel Compression: Achieving PPM-Class Text Compression Ratios with LZ-Class Decompression Speed". 2016 Data Compression Conference (DCC). p. 586. doi:10.1109/DCC.2016.119. ISBN 978-1-5090-1853-6. S2CID 3116024.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.