nach oben

2010 | Buch

Handbook of Data Compression

verfasst von: David Salomon, Giovanni Motta

Verlag: Springer London

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Data compression is one of the most important fields and tools in modern computing. From archiving data, to CD-ROMs, and from coding theory to image analysis, many facets of modern computing rely upon data compression. 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.

Inhaltsverzeichnis

Frontmatter

1. Basic Techniques

Abstract

Data is compressed by reducing its redundancy, but this also makes the data less reliable, more prone to errors. Increasing the integrity of data, on the other hand, is done by adding check bits and parity bits, a process that increases the size of the data, thereby increasing redundancy. Data compression and data reliability are therefore opposites, and it is interesting to note that the latter is a relatively recent field, whereas the former existed even before the advent of computers. The sympathetic telegraph, discussed in the Preface, the Braille code of 1820 (Section 1.1.1), the shutter telegraph of the British admiralty [Bell et al. 90], and the Morse code of 1838 (Table 2.1) use simple, intuitive forms of compression. It therefore seems that reducing redundancy comes naturally to anyone who works on codes, but increasing it is something that “goes against the grain” in humans. This section discusses simple, intuitive compression methods that have been used in the past. Today these methods are mostly of historical interest, since they are generally inefficient and cannot compete with the modern compression methods developed during the last several decades.

David Salomon, Giovanni Motta

2. Basic VL Codes

Abstract

The dates of most of the important historical events are known, but not always very precisely. We know that Kublai Khan, grandson of Ghengis Khan, founded the Yuan dynasty in 1280 (it lasted until 1368), but we don’t know precisely (i.e., the month, day and hour) when this act took place. A notable exception to this state of affairs is the modern age of telecommunications, a historical era whose birth is known precisely, up to the minute. On Friday, 24 May 1844, at precisely 9:45 in the morning, Samuel Morse inaugurated the age of modern telecommunications by sending the first telegraphic message in his new code. The message was sent over an experimental line funded by the American Congress from the Supreme Court chamber in Washington, DC to the B & O railroad depot in Baltimore, Maryland. Taken from the Bible (Numbers 23:23), the message was “What hath God wrought?” It had been suggested to Morse by Annie Ellsworth, the young daughter of a friend. It was prerecorded on a paper tape, was sent to a colleague in Baltimore, and was then decoded and sent back by him to Washington. An image of the paper tape can be viewed at [morse-tape 06].

David Salomon, Giovanni Motta

3. Advanced VL Codes

Abstract

We start this chapter with codes for the integers. This is followed by many types of variable-length codes that are based on diverse principles, have been developed by different approaches, and have various useful properties and features.

David Salomon, Giovanni Motta

4. Robust VL Codes

Abstract

The many codes included in this chapter have a common feature; thet are robust. Any errors that creep into a string of such codewords can either be detected (or even corrected automatically) or have only limited effects and do not propagate indefinitely. The chapter starts with a discussion of the principles of error-control codes.

David Salomon, Giovanni Motta

5. Statistical Methods

Abstract

Statistical data compression methods employ variable-length codes, with the shorter codes assigned to symbols or groups of symbols that appear more often in the data (have a higher probability of occurrence). Designers and implementors of variablelength codes have to deal with the two problems of (1) assigning codes that can be decoded unambiguously and (2) assigning codes with the minimum average size. The first problem is discussed in detail in Chapters 2 through 4, while the second problem is solved in different ways by the methods described here.

David Salomon, Giovanni Motta

6. Dictionary Methods

Abstract

Statistical compression methods use a statistical model of the data, which is why the quality of compression they achieve depends on how good that model is. Dictionarybased compression methods do not use a statistical model, nor do they use variablelength codes. Instead they select strings of symbols and encode each string as a token using a dictionary. The dictionary holds strings of symbols, and it may be static or dynamic (adaptive). The former is permanent, sometimes permitting the addition of strings but no deletions, whereas the latter holds strings previously found in the input stream, allowing for additions and deletions of strings as new input is being read.

David Salomon, Giovanni Motta

7. Image Compression

Abstract

The first part of this chapter discusses the basic features and types of digital images and the main approaches to image compression. This is followed by a description of about 30 different compression methods.

David Salomon, Giovanni Motta

8. Wavelet Methods

Abstract

Back in the early 1800s, the French mathematician Joseph Fourier discovered that any periodic fucntion can be expressed as a (possibly infinite) sum of sines and cosines. This surprising fact is now known as Fourier expansion and it has many applications in engineering, mainly in the analysis of signals. It can isolate the various frequencies that underlie a signal and thereby enable the user to study the signal and also edit it by deleting or adding certain frequencies. The downside of Fourier expansion is that it does not tell us when (at which point or points in time) each frequency is active in a given signal. We therefore say that Fourier expansion offers frequency resolution but no time resolution.

David Salomon, Giovanni Motta

9. Video Compression

Abstract

Sound recording and the movie camera were among the greatest inventions of ThomasEdison. They were later united when “talkies” were developed, and they are still used together in video recordings. This unification is one reason for the popularity of movies and video. With the rapid advances in computers in the 1980s and 1990s came multimedia applications, where images and sound are combined in the same file. Such files tend to be large, which is why compressing them became an important field of research.

This chapter starts with basic discussions of analog and digital video, continues with the principles of video compression, and concludes with a description of several compression methods designed specifically for video, namely MPEG-1, MPEG-4, H.261, H.264, and VC-1.

David Salomon, Giovanni Motta

10. Audio Compression

Abstract

Text does not occupy much space in the computer. An average book, consisting of a million characters, can be stored uncompressed in about 1 Mbyte, because each character of text occupies one byte (the Colophon at the end of the book illustrates this with data collected from the book itself).

David Salomon, Giovanni Motta

11. Other Methods

Abstract

Previous chapters discuss the main classes of compression methods: RLE, statistical methods, and dictionary-based methods. There are data compression methods that are not easy to classify and do not clearly belong in any of the classes discussed so far. A few such methods are described here.

David Salomon, Giovanni Motta

Backmatter

Titel: Handbook of Data Compression
verfasst von: David Salomon
Giovanni Motta
Verlag: Springer London
Electronic ISBN: 978-1-84882-903-9
Print ISBN: 978-1-84882-902-2
DOI: https://doi.org/10.1007/978-1-84882-903-9