ess of the sequence length. Since the number of codeword entries increases indefinitely, the process of updating the dictionary should be periodically reinitiated. A new dictionary can be reconstructed from scratch, or cleaned up from the earlier entries to make up new space. 10.4 Lempel-Ziv coding Given the maximum codeword size L2, the LZ algorithm can identify as many as 2L2-1 individual phrases, for instance 2 15 = 32 768 phrases with L2 = 16. Such a number is more than sufficient to cover all possible patterns in a redundant source message and, therefore, ensure effective code compression. This remains true in the case where the source characteristics evolve over time. If the memory size is assumed to be sufficiently large to fit a virtually unlimited number of entries, a key question is whether or not the coded sequence can ever be shorter than the original message. To answer this question, we need to know the number of possible phrases, c(n), and the LZ codeword size, L2, given a message length of n bits. The Lempel and Ziv analysis of distinct parsing, which provides the answer, is detailed in Appendix I, and we shall use the result here. Given a message of n bits, the operation of distinct parsing yields c(n) phrases to which c(n) unique codewords are associated. The number of pointer-address bits required to define such a parsing is log c(n), which gives L2(n) = log ((n) + 1 for the codeword size. 14 Therefore, the coded version of the message has a full sequence length of: (10.4) The code compression (or expansion) is given by the ratio: (10.5) The issue now is to determine the upper bound of Nn in the limit of infinitely long messages (n 00). In Appendix I, it is shown that the number of distinct-parsing phrases c(n) is bounded according to: (10.6) where En vanishes as n 00. We, thus, observe that the growth of the number of phrases with message size is sublinear, with an absolute upper bound of n/ logn. Another useful information is that the codeword size is bounded according to (10.7) The codeword l