Pushdown compression

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.
Type de document :
Communication dans un congrès
Susanne Albers, Pascal Weil. STACS 2008, Feb 2008, Bordeaux, France. IBFI Schloss Dagstuhl, pp.39-48, 2008
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

Contributeur : Pascal Weil <>
Soumis le : mercredi 30 janvier 2008 - 13:03:24
Dernière modification le : mardi 24 avril 2018 - 13:52:24
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 20:02:02


Fichiers produits par l'(les) auteur(s)


  • HAL Id : ensl-00175903, version 2



Pilar Albert, Elvira Mayordomo, Philippe Moser, Sylvain Perifel. Pushdown compression. Susanne Albers, Pascal Weil. STACS 2008, Feb 2008, Bordeaux, France. IBFI Schloss Dagstuhl, pp.39-48, 2008. 〈ensl-00175903v2〉



Consultations de la notice


Téléchargements de fichiers