Week 27 · 4.3–4.4 Data compression, logic gates and truth tables · 3 lessons
1
Squeezing data smaller
Computing 8: Topics 4.3–4.4, pp. 268–282
GoalExplain what data compression is and how a repeated item can be stored once with its positions.
New words
data compression · making a file smaller by changing how its data is storedposition · the place of an item in the data, such as 1st, 2nd, 3rdreconstruct · build the original data back from the stored pieces
Explanation
Data compression makes a file smaller. A smaller file takes less storage space and is sent more quickly. One way to compress is to find items that are repeated. The computer stores each different item once, with its positions. Suppose a log is rain, rain, sun, rain, sun, sun, rain. Instead of seven words, the computer stores rain at 1, 2, 4 and 7, and sun at 3, 5 and 6. When the file is opened, the computer puts each item back in its positions. The original is built again. The saving is bigger when long items are repeated many times.
Item
Times
Positions
rain
4
1, 2, 4, 7
sun
3
3, 5, 6
Worked examples
Position
1
2
3
4
5
6
7
item
rain
rain
sun
rain
sun
sun
rain
Rebuild the log from the table. Position 1 is rain, 2 is rain, 3 is sun, 4 is rain, 5 is sun, 6 is sun, 7 is rain. The original log is rebuilt exactly.
Item
Positions
thunderstorm
1, 3, 4, 6, 7, 8
sunshine
2, 5
A longer log of eight days uses two long words: thunderstorm (12 letters) and sunshine (8 letters). Written in full, the characters add up to 88. In compressed form, each word is stored once (12 + 8 = 20 characters) and the eight positions need 8 more digits. That is 28 characters, which is much less than 88.
File
Size
Time at 5 MB per second
original
40 MB
8 s
compressed
10 MB
2 s
Why compress? A 40 MB file sent at 5 MB per second takes 8 seconds. If it is compressed to 10 MB, it takes 2 seconds. It also takes up a quarter of the space.
Class activity
Compress a chant (no computer). Write a 12-word chant on a strip of paper that uses only three different words, such as “up, down, up, up, down, round …”. Make a table with each different word and its positions. Give only the table to a partner and ask them to rebuild the chant. Did they get it right? Then try a chant with 12 different words. Can you compress it with this method? Explain why not. When is compression most useful? If you have a computer or tablet, ask an adult to show you the size of a file before and after it is put into a compressed folder.
Practice
1
Compress this list: red, blue, red, red, blue, green. Write each item with its positions.
Item
Positions
red
?
blue
?
green
?
red: 1, 3, 4. blue: 2, 5. green: 6.
2
Rebuild the data: go at 2, 3; stop at 1, 4, 6; slow at 5.
Item
Positions
go
2, 3
stop
1, 4, 6
slow
5
stop, go, go, stop, slow, stop.
3
A file of 60 MB is compressed to 15 MB. How many times faster is it to send, if the speed stays the same? Why?
4 times faster, because 60 ÷ 15 = 4: it has a quarter as much data to send.
4
A pupil says, “Compression changes the information, so the file after rebuilding is different.” Do you agree for this method?
No. The method stores each item and its positions, so the data is rebuilt exactly. The data is stored in a different way, but the content is the same.