tailieunhanh - Thuật toán Algorithms (Phần 30)

Tham khảo tài liệu 'thuật toán algorithms (phần 30)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 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 opposite 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 developed 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 characters appear much more often than others raster files for encoding pictures which can have large homogeneous areas and files for the digital representation 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 .