You know the situation. You are searching for something on the Internet. The page is taking ages to download. The images probably have megabytes of data. Do you wait? Or do you give up and try another site?

Is there a way that we can reduce the size of the file we are sending (or storing) without reducing the quality of the file - yes, we can compress the data.

Count the characters, including spaces. There are 88. So, without any fancy formatting, this data would take up 88 bytes of memory.

A clever computer scientist devised a way to reduce the amount of memory required to store the text:

A repeating pattern, tter has been replaced with a shorter key, 1, and a key table has been created.

The poem now requires 64 bytes to store it and the key requires 5 bytes = 69 byes. This is a saving of about 25% - not bad for a simple example.

Because the compressed data is being stored with its key, the orignal information can be retreived by decompressing the file. No information is lost!

This is an example of lossless compression.

So, in this example, there is a compressed message and also a key to allow decompression to happen. The total filesize is the size of the compressed message plus the size of the key.

   Task 1

You are going to have a go at compressing some text by creating a key. Your challenge is to compress the text as much as you can.

Here is a link to the online widget you will be using.

Here is a link to the worksheet you will complete.

Complete the worksheet, pasting a screenshot of your solution where indicated.

A heuristic approach to problem-solving

Sometimes it would take an unreasonable amount of time to find the optimal solution to a problem.

Sometimes we just have to create the best solution we can with the time and knowledge that we have available. This is called a heuristic approach to problem-solving.

You have been experiencing a heuristic approach in solving the above problem. It involves trial and error and dealing with unexpected problems that appear along the way.

However, once you are satisfied with your solution, you should note it down. One way to do this is to develop an algorithm.

An algorithm is a clear sequence of steps that allow a problem to be solved. It can be written in plain English. Anybody should be able to follow your algorithm to solve the problem.

   Task 2

Create an algorithm that shows the sequence of steps you used to solve the text compression problem. Write each step clearly on a piece of paper. Later, you will give your algorithm to another person and (s)he will try to follow it!

Some problems are really hard to find an optimal solution. Text compression falls into this category. We are forced to follow a heuristic approach to solving the problem, doing the best we can and hoping that we can improve it given time.

Compressing digital data comes in two forms: lossy and lossless compression.

lossy compression means that some of the data will be gone forever when compression happens. This might mean a reduction in quality of the data, for example an image might look pixelated and blurry after compression. However, it is still possible to use lossy compression without too much loss of quality, as we will see later.

The other form of compression is lossless compression. This is when data is compressed and can be decompressed to recreate the original data perfectly. The text compression methods we looked at in this unit are an example of lossless compression.

Like

Thoughts   3