How Much Space Data Takes
Making a file smaller
Squeeze a run of repeated values into a count and a value, work out what that saves, and recognise the rows where it costs more than it saves.
A great deal of what a computer stores is the same value over and over. A picture of a wall is thousands of pixels of the same grey; a page of a book is line after line with the same margin. Writing every one of those out separately is honest but wasteful, and there is an obvious alternative: instead of writing the value once per pixel, write down how many there are and what they are. Nothing is thrown away, so the picture comes back exactly as it went in — but only if the row you did it to was the right kind of row.
A run, and what a run costs
A run is a stretch of pixels all the same colour, and it is written as a count followed by the letter: 6W means six white pixels one after another. Two things are written down for every run, a count and a letter, so a row written as runs costs two things per run — while writing the row out pixel by pixel costs one thing per pixel. Those two costs are what decide whether this is worth doing, and the count of pixels does not appear in the first of them at all. A row with very few runs is squeezed hard. A row with almost as many runs as pixels comes out bigger than it went in, and that is not a failure of the method, it is the method being applied to the wrong row.
Worked example
A row reads “WWWWWWWWGGB”. Write it in counted form, and work out what it costs.
Read from the left. Eight W in a row, so the first run is 8W.
The run ends where the letter changes, and not before. Counting the eight is the only fiddly part of the whole method.
Try it together
A row of 14 pixels turns out to have 9 runs in it. No letters this time — the two counts are all you need.
Work out both costs, and only then compare them.
1.What does writing this row as runs cost, in things?
Have a go
Have a go on your own. A row reads “BBBBGGGGGG”. Write it in counted form.
Ready to practise?
Eight questions on what you have just read. Nothing is timed, and you can play as many times as you like.