Asymptotic behavior of the Lempel-Ziv parsing scheme and digital trees
Philippe Jacquet, W. Szpankowski · 2002
For the memoryless source with unequal probabilities of symbols generation we derive the limiting distribution for the number of phrases in the Lempel-Ziv (1978) parsing scheme. This proves a long standing open problem. In order to establish it we had to solve another open problem, namely, that of deriving the limiting distribution of the internal path length in a digital search tree.