A Worst-Case Analysis of the LZ2 Compression Algorithm

Sheinwald, Lempel, and Ziv (1995, Inform. and Comput. 116, 128–133) proved that the power of off-line coding is not useful if we want on-line decodable files, as far as asymptotical results are concerned. In this paper, we are concerned with the finite case and consider the notion of on-line decodable optimal 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-completeness of computing the optimal parsing and that a sublogarithmic factor approximation algorithm cannot be realized on-line. We show that the Ziv–Lempel algorithm and two widely used practical implementations produce an O(n 1/4) approximation of the optimal parsing, wherenis the length of the string. By working with de Bruijn sequences, we show also infinite families of binary strings on which the approximation factor isΘ(n 1/4).

Authors

• Sergio De Agostino
• Riccardo Silvestri

Keywords

No keywords are indexed for this paper.