Universal Compression and Retrieval

Rafail Krichevsky

Kluwer Academic 1994
A book review by Danny Yee © 1995 http://dannyreviews.com/
The preface to Universal Compression and Retrieval states that it is "intended for information theorists and computer scientists" and "may serve as a technical reference for communication engineers and database designers. Some of its parts may be useful for biologists". Its relevance to people designing new database algorithms is clear, but I fear that few engineers or biologists will get much out of Universal Compression and Retrieval. While it doesn't assume that much mathematical background — basic abstract algebra and complexity theory, some point set topology, a little Galois theory --, it is solid "claim; proof" mathematics, with little exploration of the significance of its results. The material covered includes different kinds of sources, entropy; encoding of different sources and the Kolmogorov complexity; universal numerators and hash-sets; universal sets, compressing maps and hash functions; and linear and polynomial Galois hashing, with applications to string matching and different methods of retrieval. Several new algorithms with good complexities are presented.

I found Universal Compression and Retrieval heavy going, partly because almost all the material was new to me (the volume is definitely not recommended as an introductory text) and partly because of the poor quality of the text, which is riddled with mistakes. The straight spelling and grammar errors are only distracting, but the convoluted syntax and the typographical mistakes — "<" signs where there should be ">" signs; use of the same symbol for two different purposes in the one formula — are really confusing. All of this could easily have been fixed by a copy-editor, so I think the blame should be assigned to the publisher, not to the author (who clearly isn't a native English speaker). A glance at another Kluwer Academic volume suggests that "no copy-editing" is their standard practice, so I'd recommend not buying any of their books without first checking that the density of errors is acceptable. That they can put this sort of material into a high quality, hardcover volume, printed on acid-free paper and priced so expensively, suggests that they have their priorities completely wrong.

July 1995

External links:
- buy from Amazon.com or Amazon.co.uk
Related reviews:
- books about computer science
- books about mathematics
%T Universal Compression and Retrieval
%A Krichevsky, Rafail
%I Kluwer Academic
%D 1994
%O hardcover, bibliography, index
%G ISBN 0792326725
%P viii,219pp