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 条

[21] A novel VLSI architecture for Lempel-Ziv based data compression
Lai, YK
Chen, KC
ISCAS 2000: IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS - PROCEEDINGS, VOL V: EMERGING TECHNOLOGIES FOR THE 21ST CENTURY, 2000, : 617 - 620
[22] Lempel-Ziv and Multiscale Lempel-Ziv Complexity in Depression
Kalev, K.
Bachmann, M.
Orgo, L.
Lass, J.
Hinrikus, H.
2015 37TH ANNUAL INTERNATIONAL CONFERENCE OF THE IEEE ENGINEERING IN MEDICINE AND BIOLOGY SOCIETY (EMBC), 2015, : 4158 - 4161
[23] A PostScript printer controller embedded with Lempel-Ziv data compression function
Satoh, A
Ueda, M
Satoh, T
ELECTRONICS AND COMMUNICATIONS IN JAPAN PART II-ELECTRONICS, 1999, 82 (08): : 17 - 26
[24] Application of Lempel-Ziv factorization to the approximation of grammar-based compression
Rytter, W
COMBINATORIAL PATTERN MATCHING, 2002, 2373 : 20 - 31
[25] Efficient VLSI for Lempel-Ziv compression in wireless data communication networks
Jung, BJ
Burleson, WP
IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, 1998, 6 (03) : 475 - 483
[26] Error resilient Lempel-Ziv data compression scheme with perfect hashing
Chang, Chinchen
Tseng, Hsienwen
INTERNATIONAL JOURNAL OF INNOVATIVE COMPUTING INFORMATION AND CONTROL, 2008, 4 (03): : 761 - 770
[27] A statistical Lempel-Ziv compression algorithm for personal digital assistant (PDA)
Kwong, S
Ho, YF
IEEE TRANSACTIONS ON CONSUMER ELECTRONICS, 2001, 47 (01) : 154 - 162
[28] Application of Lempel-Ziv factorization to the approximation of grammar-based compression
Rytter, W
THEORETICAL COMPUTER SCIENCE, 2003, 302 (1-3) : 211 - 222
[29] On Lempel-Ziv Decompression in Small Space
Puglisi, Simon J.
Rossi, Massimiliano
2019 DATA COMPRESSION CONFERENCE (DCC), 2019, : 221 - 230
[30] Huffman and Lempel-Ziv based Data Compression Algorithms for Wireless Sensor Networks
Renugadevi, S.
Darisini, P. S. Nithya
2013 INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION, INFORMATICS AND MEDICAL ENGINEERING (PRIME), 2013,

← 1 2 3 4 5 →