License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1332
URN: urn:nbn:de:0030-drops-13327
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1332/
Go to the corresponding LIPIcs Volume Portal

Albert, Pilar ; Mayordomo, Elvira ; Moser, Philip ; Perifel, Sylvain

Pushdown Compression

pdf-format:
22011.AlbertPilar.Paper.1332.pdf (0.2 MB)

Abstract

The pressing need for efficient compression schemes for XML
documents has recently been focused on stack computation (Hariharan
and Shankar 2006, League and Eng 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.

The celebrated Lempel-Ziv algorithm LZ78 was introduced as a general
purpose compression algorithm that outperforms finite-state
compressors on all sequences. We compare the performance of the
Lempel-Ziv algorithm with that of the pushdown compressors, or
compression algorithms that can be implemented with a pushdown
transducer. 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 Lempel-Ziv is
incomparable with pushdown compressors.

BibTeX - Entry

@InProceedings{albert_et_al:LIPIcs:2008:1332,
  author =	{Pilar Albert and Elvira Mayordomo and Philip Moser and Sylvain Perifel},
  title =	{{Pushdown Compression}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{39--48},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1332},
  URN =		{urn:nbn:de:0030-drops-13327},
  doi =		{10.4230/LIPIcs.STACS.2008.1332},
  annote =	{Keywords: Finite-state compression, Lempel-Ziv algorithm, pumping-lemma, pushdown compression, XML document}
}

Keywords: Finite-state compression, Lempel-Ziv algorithm, pumping-lemma, pushdown compression, XML document
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI