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 条
  • [31] Relative Lempel-Ziv Compression of Genomes for Large-Scale Storage and Retrieval
    Kuruppu, Shanika
    Puglisi, Simon J.
    Zobel, Justin
    STRING PROCESSING AND INFORMATION RETRIEVAL, 2010, 6393 : 201 - +
  • [32] Design of hardware accelerator for Lempel-Ziv 4 (LZ4) compression
    Lee, Sang Muk
    Jang, Ji Hoon
    Oh, Jung Hwan
    Kim, Ji Kwang
    Lee, Seung Eun
    IEICE ELECTRONICS EXPRESS, 2017, 14 (11):
  • [33] Lossy Lempel-Ziv algorithm for large alphabet sources and applications to image compression
    Finamore, WA
    Leister, MD
    INTERNATIONAL CONFERENCE ON IMAGE PROCESSING, PROCEEDINGS - VOL I, 1996, : 225 - 228
  • [34] Comparison of Huffman Algorithm and Lempel-Ziv Algorithm for Audio, Image and Text Compression
    Bedruz, Rhen Anjerome
    Quiros, Ana Riza F.
    2015 INTERNATIONAL CONFERENCE ON HUMANOID, NANOTECHNOLOGY, INFORMATION TECHNOLOGY,COMMUNICATION AND CONTROL, ENVIRONMENT AND MANAGEMENT (HNICEM), 2015, : 508 - +
  • [35] NEW ASYMPTOTIC BOUNDS AND IMPROVEMENTS ON THE LEMPEL-ZIV DATA-COMPRESSION ALGORITHM
    BENDER, PE
    WOLF, JK
    IEEE TRANSACTIONS ON INFORMATION THEORY, 1991, 37 (03) : 721 - 729
  • [36] Lempel-Ziv Networks
    Saul, Rebecca
    Alam, Mohammad Mahmudul
    Hurwitz, John
    Raff, Edward
    Oates, Tim
    Holt, James
    PROCEEDINGS ON I CAN'T BELIEVE IT'S NOT BETTER! - UNDERSTANDING DEEP LEARNING THROUGH EMPIRICAL FALSIFICATION, VOL 187, 2022, 187 : 1 - 11
  • [37] A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support
    Dutta, Akashnil
    Levi, Reut
    Ron, Dana
    Rubinfeld, Ronitt
    2013 DATA COMPRESSION CONFERENCE (DCC), 2013, : 113 - 122
  • [38] A dynamic and secure Arabic Text compression technique using bitwise Lempel-Ziv algorithm
    Musa A.
    Al-Dmour A.
    Fraij F.
    Al-Khaleel O.
    Irshid M.
    Information Technology Journal, 2010, 9 (04) : 673 - 679
  • [39] Simple universal lossy data compression schemes derived from the Lempel-Ziv algorithm
    Yang, EH
    Kieffer, JC
    IEEE TRANSACTIONS ON INFORMATION THEORY, 1996, 42 (01) : 239 - 245
  • [40] FIXED DATA-BASE VERSION OF THE LEMPEL-ZIV DATA-COMPRESSION ALGORITHM
    WYNER, AD
    ZIV, J
    IEEE TRANSACTIONS ON INFORMATION THEORY, 1991, 37 (03) : 878 - 890
12345