Tài liệu Thuật toán Algorithms (Phần 30) pptx

22. File Compression

For the most part, the algorithms that we have studied have been de￾signed primarily to use as little time as possible and only secondarily to

conserve space. In this section, we’ll examine some algorithms with the op￾posite orientation: methods designed primarily to reduce space consumption

without using up too much time. Ironically, the techniques that we’ll examine

to save space are “coding” methods from information theory which were de￾veloped to minimize the amount of information necessary in communications

systems and therefore originally intended to save time (not space).

In general, most files stored on computer systems have a great deal of

redundancy. The methods we will examine save space by taking advantage

of the fact that most files have a relatively low “information content.” File

compression techniques are often used for text files (in which certain charac￾ters appear much more often than others), “raster” files for encoding pictures

(which can have large homogeneous areas), and files for the digital repre￾sentation of sound and other analog signals (which can have large repeated

patterns).

We’ll look at an elementary algorithm for the problem (which is still quite

useful) and an advanced “optimal” method. The amount of space saved by

these methods will vary depending on characteristics of the file. Savings of

20% to 50% are typical for text files, and savings of 50% to 90% might be

achieved for binary files. For some types of files, for example files consisting

of random bits, little can be gained. In fact, it is interesting to note that any

general-purpose compression method must make some files longer (otherwise

we could continually apply the method to produce an arbitrarily small file).

On one hand, one might argue that file compression techniques are less

important than they once were because the cost of computer storage devices

has dropped dramatically and far more storage is available to the typical user

than in the past. On the other hand, it can be argued that file compression

283