DocumentCode
2252937
Title
Asymptotic behavior of the Lempel-Ziv parsing scheme and digital trees
Author
Jacquet, Philippe ; Szpankowski, W-ojciech
Author_Institution
Inst. Nat. de Recherche en Inf. et Autom., Le Chesnay, France
fYear
1995
fDate
17-22 Sep 1995
Firstpage
14
Abstract
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
Keywords
grammars; probability; speech coding; statistical analysis; tree searching; Lempel-Ziv parsing scheme; asymptotic behavior; digital search tree; digital trees; internal path length; limiting distribution; memoryless source; open problem; symbols generation; unequal probabilities; Computer science; Convergence; Differential equations; Entropy; Gaussian distribution; Partitioning algorithms;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Theory, 1995. Proceedings., 1995 IEEE International Symposium on
Conference_Location
Whistler, BC
Print_ISBN
0-7803-2453-6
Type
conf
DOI
10.1109/ISIT.1995.531116
Filename
531116
Link To Document