6 Saving space
This chapter covers
- Reducing the size of data by compression
- Simple compression of text by substitution
- Advanced compression with frequency counts
As computers get ever faster, we ask ever more of them: a high-resolution film streamed in real time, a faster download, or the same experience on a mobile device over a slow connection as we have at home or in the office over a fast one. When we talk of efficiency, we are concerned with the time taken to do a task, the space required to store data, and secondary effects such as how often we have to charge our device’s battery. And so we cannot simply say, “Things are getting faster all the time; we need not worry about efficiency.” In this chapter, we will delve into one tool for managing the size of information: compression.
6.1 Compression
An important tool for reducing the space information takes up (and so increasing the speed with which it can be moved around) is compression. The idea is to process the information in such a way that it not only becomes smaller but also so that it may be decompressed. In other words, the process must be reversible.