Fundamental Data Compression

Ida Mengyi Pu

• Publisher: Butterworth-Heinemann
• Year: 2005
• ISBN:
  9780080530260
• Topic: Informatica
• Subtopic: Informatica generale

Fundamental Data Compression provides all the information students need to be able to use this essential technology in their future careers. A huge, active research field, and a part of many people's everyday lives, compression technology is an essential part of today's Computer Science and Electronic Engineering courses. With the help of this book, students can gain a thorough understanding of the underlying theory and algorithms, as well as specific techniques used in a range of scenarios, including the application of compression techniques to text, still images, video and audio. Practical exercises, projects and exam questions reinforce learning, along with suggestions for further reading.* Dedicated data compression textbook for use on undergraduate courses
* Provides essential knowledge for today's web/multimedia applications
* Accessible, well structured text backed up by extensive exercises and sample exam questions

Chapter 1

Introduction

Data compression is, in the context of computer science, the science (and art) of representing information in a compact form. It has been one of the critical enabling technologies for the ongoing digital multimedia revolution for decades.

Most people frequently use data compression software such as zip, gzip and WinZip (and many others) to reduce the file size before storing or transferring it in media. Compression techniques are embedded in more and more software and data are often compressed without people knowing it.

Data compression has become a common requirement for most application software as well as an important and active research area in computer science. Without compression techniques, none of the ever-growing Internet, digital TV, mobile communication or increasing video communication techniques would have been practical developments.

Typical examples of application areas that are relevant to and motivated by data compression include

• personal communication systems such as facsimile, voice mail and telephony

• computer systems such as memory structures, disks and tapes

• mobile computing

• distributed computer systems

• computer networks, especially the Internet

• multimedia evolution, imaging, signal processing

• image archival and videoconferencing

• digital and satellite TV.

Practical problems have motivated various researches in data compression. Equally, research in data compression has also been based on or stimulated other new subject areas. Partly due to its broad application territory, data compression overlaps with many science branches and can be found in many different subject areas. For example, you will see chapters or sections dedicated to data compression in books on

• information theory

• coding theory

• computer networks and telecommunications

• digital signal processing

• image processing

• multimedia

• steganography

• computer security.

The language used in unrelated disciplines can be substantially different. In this book, the word data is in general used to mean the information in digital form on which computer programs operate, and compression means a process of removing redundancy in the data. By ‘compressing data’, we actually mean deriving techniques or, more specifically, designing efficient algorithms to:

• represent data in a less redundant fashion

• remove the redundancy in data

• implement compression algorithms, including both compression and decompression.

The interests and goals also tend to be diverse among people with different disciplinary backgrounds. This book focuses on the algorithmic aspects of data compression. We view data compression as a process of deriving algorithmic solutions to a compression problem. An algorithmic problem is a general question to be answered by an ordered sequence of instructions. The instruction sequence is regarded as a sequential algorithm for the problem as well as the solution to the problem. The algorithm allows a solution to any instance of the problem to be derived by execution of the algorithm. For example, a searching problem may be defined as follows:

Given a set s of elements and a target x, is the target x in the set?

This question is ‘general’ because it includes many instances. The set can contain any collection of elements and the target x can be any one of the same type. For instance, if s = (12, 34, 2, 9, 7, 5), is x = 7 in the list? The algorithmic solution to this problem is to find an algorithm which derives an answer to every instance of the problem. A native algorithm would be the so-called sequential search as in Algorithm 1.1. The string is stored in a one-dimensional array L[i].

The algorithm is written in pseudocode that is close enough to most conventional high-level computer languages. The advantage of using pseudocode is to allow the algorithm design to concentrate on the algorithmic ideas instead of being distracted by syntax details of a certain computer language. We shall present most algorithms in the book in pseudocode (see Appendix D).

1.1 Data compression problems

A compression problem involves finding an efficient algorithm to remove various redundancy from a certain type of data. The general question to ask here would be, for example, given a string s, what is the alternative sequence of symbols which takes less storage space? The solutions to the compression problems would then be the compression algorithms that will derive an alternative sequence of symbols which contains fewer number of bits in total, plus the decompression algorithms to recover the original string.

How many fewer bits? It would depend on the algorithms but it would also depend on how much the redundancy can be extracted from the original data. Different data may require different techniques to identify the redundancy and to remove the redundancy in the data. Obviously, this makes the compression problems ‘hard’ to solve because the general question is difficult to answer easily when it contains too many instances. Fortunately, we can take certain constraints and heuristics into consideration when designing algorithms.

There is no ‘one size fits all’ solution for data compression problems. In data compression studies, we essentially need to analyse the characteristics of the data to be compressed and hope to deduce some patterns in order to achieve a compact representation. This gives rise to a variety of data modelling and representation techniques, which are at the heart of compression techniques.

1.1.1 Compression

Data compression can be viewed as a means for efficient representation of a digital source of data such as text, image, sound or any combination of all these types such as video. The goal of data compre...