Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression

被引：0
|
作者：
Mayordomo, Elvira [1 ]
Moser, Philippe [2 ]
机构：
[1] Univ Zaragoza, Dept Informat & Ingn Sistemas, Maria de Luna 1, Zaragoza 50018, Spain
[2] Natl Univ Ireland Maynooth, Dept Comp Sci, Maynooth, Kildare, Ireland
来源：
SOFSEM 2009-THEORY AND PRACTICE OF COMPUTER SCIENCE, PROCEEDINGS | 2009年 / 5404卷
关键词：
compression algorithms; plogon; computational complexity; data stream algorithms; Lempel-Ziv algorithm; pushdown compression;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
This paper considers online compression algorithms that use at most polylogarithmic space (plogon). These algorithms correspond to compressors in the data stream model. We study the performance attained by these algorithms and show they are incomparable with both pushdown compressors and the Lempel-Ziv compression algorithm.
引用
收藏
页码：633 / +
页数：3
相关论文
共 50 条
  • [1] Polylog Space Compression, Pushdown Compression, and Lempel-Ziv Are Incomparable
    Mayordomo, Elvira
    Moser, Philippe
    Perifel, Sylvain
    THEORY OF COMPUTING SYSTEMS, 2011, 48 (04) : 731 - 766
  • [2] Polylog Space Compression, Pushdown Compression, and Lempel-Ziv Are Incomparable
    Elvira Mayordomo
    Philippe Moser
    Sylvain Perifel
    Theory of Computing Systems, 2011, 48 : 731 - 766
  • [3] Lempel-Ziv dimension for Lempel-Ziv compression
    Lopez-Valdes, Maria
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2006, PROCEEDINGS, 2006, 4162 : 693 - 703
  • [4] Generalized Lempel-Ziv compression for audio
    Kirovski, Darko
    Landau, Zeph
    IEEE TRANSACTIONS ON AUDIO SPEECH AND LANGUAGE PROCESSING, 2007, 15 (02): : 509 - 518
  • [5] Pushdown and Lempel-Ziv depth
    Jordon, Liam
    Moser, Philippe
    INFORMATION AND COMPUTATION, 2023, 292
  • [6] Generalized Lempel-Ziv compression for audio
    Kirovski, D
    Landau, Z
    2004 IEEE 6TH WORKSHOP ON MULTIMEDIA SIGNAL PROCESSING, 2004, : 127 - 130
  • [7] Lempel-Ziv compression of structured text
    Adiego, J
    Navarro, G
    de la Fuente, P
    DCC 2004: DATA COMPRESSION CONFERENCE, PROCEEDINGS, 2004, : 112 - 121
  • [8] Lempel-Ziv compression of highly structured documents
    Adiego, Joaquin
    Navarro, Gonzalo
    de la Fuente, Pablo
    JOURNAL OF THE AMERICAN SOCIETY FOR INFORMATION SCIENCE AND TECHNOLOGY, 2007, 58 (04): : 461 - 478
  • [9] ON THE BIT-COMPLEXITY OF LEMPEL-ZIV COMPRESSION
    Ferragina, Paolo
    Nitto, Igor
    Venturini, Rossano
    SIAM JOURNAL ON COMPUTING, 2013, 42 (04) : 1521 - 1541
  • [10] Lossy lempel-ziv algorithm for image compression
    Cmojevic, V
    Senk, V
    Trpovski, Z
    TELSIKS 2003: 6TH INTERNATIONAL CONFERENCE ON TELECOMMUNICATIONS IN MODERN SATELLITE, CABLE AND BROADCASTING SERVICE, VOLS 1 AND 2, PROCEEDINGS OF PAPERS, 2003, : 522 - 525
12345