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 条
  • [41] Fast Online Lempel-Ziv Factorization in Compressed Space
    Policriti, Alberto
    Prezza, Nicola
    STRING PROCESSING AND INFORMATION RETRIEVAL (SPIRE 2015), 2015, 9309 : 13 - 20
  • [42] Area reduction and improvements in speed and compression ratio for a Lempel-Ziv data compression circuit using a content addressable memory
    Satoh, A
    ELECTRONICS AND COMMUNICATIONS IN JAPAN PART II-ELECTRONICS, 1999, 82 (03): : 1 - 10
  • [43] Lempel-Ziv Factorization Using Less Time & Space
    Chen, Gang
    Puglisi, Simon J.
    Smyth, W. F.
    MATHEMATICS IN COMPUTER SCIENCE, 2008, 1 (04) : 605 - 623
  • [44] Lempel-Ziv Factorization Revisited
    Ohlebusch, Enno
    Gog, Simon
    COMBINATORIAL PATTERN MATCHING, 22ND ANNUAL SYMPOSIUM, CPM 2011, 2011, 6661 : 15 - 26
  • [45] On Lempel-Ziv complexity of sequences
    Doganaksoy, Ali
    Gologlu, Faruk
    SEQUENCES AND THEIR APPLICATIONS - SETA 2006, 2006, 4086 : 180 - 189
  • [46] Lempel-Ziv Computation In Compressed Space (LZ-CICS)
    Koeppl, Dominik
    Sadakane, Kunihiko
    2016 DATA COMPRESSION CONFERENCE (DCC), 2016, : 3 - 12
  • [47] Lempel-Ziv type high-speed data compression circuit using content addressable memory
    IBM Japan, Ltd, Yamato, Japan
    Electron Commun Jpn Part II Electron, 7 (60-67):
  • [48] Lempel-Ziv Factorization Powered by Space Efficient Suffix Trees
    Fischer, Johannes
    Tomohiro, I
    Koeppl, Dominik
    Sadakane, Kunihiko
    ALGORITHMICA, 2018, 80 (07) : 2048 - 2081
  • [49] A Low-Complexity and High-Throughput Hardware Design for Lempel-Ziv 4 Compression Algorithm
    Chen, Tao
    Song, Suwen
    Wang, Zhongfeng
    IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS, 2025,
  • [50] A Low-Complexity and High-Throughput Hardware Design for Lempel-Ziv 4 Compression Algorithm
    Chen, Tao
    Song, Suwen
    Wang, Zhongfeng
    IEEE Transactions on Circuits and Systems I: Regular Papers,
12345