D. Salomon — Handbook of Data Compression (Fifth edition)

Автор: D. Salomon
Название книги: Handbook of Data Compression (Fifth edition)
Формат: PDF
Жанр: Математика
Страницы: 1370
Качество: Изначально компьютерное, E-book

This book provides a comprehensive reference for the many different types and methods of compression. Included are a detailed and helpful taxonomy, analysis of most common methods, and discussions on the use and comparative benefits of methods and description of «how to» use them. Detailed descriptions and explanations of the most well-known and frequently used compression methods are covered in a self-contained fashion, with an accessible style and technical level for specialists and non-specialists.

Gentle Reader. The thick, heavy volume you are holding in your hands was intended
to be the fifth edition of Data Compression: The Complete Reference.
Instead, its title indicates that this is a handbook of data compression. What makes
a book a handbook? What is the difference between a textbook and a handbook? It
turns out that “handbook” is one of the many terms that elude precise definition. The
many definitions found in dictionaries and reference books vary widely and do more to
confuse than to illuminate the reader. Here are a few examples:
A concise reference book providing specific information about a subject or location
(but this book is not concise).
A type of reference work that is intended to provide ready reference (but every
reference work should provide ready reference).
A pocket reference is intended to be carried at all times (but this book requires big
pockets as well as deep ones).
A small reference book; a manual (definitely does not apply to this book).
General information source which provides quick reference for a given subject area.
Handbooks are generally subject-specific (true for this book).
Confusing; but we will use the last of these definitions. The aim of this book is to
provide a quick reference for the subject of data compression. Judging by the size of the
book, the “reference” is certainly there, but what about “quick?” We believe that the
following features make this book a quick reference:
The detailed index which constitutes 3% of the book.
The glossary. Most of the terms, concepts, and techniques discussed throughout
the book appear also, albeit briefly, in the glossary.
The particular organization of the book. Data is compressed by removing redundancies
in its original representation, and these redundancies depend on the type of
data. Text, images, video, and audio all have different types of redundancies and are
best compressed by different algorithms which in turn are based on different approaches.
Thus, the book is organized by different data types, with individual chapters devoted
to image, video, and audio compression techniques. Some approaches to compression,
however, are general and work well on many different types of data, which is why the
book also has chapters on variable-length codes, statistical methods, dictionary-based
methods, and wavelet methods.
The main body of this volume contains 11 chapters and one appendix, all organized
in the following categories, basic methods of compression, variable-length codes, statistical
methods, dictionary-based methods, methods for image compression, wavelet methods,
video compression, audio compression, and other methods that do not conveniently
fit into any of the above categories. The appendix discusses concepts of information
theory, the theory that provides the foundation of the entire field of data compression.
In addition to its use as a quick reference, this book can be used as a starting point
to learn more about approaches to and techniques of data compression as well as specific
algorithms and their implementations and applications. The broad coverage makes the
book as complete as practically possible. The extensive bibliography will be very helpful
to those looking for more information on a specific topic. The liberal use of illustrations
and tables of data helps to clarify the text.
This book is aimed at readers who have general knowledge of computer applications,
binary data, and files and want to understand how different types of data can be
compressed. The book is not for dummies, nor is it a guide to implementors. Someone
who wants to implement a compression algorithm A should have coding experience and
should rely on the original publication by the creator of A.
In spite of the growing popularity of Internet searching, which often locates quantities
of information of questionable quality, we feel that there is still a need for a concise,
reliable reference source spanning the full range of the important field of data compression.
New to the Handbook
The following is a list of the new material in this book (material not included in
past editions of Data Compression: The Complete Reference).
The topic of compression benchmarks has been added to the Introduction.
The paragraphs titled “How to Hide Data” in the Introduction show how data
compression can be utilized to quickly and efficiently hide data in plain sight in our
computers.
Several paragraphs on compression curiosities have also been added to the Introduction.
The new Section 1.1.2 shows why irreversible compression may be useful in certain
situations.
Chapters 2 through 4 discuss the all-important topic of variable-length codes. These
chapters discuss basic, advanced, and robust variable-length codes. Many types of VL
codes are known, they are used by many compression algorithms, have different properties,
and are based on different principles. The most-important types of VL codes are
prefix codes and codes that include their own length.
Section 2.9 on phased-in codes was wrong and has been completely rewritten.
An example of the start-step-stop code (2, 2,∞) has been added to Section 3.2.
Section 3.5 is a description of two interesting variable-length codes dubbed recursive
bottom-up coding (RBUC) and binary adaptive sequential coding (BASC). These codes
represent compromises between the standard binary (β) code and the Elias gamma
codes.
Section 3.28 discusses the original method of interpolative coding whereby dynamic
variable-length codes are assigned to a strictly monotonically increasing sequence of
integers.
Section 5.8 is devoted to the compression of PK (packed) fonts. These are older
bitmaps fonts that were developed as part of the huge TEX project. The compression
algorithm is not especially efficient, but it provides a rare example of run-length encoding
(RLE) without the use of Huffman codes.
Section 5.13 is about the Hutter prize for text compression.
PAQ (Section 5.15) is an open-source, high-performance compression algorithm and
free software that features sophisticated prediction combined with adaptive arithmetic
encoding. This free algorithm is especially interesting because of the great interest it
has generated and because of the many versions, subversions, and derivatives that have
been spun off it.
Section 6.3.2 discusses LZR, a variant of the basic LZ77 method, where the lengths
of both the search and look-ahead buffers are unbounded.
Section 6.4.1 is a description of LZB, an extension of LZSS. It is the result of
evaluating and comparing several data structures and variable-length codes with an eye
to improving the performance of LZSS.
SLH, the topic of Section 6.4.2, is another variant of LZSS. It is a two-pass algorithm
where the first pass employs a hash table to locate the best match and to count
frequencies, and the second pass encodes the offsets and the raw symbols with Huffman
codes prepared from the frequencies counted by the first pass.
Most LZ algorithms were developed during the 1980s, but LZPP, the topic of Section
6.5, is an exception. LZPP is a modern, sophisticated algorithm that extends LZSS
in several directions and has been inspired by research done and experience gained by
many workers in the 1990s. LZPP identifies several sources of redundancy in the various
quantities generated and manipulated by LZSS and exploits these sources to obtain
better overall compression.
Section 6.14.1 is devoted to LZT, an extension of UNIX compress/LZC. The major
innovation of LZT is the way it handles a full dictionary.
LZJ (Section 6.17) is an interesting LZ variant. It stores in its dictionary, which
can be viewed either as a multiway tree or as a forest, every phrase found in the input.
If a phrase is found n times in the input, only one copy is stored in the dictionary. Such
behavior tends to fill the dictionary up very quickly, so LZJ limits the length of phrases
to a preset parameter h.
The interesting, original concept of antidictionary is the topic of Section 6.31. A
dictionary-based encoder maintains a list of bits and pieces of the data and employs this
list to compress the data. An antidictionary method, on the other hand, maintains a
list of strings that do not appear in the data. This generates negative knowledge that
allows the encoder to predict with certainty the values of many bits and thus to drop
those bits from the output, thereby achieving compression.
The important term “pixel” is discussed in Section 7.1, where the reader will discover
that a pixel is not a small square, as is commonly assumed, but a mathematical point.
Section 7.10.8 discusses the new HD photo (also known as JPEG XR) compression
method for continuous-tone still images.
ALPC (adaptive linear prediction and classification), is a lossless image compression
algorithm described in Section 7.12. ALPC is based on a linear predictor whose
coefficients are computed for each pixel individually in a way that can be mimiced by
the decoder.
Grayscale Two-Dimensional Lempel-Ziv Encoding (GS-2D-LZ, Section 7.18) is an
innovative dictionary-based method for the lossless compression of grayscale images.
Section 7.19 has been partially rewritten.
Section 7.40 is devoted to spatial prediction, a combination of JPEG and fractalbased
image compression.
A short historical overview of video compression is provided in Section 9.4.
The all-important H.264/AVC video compression standard has been extended to
allow for a compressed stream that supports temporal, spatial, and quality scalable
video coding, while retaining a base layer that is still backward compatible with the
original H.264/AVC. This extension is the topic of Section 9.10.
The complex and promising VC-1 video codec is the topic of the new, long Section
9.11.
The new Section 11.6.4 treats the topic of syllable-based compression, an approach
to compression where the basic data symbols are syllables, a syntactic form between
characters and words.
The commercial compression software known as stuffit has been around since 1987.
The methods and algorithms it employs are proprietary, but some information exists
in various patents. The new Section 11.16 is an attempt to describe what is publicly
known about this software and how it works.
There is now a short appendix that presents and explains the basic concepts and
terms of information theory.
We would like to acknowledge the help, encouragement, and cooperation provided
by Yuriy Reznik, Matt Mahoney, Mahmoud El-Sakka, Pawel Pylak, Darryl Lovato,
Raymond Lau, Cosmin Trut¸a, Derong Bao, and Honggang Qi. They sent information,
reviewed certain sections, made useful comments and suggestions, and corrected numerous
errors.
A special mention goes to David Bryant who wrote Section 10.11.
Springer Verlag has created the Springer Handbook series on important scientific
and technical subjects, and there can be no doubt that data compression should be
included in this category. We are therefore indebted to our editor, Wayne Wheeler,
for proposing this project and providing the encouragement and motivation to see it
through.