A Worst-Case Analysis of the LZ2 Compression Algorithm

Authors: De Agostino S.; Silvestri R.

Source: Information and Computation, Volume 139, Number 2, December 1997 , pp. 258-268(11)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

Sheinwald, Lempel, and Ziv (1995, Inform. and Comput. 116,128-133) proved that the power of off-line coding is notuseful if we want on-line decodable files, as far as asymptoticalresults are concerned. In this paper, we are concerned withthe finite case and consider the notion of on-line decodableoptimal parsing based on the parsing defined by the Ziv-Lempel(LZ2) compression algorithm. De Agostino and Storer (1996, Inform.Process. Lett. 59, 169-174) proved the NP-completenessof computing the optimal parsing and that a sublogarithmic factorapproximation algorithm cannot be realized on-line. We showthat the Ziv-Lempel algorithm and two widely used practicalimplementations produce an O(n1/4) approximation of the optimalparsing, where n is the length of the string. By working withde Bruijn sequences, we show also infinite families of binarystrings on which the approximation factor is Theta(n1/4).Copyright 1997 Academic Press

Language: English

Document Type: Research article

Affiliations: Computer Science Department, University "La Sapienza,", Via Salaria 113, Rome, 00198, Italy

Publication date: 1997-12-01