ength, thus, increases somewhat slower than the logarithm (base 2) of the message length N. Both properties concerning the growth of c(n) and L2(n) are advantageous for memory size considerations. Replacing next the property in Eq. (10.6) in Eq. (10.5) yields for the compression ratio: (10.8) Taking the infinite limit in Eq. (10.8) leads to the conclusion R(n which proves that compression is possible (the compression rate being defined as r = 1 - R(n)). Yet, we don't know exactly how much compression can be achieved. 14 In the example of Fig. 10.5, for instance, we have n = 71 bits, c(n) = 16 and L2 = 5. Integer, arithmetic, and adaptive coding A more general and finer-grain analysis, which requires a very involved demonstration, provided in. 15 Here, I shall just provide the conclusion, which takes the form im sup R(n) < H (X), (10.9) where H(X) is the entropy of the binary source X = {0,1} from which the message string is generated. 16 This property shows that the LZ code is asymptotically optimal. In Section 3.2, indeed, we have seen that a code is optimal if, given the source entropy H(X), the mean codeword length L satisfies: H(X)<L < H(X) + 1. (10.10) This inequality also applies to any optimal block code with fixed length Ls(n), as applied to an n-bit message from extended source X(n): (10.11) Dividing Eq. (10.11) by n and taking the limit oo yields: (10.12) or, equivalently, (10.13) The last equality in Eq. (10.13) is made under the assumption that, in the infinite limit, the extended source becomes memoryless. This concept means that the source events become asymptotically independent as their number increases, which justifies the limit. Returning to the earlier issue, we can, thus, conclude from the result in Eq. (10.9) that LZ coding is asymptotically optimal, with an average codeword length (bit/source- symbol) ultimately no greater than the source entropy. The original LZ77 algorithm (also called LZ1) was further developed into a LZ78 ver- sion (also called LZ2). The latter version corresponds to the