File Compression

WinZipMany computer users make extensive use of compressed files, often known as ZIP files. Compression is a useful technique as it speeds up the transmission of files over a slow network connection and reduces the space required to store files on disk. A utility program such as WinZip or WinRar can be used to compress and decompress files.

Computer files often exhibit redundancy, ie: the same information is repeated in different places. For example, if a short text file contains 100 words, we may find that 50 of these are repetitions of a word that has already been used.

This website gives an example based on John F Kennedy’s famous inaugural speech:

“Ask not what your country can do for you — ask what you can do for your country.”

Even in this short phrase there is considerable redundancy: the following words all appear twice: ask, what, your, country, can, do, for, you, meaning that almost half of the phrase is redundant.

Most file compression programs make use of the LZ adaptive dictionary-based algorithm. The initials are derived from the originators of the algorithm, Lempel and Ziv. Dictionaries can be created in a variety of ways, but one of the simplest is a numbered list. We can go through the phrase quoted above,  select the repeated words and place them in a numbered list:

  1. ask
  2. what
  3. your
  4. country
  5. can
  6. for
  7. you

We can now rewrite our sentence, using the index numbersa rather than the original words:

“1 not 2 3 4 5 6 7 8 — 1 2 8 5 6 7 3 4”.

This is obviously shorter than the original phrase, but, since we have to save the dictionary as well as the compressed text it won’t really save a lot of space. However, with a longer piece of text there would be frequent repetitions of words so space savings could be significant.

In practice, file compression programs build up a dictionary of patterns of characters, rather than words. For example the pattern “can do for you” occurs twice in our phrase. Using patterns makes the dictionary smaller and allows a greater degree of compression.

The type of compression known as lossless compression, because it allows the original file to be recreated exactly. Another type of compression, known as lossy compression is widely used for compressing audio, video and image files. With lossy compression it is not possible to recreate the original file exactly, but you should be able to recreate one which looks or sounds virtually the same. Obviously, lossy compression is not useful for some types of files such as text files, computer programs or databases, as we need to be able to recreate the original file exactly.

This Wikipedia article giver further information about file compression.

Next: Sound