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.
