iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/978-1-4939-2864-4_635
Grammar Compression | SpringerLink
Skip to main content
Springer Nature Link
Log in

Grammar Compression

  • Reference work entry
  • First Online:
Encyclopedia of Algorithms

Years and Authors of Summarized Original Work

  • 2000; Kieffer, Yang

  • 2003; Rytter

  • 2004; Sakamoto et al.

  • 2005; Charikar et al.

Grammar Compression, Fig. 1
figure 720 figure 720

(Left) an SLP G that represents string aabaaaaaba, where the variable X7 is the start symbol. (Center) derivation tree of G. (Right) an ordered DAG corresponding to G, where the solid and dashed edges respectively correspond to the first and second child of each node

Full size image

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 1,099.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Recommended Reading

  1. Apostolico A, Lonardi S (2000) Off-line compression by greedy textual substitution. Proc IEEE 88(11):1733–1744

    Article  Google Scholar 

  2. Bille P, Landau GM, Raman R, Sadakane K, Satti SR, Weimann O (2011) Random access to grammar-compressed strings. In: Proceedings of the SODA’11, San Francisco, pp 373–389

    Google Scholar 

  3. Charikar M, Lehman E, Liu D, Panigrahy R, Prabhakaran M, Sahai A, Shelat A (2005) The smallest grammar problem. IEEE Trans. Inf. Theory 51(7):2554–2576

    Article  MathSciNet  MATH  Google Scholar 

  4. Ga̧sieniec L, Kolpakov R, Potapov I, Sant P (2005) Real-time traversal in grammar-based compressed files. In: Proceedings of the DCC’05, Snowbird, p 458

    Google Scholar 

  5. Jeż A (2013) Approximation of grammar-based compression via recompression. In: Proceedings of the CPM’13, Bad Herrenalb, pp 165–176

    Google Scholar 

  6. Jeż A (2014) A really simple approximation of smallest grammar. In: Proceedings of the CPM’14, Moscow, pp 182–191

    Google Scholar 

  7. Karpinski M, Rytter W, Shinohara A (1997) An efficient pattern-matching algorithm for strings with short descriptions. Nord J Comput 4:172–186

    MathSciNet  MATH  Google Scholar 

  8. Kieffer JC, Yang EH (2000) Grammar-based codes: a new class of universal lossless source codes. IEEE Trans Inf Theory 46(3):737–754

    Article  MathSciNet  MATH  Google Scholar 

  9. Kieffer J, Yang E, Nelson G, Cosman P (2000) Universal lossless compression via multilevel pattern matching. IEEE Trans Inf Theory 46(4):1227–1245

    Article  MathSciNet  MATH  Google Scholar 

  10. Lanctôt JK, Li M, Yang E (2000) Estimating DNA sequence entropy. In: Proceedings of the SODA’00, San Francisco, pp 409–418

    Google Scholar 

  11. Larsson NJ, Moffat A (2000) Off-line dictionary-based compression. Proc IEEE 88(11):1722–1732

    Article  Google Scholar 

  12. Maruyama S, Sakamoto H, Takeda M (2012) An online algorithm for lightweight grammar-based compression. Algorithms 5(2):214–235

    Article  MathSciNet  Google Scholar 

  13. Maruyama S, Tabei Y, Sakamoto H, Sadakane K (2013) Fully-online grammar compression. In: Proceedings of the SPIRE’13, Jerusalem, pp 218–229

    Google Scholar 

  14. Nakamura R, Inenaga S, Bannai H, Funamoto T, Takeda M, Shinohara A (2009) Linear-time text compression by longest-first substitution. Algorithms 2(4):1429–1448

    Article  MathSciNet  Google Scholar 

  15. Nevill-Manning CG, Witten IH (1997) Identifying hierarchical structure in sequences: a linear-time algorithm. J Artif Intell Res 7(1):67–82

    MATH  Google Scholar 

  16. Rytter W (2003) Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor Comput Sci 302(1–3):211–222

    Article  MathSciNet  MATH  Google Scholar 

  17. Sahinalp SC, Vishkin U (1995) Data compression using locally consistent parsing. Technical report, UMIACS Technical Report

    Google Scholar 

  18. Sakamoto H (2005) A fully linear-time approximation algorithm for grammar-based compression. J Discret Algorithms 3(2–4):416–430

    Article  MathSciNet  MATH  Google Scholar 

  19. Sakamoto H, Kida T, Shimozono S (2004) A space-saving linear-time algorithm for grammar-based compression. In: Proceedings of the SPIRE’04, Padova, pp 218–229

    Google Scholar 

  20. Sakamoto H, Maruyama S, Kida T, Shimozono S (2009) A space-saving approximation algorithm for grammar-based compression. IEICE Trans 92-D(2):158–165

    Google Scholar 

  21. Storer JA (1977) NP-completeness results concerning data compression. Technical report 234, Department of Electrical Engineering and Computer Science, Princeton University

    Google Scholar 

  22. Verbin E, Yu W (2013) Data structure lower bounds on random access to grammar-compressed strings. In: Proceedings of the CPM’13, Bad Herrenalb, pp 247–258

    Google Scholar 

  23. Yao ACC (1976) On the evaluation of powers. SIAM J Comput 5(1):100–1–03

    Google Scholar 

  24. Ziv J, Lempel A (1978) Compression of individual sequences via variable-length coding. IEEE Trans Inf Theory 24(5):530–536

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Informatics, Kyushu University, Fukuoka, Japan

    Hideo Bannai

Authors
  1. Hideo Bannai
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hideo Bannai .

Editor information

Editors and Affiliations

  1. Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL, USA

    Ming-Yang Kao

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer Science+Business Media New York

About this entry

Cite this entry

Bannai, H. (2016). Grammar Compression. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_635

Download citation

Publish with us

Policies and ethics

Search

Navigation