Data Compression and Digital Trees

Motivated by the data compression scheme due to Ziv and Lempel, we discuss several problems on digital search trees and suffix trees. First of all, we consider a digital search tree built over $n$ independent strings, and for the symmetric alphabet we compute the variance of the external path length. We believe this can be used to estimate the variance of the number of phrases in the Ziv-Lempel parsing algorithm. We also discuss another Ziv-Lempel parsing algorithm that leads to suffix trees. Finally, we present some open problems in this area. \noindent Part of this work was done with P. Kirschenhofer and H. Prodinger, and part with P. Jacquet.