Universal Compression and Retrieval
By: by Rafail Krichevsky
Series: Mathematics and Its Applications -- 274; Mathematics and Its Applications -- 274
Publisher: Springer Netherlands
Published: 1994
Place of publication: Dordrecht
Language: eng
Format: [electronic resource] /
Number of pages: 223
ISBN-13: 9789048143573; 9789401736282
Subjects: Computer engineering; Coding theory; Computational complexity; Computer science
Description: 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 the latest developments, some of which appear in book form for the first time. The major differences between this volume and previously published works is that here information retrieval is incorporated into source coding instead of discussing it separately. Second, this volume 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? Third, 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 epsilon-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. For researchers and graduate students of information theory and theoretical computer science. The book will also serve as a useful reference for communication engineers and database designers.
Notes: Online full text is restricted to subscribers.

Also available in print.

Mode of access: World Wide Web.