Asymptotic behavior of the Lempel-Ziv parsing scheme and digitaltrees

摘要

For the memoryless source with unequal probabilities of symbolsgeneration we derive the limiting distribution for the number of phrasesin the Lempel-Ziv (1978) parsing scheme. This proves a long standingopen problem. In order to establish it we had to solve another openproblem, namely, that of deriving the limiting distribution of theinternal path length in a digital search tree