Lossless Data Compression - Important Concepts in Signal Processing, Image Processing and Data Compression - page 55

previous frame in video encoding. In the wavelet transformation the probabilities are also
passed through the hierarchy.
Historical legal issues
Many of these methods are implemented in open-source and proprietary tools,
particularly LZW and its variants. Some algorithms are patented in the USA and other
countries and their legal usage requires licensing by the patent holder. Because of patents
on certain kinds of LZW compression, and in particular licensing practices by patent
holder Unisys that many developers considered abusive, some open source proponents
encouraged people to avoid using the Graphics Interchange Format (GIF) for
compressing image files in favor of Portable Network Graphics PNG, which combines
the LZ77-based deflate algorithm with a selection of domain-specific prediction filters.
However, the patents on LZW have expired on June 20 2003.
Many of the lossless compression techniques used for text also work reasonably well for
indexed images, but there are other techniques that do not work for typical text that are
useful for some images (particularly simple bitmaps), and other techniques that take
advantage of the specific characteristics of images (such as the common phenomenon of
contiguous 2-D areas of similar tones, and the fact that color images usually have a
preponderance of a limited range of colors out of those representable in the color space).
As mentioned previously, lossless sound compression is a somewhat specialised area.
Lossless sound compression algorithms can take advantage of the repeating patterns
shown by the wave-like nature of the data - essentially using models to predict the "next"
value and encoding the (hopefully small) difference between the expected value and the
actual data. If the difference between the predicted and the actual data (called the "error")
tends to be small, then certain difference values (like 0, +1, -1 etc. on sample values)
become very frequent, which can be exploited by encoding them in few output bits.
It is sometimes beneficial to compress only the differences between two versions of a file
(or, in video compression, of an image). This is called delta compression (from the Greek
letter Δ which is commonly used in mathematics to denote a difference), but the term is
typically only used if both versions are meaningful outside compression and
decompression. For example, while the process of compressing the error in the above-
mentioned lossless audio compression scheme could be described as delta compression
from the approximated sound wave to the original sound wave, the approximated version
of the sound wave is not meaningful in any other context.
Lossless compression methods
By operation of the pigeonhole principle, no lossless compression algorithm can
efficiently compress all possible data, and completely random data streams cannot be
compressed. For this reason, many different algorithms exist that are designed either with
a specific type of input data in mind or with specific assumptions about what kinds of
redundancy the uncompressed data are likely to contain.