Universal Compression and Retrieval

This volume constitutes a comprehensive self-contained course on source encoding. This is a rapidly developing field and the purpose of this book is to present the theory from its beginnings to current developments. This text incorporates information retrieval into source coding and places an emphasis on the trade-off between complexity and the quality of coding; i.e. what is the price of achieving a maximum degree of data compression? Special attention is paid to universal families which contain a good compressing map for every source in a set. The volume presents a new algorithm for retrieval, which is optimal with respect to both program length and running time, and algorithms for hashing and adaptive on-line compressing. All the main tools of source coding and data compression such as Shannon, Ziv-Lempel, Gilbert-Moore codes, Kolmogorov complexity e-entropy, lexicographic and digital search, are discussed. Moreover, data compression methods are described for developing short programs for partially specified Boolean functions, short formulas for threshold functions, identification keys, stochastic algorithms for finding the occurrence of a word in a text and T-independent sets. This work is aimed at researchers and graduate students of information theory and theoretical computer science. It shouldalso serve as a useful reference for communication engineers and database designers.