A WORST-CASE ANALYSIS OF THE LZ2 COMPRESSION ALGORITHM

Sheinwald, Lempel, and Ziv (1995, Inform, and Comput. 116, 128-133) pr oved that the power of off-line coding is not useful if we want on-lin e decodable files, as far as asymptotical results are concerned. In th is paper, we are concerned with the finite case and consider the notio n of on-line decodable optimal parsing based on the parsing defined by the Ziv-Lempel (LZ2) compression algorithm. De Agostino and Storer (1 996, Inform. Process. Lett. 59, 169-174) proved the NP-completeness of computing the optimal parsing and that a sublogarithmic factor approx imation algorithm cannot be realized on-line. We show that the Ziv-Lem pel algorithm and two widely used practical implementations produce an O(n(1 4)) approximation of the optimal parsing, where n is the length of the string. By working with de Bruijn sequences, we show also infi nite families of binary strings on which the approximation factor is O (n(1 4)). (C) 1997 Academic Press.