 dictionary-based approach that I have described. The original LZ77 uses, instead, a sliding-window approach. The LZ77 algorithm checks out the input symbol sequence, and searches for any match in a sliding-window buffer (the dictionary equivalent). The algorithm output, called a token, is made of three numbers: the offset of the sliding window, where the matched sequence is found to begin; the length of the matched sequence; and the unique code of the last unmatched symbol. Both LZ77 and LZ78 have generated a prolific family of variants (and related patents), which can be listed as: (For LZ77): LZR, LZSS (Lempel-Ziv-Storer-Szymanski), LZB, and LZH (Lampel- Ziv-Haruyasu); (For rZL878 LZW (Lempel-Ziv-Welch), LZC, LZT, LZMW, LZJ, and LZFG. 15 T.M. Cover and J.A. Thomas Elements of Information Theory (New York: John Wiley & Sons, 1991). 16 Recall that the entropy of a binary source is bounded to the maximum Hmax(X) = 1, which corresponds to a uniformly distributed source. 10.5 Exercises The LZ algorithm family has led to several data-compression standards and file-archival utilities known as Zip (from LZC), GNU zip or gzip (from LZ77), PKZIP (from LZW), PKARK, Bzip/Bzip2, ppmz, pack, lzexe (a MS-DOS utility), and compress (from LZC and LZW, a UNIX utility), for instance. Such programs make it possible to compress most ASCII-source files by a factor of two, and sometimes up to three, but with differ- ent performance and computing speeds. 17 The algorithm LZW is also used for image compression in the well-known formats called GIF (graphic interchange format) and TIFF (tagged image file format); for instance, GIF has become a leading standard for the exchange of graphics on the World Wide Web. The original LZ77 algorithm is used in the patent-free image format PNG (portable network graphics). See Appendix G for a more detailed description of data and image compression standards. Exercises 10.1 (B): Determine the coding efficiency corresponding to the symbol source defined in Table 10.7, using Elias-gamma and Elias-delt