DocumentCode
322417
Title
A universal upper bound on the performance of the Lempel-Ziv algorithm on maliciously-constructed data
Author
Lathrop, James I. ; Strauss, Martin
Author_Institution
Dept. of Comput. Sci., Iowa State Univ., Ames, IA, USA
fYear
1997
fDate
11-13 Jun 1997
Firstpage
123
Lastpage
135
Abstract
We consider the performance of the Lempel-Ziv (1978) algorithm on finite strings and infinite sequences having unbalanced statistics. We show that such strings and sequences are compressed by the Lempel-Ziv algorithm. We show that the converse does not hold, i.e., that there are sequences with perfectly balanced asymptotic statistics that the Lempel-Ziv algorithm compresses optimally
Keywords
data compression; sequences; statistical analysis; Lempel-Ziv algorithm performance; finite strings; infinite sequences; maliciously-constructed data; optimal compression; perfectly balanced asymptotic statistics; unbalanced statistics; universal upper bound; Automata; Computer science; Entropy; Frequency; Laboratories; Probability; Statistics; Upper bound;
fLanguage
English
Publisher
ieee
Conference_Titel
Compression and Complexity of Sequences 1997. Proceedings
Conference_Location
Salerno
Print_ISBN
0-8186-8132-2
Type
conf
DOI
10.1109/SEQUEN.1997.666909
Filename
666909
Link To Document