[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Polylog Space Compression, Pushdown Compression, and Lempel-Ziv Are Incomparable

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation (Hariharan, S., & Shankar, P. in: Proceedings of the 2006 IEEE data compression conference, p. 453, 2006; League, C., & Eng, K. in: Proceedings of the 2007 IEEE data compression conference, pp. 272–282, 2007), and in particular calls for a formulation of information-lossless stack or pushdown compressors that allows a formal analysis of their performance and a more ambitious use of the stack in XML compression, where so far it is mainly connected to parsing mechanisms. In this paper we introduce the model of pushdown compressor, based on pushdown transducers that compute a single injective function while keeping the widest generality regarding stack computation.

We also consider online compression algorithms that use at most polylogarithmic space (plogon). These algorithms correspond to compressors in the data stream model.

We compare the performance of these two families of compressors with each other and with the general purpose Lempel-Ziv algorithm. This comparison is made without any a priori assumption on the data’s source and considering the asymptotic compression ratio for infinite sequences. We prove that in all cases they are incomparable.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.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

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Albert, P., Mayordomo, E., Moser, P.: Bounded pushdown dimension vs Lempel Ziv information density. Tech. Rep. TR07-051, ECCC: Electronic Colloquium on Computational Complexity (2007)

  2. Albert, P., Mayordomo, E., Moser, P., Perifel, S.: Pushdown compression. In: Proceedings of the 25th Symposium on Theoretical Aspects of Computer Science (STACS 2008), pp. 39–48 (2008)

  3. Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. 58, 137–147 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  4. Alur, R., Madhusudan, P.: Adding nesting structure to words. In: Proceedings of the Tenth International Conference on Developments in Language Theory. Lecture Notes in Computer Science, vol. 4036. Springer, Berlin (2006)

    Google Scholar 

  5. Autebert, J., Berstel, J., Boasson, L.: Context-free languages and pushdown automata. In: Rozenberg, G., Salomaa, A. (eds.). Handbook of Formal Languages, vol. 1, pp. 111–174. Springer, Berlin (1997)

    Google Scholar 

  6. Champernowne, D.G.: Construction of decimals normal in the scale of ten. J. Lond. Math. Soc. 2(8), 254–260 (1933)

    Article  Google Scholar 

  7. Copeland, A., Erdös, P.: Note on normal numbers. Bull. Am. Math. Soc. 52, 857–860 (1946)

    Article  MATH  Google Scholar 

  8. Dai, J.J., Lathrop, J.I., Lutz, J.H., Mayordomo, E.: Finite-state dimension. Theor. Comput. Sci. 310, 1–33 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  9. Ginsburg, S., Rose, G.F.: Preservation of languages by transducers. Inf. Control 9(2), 153–176 (1966)

    Article  MathSciNet  MATH  Google Scholar 

  10. Ginsburg, S., Rose, G.F.: A note on preservation of languages by transducers. Inf. Control 12(5/6), 549–552 (1968)

    Article  MathSciNet  MATH  Google Scholar 

  11. Hariharan, S., Shankar, P.: Evaluating the role of context in syntax directed compression of xml documents. In: Proceedings of the 2006 IEEE Data Compression Conference (DCC 2006), p. 453 (2006)

  12. Hartmanis, J., Immerman, N., Mahaney, S.: One-way log-tape reductions. In: Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS’78), pp. 65–72. IEEE Computer Society, Los Alamitos (1978)

    Chapter  Google Scholar 

  13. Hitchcock, J.M.: Effective fractal dimension: Foundations and applications. Ph.D. thesis. Iowa State University (2003)

  14. Indyk, P., Woodruff, D.: Optimal approximations of the frequency moments of data streams. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pp. 202–208 (2005)

  15. Kuma, V., Madhusudan, P., Viswanathan, M.: Visibly pushdown automata for streaming xml. In: International World Wide Web Conference WWW 2007, pp. 1053–1062 (2007)

  16. Lathrop, J.I., Strauss, M.J.: A universal upper bound on the performance of the Lempel-Ziv algorithm on maliciously-constructed data. In: Compression and Complexity of Sequences ’97, pp. 123–135 (1998)

  17. League, C., Eng, K.: Type-based compression of xml data. In: Proceedings of the 2007 IEEE Data Compression Conference (DCC 2007), pp. 272–282 (2007)

  18. Lempel, A., Ziv, J.: Compression of individual sequences via variable rate coding. In: Transaction on Information Theory, pp. 530–536 (1978)

  19. López-Valdés, M., Mayordomo, E.: Dimension is compression. In: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, pp. 676–685 (2005)

  20. Mayordomo, E.: Effective fractal dimension in algorithmic information theory. In: New Computational Paradigms: Changing Conceptions of What is Computable, pp. 259–285 (2008)

  21. Mayordomo, E., Moser, P.: polylog space compression is incomparable with Lempel-Ziv and pushdown compression. In: Proceedings of the 35th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM09), pp. 633–644 (2009)

  22. Sculley, D., Brodley, C.E.: Compression and machine learning: A new perspective on feature space vectors. In: Proceedings of the Data Compression Conference (DCC-2006), pp. 332–341 (2006)

Download references

Author information

Authors and Affiliations

  1. Departamento de Informática e Ingeniería de Sistemas, Instituto de Investigación en Ingeniería de Aragón (I3A), Universidad de Zaragoza, María de Luna 1, 50018, Zaragoza, Spain

    Elvira Mayordomo

  2. Department of Computer Science, National University of Ireland Maynooth, Maynooth, Co. Kildare, Ireland

    Philippe Moser

  3. LIAFA, (Université Paris Diderot – Paris 7, CNRS), Paris, France

    Sylvain Perifel

Authors
  1. Elvira Mayordomo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Philippe Moser
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sylvain Perifel
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Elvira Mayordomo.

Additional information

E. Mayordomo’s and P. Moser’s research supported in part by Spanish Government MEC and the European Regional Development Fund (ERDF) under Projects TIN2005-08832-C03-02 and TIN2008-06582-C03-02.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mayordomo, E., Moser, P. & Perifel, S. Polylog Space Compression, Pushdown Compression, and Lempel-Ziv Are Incomparable. Theory Comput Syst 48, 731–766 (2011). https://doi.org/10.1007/s00224-010-9267-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-010-9267-6

Keywords

Search

Navigation