Average profile of the Lempel-Ziv scheme for a Markovian source
Jing Tang, W. Szpanskowski · 2002
We consider the Lempel-Ziv (1978) parsing scheme (LZ'78) which parses a sequence into phrases such that the next phrase is the shortest phrase not seen in the past. Two models called further digital tree model and Lempel-Ziv model are of interest. The former asks for the length of the Lempel-Ziv string composed of m phrases. The latter assumes that the string is of fixed length, say n, and investigates the number of phrases generated by the scheme. We are interested in the average profile which is defined as the average number of phrases of a given size. The average profile is related to the length of a randomly selected phrase which we denote either as D/sub m/, for the digital tree model or as D/sub n//sup LZ/ for the Lempel-Ziv model. Thus, we concentrate on studying D/sub m/, and D/sub n//sup LZ/. More precisely, we investigate the fine structure (i.e., second-order properties) of these parameters for a Markovian source over a finite alphabet /spl Sigma/ of size V.