H(P):= 

p_{s} lg p_{s}, 
h= 

 


P(x_{1}^{n})lg P(x_{1}^{n}). 
h= 

p_{i} 

p_{i,j}lg p_{i,j}, 
R_{n}(C,P;x_{1}^{n}):=L  (  C(x_{1}^{n})  )  +lg P(x_{1}^{n}), 

_{n}(C,P)=E  [  R_{n}(C,P;x_{1}^{n})  ]  , R_{n}^{*}(C,P)= 

[  R_{n}(C,P;x_{1}^{n})  ]  . (1) 
Louchard and Szpankowski (1997), Savari (1997), Wyner (1998), and JacquetSzpankowski (1995) proved that the LempelZiv algorithms under either a memoryless or a Markov model have rates that are Q(n/log n) for LZ'78^{3} and Q(nloglog n/log n) for LZ'77. The proofs provide detailed asymptotic information on the redundancy. The results again involve subtle fluctuations. The analysis is close to that of digital tries, with Mellin transforms playing a prominent rôle.
Figure 1: Huffman code redundancy for a memoryless source with control parameter a=lg(1/p1): (a) irrational case (p=1/p); (b) rational case (p=1/9).
lg 


P(x_{1}^{n}) £ R_{n}^{*}( S) £ 1+lg 


P(x_{1}^{n}). (3) 
A_{n} := 


P(x_{1}^{n}) = 


æ ç ç è 

ö ÷ ÷ ø 

æ ç ç è 

ö ÷ ÷ ø 

. 
A_{n}= 

[z^{n}] 

where T(z)=ze^{T(z)} 
A_{n}~ 


~( 

)^{1/2} and lg A_{n}= 

lg n+lg( 

)^{1/2}+o(1). 
r_{n}= 



æ ç ç è 

ö ÷ ÷ ø 

æ ç ç è 

ö ÷ ÷ ø 

... 
æ ç ç è 

ö ÷ ÷ ø 

. 
S(z,u):= 

b(z^{i}u) where b(z)= 

. 
lg r_{n} = 

( 
æ ç ç è 

1 
ö ÷ ÷ ø 
n)^{1/2}  

lg n + 

lg log n +O(1), 
http://www.cs.purdue.edu/people/spa
.This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.