Through information theory, problems of communication and compression can be precisely modeled, formulated, and analyzed, and this information can be transformed by means of algorithms. Also, learning can be viewed as compression with side information. Aimed at students and researchers, this book addresses data compression and redundancy within existing methods and central topics in theoretical data compression, demonstrating how to use tools from analytic combinatorics to discover and analyze precise behavior of source codes. It shows that to present better learnable or extractable information in its shortest description, one must understand what the information is, and then algorithmically extract it in its most compact form via an efficient compression algorithm. Part I covers fixed-to-variable codes such as Shannon and Huffman codes, variable-to-fixed codes such as Tunstall and Khodak codes, and variable-to-variable Khodak codes for known sources. Part II discusses universal source coding for memoryless, Markov, and renewal sources.

The term analytic information theory has been coined to describe problems of information theory studied by analytic tools. The approach of applying tools from analysis of algorithms to problems of source coding and, in general, to information theory lies at the crossroad of computer science and information theory. Combining the tools from both areas often provides powerful results, such as computer scientist Abraham Lempel and information theorist Jacob Ziv working together in the late 1970s to develop compression algorithms that are now widely referred to as Lempel-Ziv algorithms and are the basis of the ZIP compression still used extensively in computing today. This monograph surveys the use of these techniques for the rigorous analysis of code redundancy for known sources in lossless data compression. A separate chapter is devoted to precise analyses of each of three types of lossless data compression schemes, namely fixed-to-variable length codes, variable-to-fixed length codes, and variable-to-variable length codes. Each one of these schemes is described in detail, building upon work done in the latter part of the 20th century to present new and powerful techniques. For the first time, this survey presents redundancy for universal variable-to-fixed and variable-to-variable length codes in a comprehensive and coherent manner. The monograph will be of interest to computer scientists and information theorists working on modern coding techniques. Written by two leading experts, it provides the reader with a unique, succinct starting point for their own research into the area.