On Generalized Digital Search Trees With Applications To A Generalized Lempel-Ziv Algorithm

The goal of this research is twofold: (i) to analyze generalized digital search trees, and (ii) to derive the average profile (i.e., phrase length) of a generalization of the well known parsing algorithm due to Lempel and Ziv. In the generalized Lempel-Ziv parsing scheme, one partitions a sequence of symbols from a finite alphabet into phrases such that the new phrase is the longest substring seen in the past by at most b \Gamma 1 phrases. The case b = 1 corresponds to the original Lempel-Ziv scheme. As expected, such a scheme can be analyzed by considering a generalized digital search tree in which every node is capable of storing up to b strings. Such a digital tree is known as b-digital search tree. In this paper, we concentrate on investigating the depth of a randomly selected node in such a tree. We apply analytical techniques of analysis of algorithms to establish the mean, the variance and the limiting distribution of the depth. Based on these results, we infer the probabilistic..