+612 9045 4394
$7.95 Delivery per order to Australia and New Zealand
100% Australian owned
Over a hundred thousand in-stock titles ready to ship
Universal Compression and Retrieval : Mathematics and Its Applications - Rafael Krichevsky

Universal Compression and Retrieval

Mathematics and Its Applications

Hardcover Published: 28th February 1994
ISBN: 9780792326724
Number Of Pages: 224

Share This Book:


or 4 easy payments of $79.05 with Learn more
Ships in 15 business days

Earn 632 Qantas Points
on this Book

Other Available Editions (Hide)

  • Paperback View Product Published: 6th December 2010
    Ships in 15 business days

Objectives Computer and communication practice relies on data compression and dictionary search methods. They lean on a rapidly developing theory. Its exposition from a new viewpoint is the purpose of the book. We start from the very beginning and finish with the latest achievements of the theory, some of them in print for the first time. The book is intended for serving as both a monograph and a self-contained textbook. Information retrieval is the subject of the treatises by D. Knuth (1973) and K. Mehlhorn (1987). Data compression is the subject of source coding. It is a chapter of information theory. Its up-to-date state is presented in the books of Storer (1988), Lynch (1985), T. Bell et al. (1990). The difference between them and the present book is as follows. First. We include information retrieval into source coding instead of discussing it separately. Information-theoretic methods proved to be very effective in information search. Second. For many years the target of the source coding theory was the estimation of the maximal degree of the data compression. This target is practically bit today. The sought degree is now known for most of the sources. We believe that the next target must be the estimation of the price of approaching that degree. So, we are concerned with trade-off between complexity and quality of coding. Third. We pay special attention to universal families that contain a good comĀ­ pressing map for every source in a set.

Introductionp. 1
Nomenclaturep. 4
Information Source and Entropyp. 8
Finite Combinatorial Sourcesp. 8
Epsilon-entropyp. 11
Stochastic Sourcesp. 16
Stationary Stochastic Sourcesp. 20
Stationary Combinatorial Sources and Jablonskii Invariant Classesp. 22
Source Codingp. 27
Types of Codesp. 27
Kraft Inequality and Levenstein Codep. 33
Encoding of Combinatorial Sourcesp. 38
Hashingp. 41
Encoding of Individual Words and Stochastic Sourcesp. 44
Equiprobable Letters and Threshold Functionsp. 51
Stationary Sourcesp. 55
Kolmogorov Complexityp. 62
Majorizing the Kolmogorov Complexityp. 66
Universal Codesp. 74
Encoding of Sets of Stochastic Sourcesp. 74
Block-to Variable Length Encoding of Bernoulli Sourcesp. 78
Variable-Length-to-Block Encoding of Bernoulli Sourcesp. 82
Adaptive Encodingp. 86
Monotone Sourcesp. 91
Universal Encoding of Combinatorial Sourcesp. 97
Universal Encoding of Stationary Sourcesp. 102
Universal Sets of Compressing Mapsp. 109
Definition of Universal Setp. 109
Covering Lemmap. 111
Cluster Distributionp. 112
Large Deviations Probabilitiesp. 116
Universal Numeratorp. 123
Universal Hash - Setsp. 127
Piercing Sets and Independent Setsp. 133
Elementary Universal Setsp. 135
Universal Sets Based on Codesp. 135
Linear Galois Hashingp. 139
Polynomial Galois Hashingp. 143
String Matchingp. 151
Digital Retrievalp. 152
Digital Calculation of Boolean Functionsp. 161
Lexicographic Retrievalp. 164
Enumerative Retrievalp. 168
Optimal Numeratorp. 175
Lexicographic-Polynomial Partitionsp. 175
Multilevel Galois Partitionsp. 183
Partition-Numerator Interfacep. 190
Low Redundant Numeratorsp. 194
Highly Redundant Numeratorsp. 196
Channels with Arbitrary Additive Noisep. 198
Partial Boolean Functions, Piercing and Independent Sets, Threshold Formulasp. 200
Short Tables for Rapid Computation of Lipschitz Functionsp. 202
Appendix 1p. 209
Appendix 2p. 210
Referencesp. 213
Indexp. 218
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9780792326724
ISBN-10: 0792326725
Series: Mathematics and Its Applications
Audience: General
Format: Hardcover
Language: English
Number Of Pages: 224
Published: 28th February 1994
Country of Publication: NL
Dimensions (cm): 24.89 x 16.15  x 1.85
Weight (kg): 0.54

Earn 632 Qantas Points
on this Book