Study Guide

Data Compression

Why files are made smaller, how run-length encoding shortens repeated data without losing anything, and how lossy compression shrinks a file by permanently removing data.

Lesson 1.10 Data Representation

For: Cambridge IGCSE Computer Science learners, or anyone who has met images, sound and file sizes

Stage: Think

A shorter message

A fictional jeweller, Dalia, orders a bead pattern by phone. Each call costs money for every second, so she wants the message to be as short as possible, but the supplier must be able to rebuild the exact pattern. The pattern has 16 beads in a row:

white, white, white, white, white, white, white, white, black, black, black, black, white, white, white, white.

Think it through

How could Dalia say this pattern in far fewer words, so that the supplier still gets every bead right?

Show what happens

She could say how many beads of each colour come in a row: “8 white, 4 black, 4 white.” That is six words, in place of sixteen, and nothing is lost: the supplier can rebuild the exact pattern.

Making a file smaller is called compression. Dalia’s method stores a repeated value once, together with how many times it repeats. That is run-length encoding (RLE), and a group of identical items next to each other is a run.

Stage: Discover

Run-length encoding on text

  1. Find the runs. Reading from the left: AAAA (4 As), BBB (3 Bs), CC (2 Cs) and D (1 D).
  2. Write each run as a count and then the character. 4A, 3B, 2C, 1D.
  3. Join them. 4A3B2C1D.
  4. Compare. The original has 10 characters, and the encoded version has 8.

The conversion can be reversed with no loss: 4A3B2C1D is read as AAAA BBB CC D. The books differ about the order of the pair; this lesson always writes the count first.

Encoding text with RLE
OriginalRun-length encoded
WWWWBBB4W3B
AAABCCCC
PPPPPQQ
XXXXXXXXXX (ten Xs)
ABAB

    Show the completed table
    OriginalRun-length encoded
    WWWWBBB4W3B
    AAABCCCC3A1B4C
    PPPPPQQ5P2Q
    XXXXXXXXXX (ten Xs)10X
    ABAB1A1B1A1B

    Think it through

    Look at the last row. ABAB has 4 characters. How many characters does its run-length encoded form have? What does this tell you about when RLE is useful and when it is not?

    Show a model answer

    1A1B1A1B has 8 characters, twice as many as the original. RLE only helps when the data has long runs of the same value. When the values keep changing, each run is a single item and the counts make the data longer.

    RLE makes ten Xs into three characters, but makes ABAB twice as long. A method of compression works well for some kinds of data, and badly for others. That is why a picture with large areas of one colour compresses well with RLE and a photograph, where nearly every pixel differs from its neighbour, does not.

    Decoding RLE back to text
    Run-length encodedOriginal
    2A3BAABBB
    5X2Y
    3A2B1C
    1H1I
    9Z

      Show the completed table
      Run-length encodedOriginal
      2A3BAABBB
      5X2YXXXXXYY
      3A2B1CAAABBC
      1H1IHI
      9ZZZZZZZZZZ

      Decoding gets back exactly the text that was encoded. Nothing was lost, which is the key idea of the next steps.

      Stage: Predict

      Why make a file smaller?

      A fictional pupil shares a video file of 8 MiB. She sends it over a connection that carries 1 MiB each second.

      Think it through

      How long does it take to send the file? If the same video were compressed to 2 MiB, how long would it take then? What else gets smaller, besides the time?

      Show what happens

      8 MiB at 1 MiB a second takes 8 seconds. Compressed to 2 MiB, it takes 2 seconds. The compressed file also takes less room on the pupil’s phone and on every device that stores a copy, and it uses less of the connection’s capacity, which leaves more for others.

      Compression exists to reduce the size of a file. The smaller size has three results:

      • Less storage space is needed, so more files fit on a device.
      • Less bandwidth is needed. Bandwidth is the amount of data a connection can carry in a given time, so a smaller file uses less of it, and more users can share one connection.
      • A shorter transmission time: the file arrives sooner, as in the 8 seconds against 2 seconds above.

      Apply it

      A file of 12 MiB is compressed to 3 MiB, and sent over a connection that carries 1 MiB each second. How much shorter is the transmission time?
      Show the answer

      Answer: C. 9 seconds shorter, because 12 seconds becomes 3 seconds.

      Before: 12 MiB ÷ 1 MiB a second = 12 seconds. After: 3 ÷ 1 = 3 seconds. The saving is 12 − 3 = 9 seconds.

      Stage: Predict

      Keeping everything or letting some go

      RLE rebuilds the original exactly. There is another way to make a file smaller: take data out.

      Think it through

      A pupil has a photo of 1024 × 768 pixels with a colour depth of 24 bits (2.25 MiB). To make it smaller she reduces the colour depth to 8 bits. What is the new size? Could she get the original 24-bit colours back from the smaller file?

      Show what happens

      The new size is 1024 × 768 × 8 = 6 291 456 bits, which is 786 432 bytes, or 768 KiB, or 0.75 MiB: a third of the size. She could not get the 24-bit colours back, because the extra colour information has been thrown away and is not stored anywhere in the new file.

      This is the difference between the two types of compression:

      Do not confuse: Lossless and lossy compression

      Is anything lost?Lossless
      Nothing is lost for good. Decompressing gives back exactly the original data.Run-length encoding: 4A3B2C1D decodes to AAAABBBCCD.
      Is anything lost?Lossy
      Some data is removed permanently, so the file is smaller but cannot be restored.Reducing the colour depth from 24 bits to 8 bits.

      Both make the file smaller. The difference is whether the original data can be got back.

      1. Reduce the colour depth. A 1024 × 768 image at 24 bits is 2.25 MiB. At 8 bits it is 0.75 MiB, as in the question above. It is a third of the size, and has only 256 colours.
      2. Reduce the resolution. If the same image is shrunk to 512 × 384 pixels at 24 bits, it has a quarter of the pixels, so its size is 2.25 ÷ 4 = 0.5625 MiB (576 KiB). The fine detail is gone for good.
      3. Reduce the sample rate of a sound. A recording at 16 000 Hz is 2000 KiB for 64 seconds (16 bits for each sample). At 8000 Hz it is 1000 KiB: half the size, with less of the wave kept.
      4. Why each is lossy. In every case a number of the original values is no longer stored, so no method can put them back.

      Check your understanding

      A sound is compressed by lowering its sample resolution from 16 bits to 8 bits. Which statement is correct?
      Show the answer

      Answer: B. The file is smaller, and the original cannot be restored, because detail was permanently removed.

      Half the bits for each sample means about half the file size, and the finer levels cannot be got back. This is lossy compression.

      Stage: Apply

      Run-length encoding on a picture

      RLE also works on a row of pixels, with each pixel as a colour. The house from the images lesson is 8 pixels wide, with W for a white pixel and B for a black one.

      Think it through

      The first row of the house is WWWBBWWW. Write it as runs, using the count first.

      Show what happens

      3 whites, 2 blacks and 3 whites: 3W2B3W. The 8 pixels become 3 pairs of a count and a colour.

      The house, one row at a time
      RowPixelsRun-length encoded
      1WWWBBWWW3W2B3W
      2WWBBBBWW
      3WBBBBBBW
      4BBBBBBBB
      5WBBBBBBW
      6WBBWWBBW

        Show the completed table
        RowPixelsRun-length encoded
        1WWWBBWWW3W2B3W
        2WWBBBBWW2W4B2W
        3WBBBBBBW1W6B1W
        4BBBBBBBB8B
        5WBBBBBBW1W6B1W
        6WBBWWBBW1W2B2W2B1W

        Row 4 shrinks well, but row 6 has five runs, and its encoding (10 characters) is longer than its 8 pixels. On a small picture with so many changes of colour RLE saves little. It saves a lot when rows have long runs.

        Check your understanding

        A row of 8 pixels is stored as 2W1B1W3B1W. Which row of pixels is it? (W is white and B is black.)
        Show the answer

        Answer: B. WWBWBBBW

        2W is WW, 1B is B, 1W is W, 3B is BBB and 1W is W: WWBWBBBW, which is 2 + 1 + 1 + 3 + 1 = 8 pixels.

        Check your understanding

        A row of 64 pixels has 28 white pixels, then 8 black pixels, then 28 white pixels. Which is its run-length encoding?
        Show the answer

        Answer: A. 28W8B28W

        The row is three runs, 28W8B28W: six characters, in place of 64 pixels. This is how large areas of a single colour compress well.

        Stage: Explain

        Choosing lossy or lossless

        Think it through

        Would you accept a compressed copy of an essay in which a few letters had been removed to save space? Would you accept a compressed copy of a holiday photo with slightly fewer colours? Explain the difference.

        Show a model answer

        A missing letter can change the meaning of a text, so an essay needs lossless compression. A holiday photo with slightly fewer colours still looks like the same picture, so a lossy method, which saves much more space, may be acceptable. The choice depends on whether the lost data matters.

        Lossy or lossless?
        SituationSuitable method (lossy or lossless)
        A text document of an essaylossless
        A computer program file, where one changed instruction could stop it working
        A holiday photo for a web page that must load quickly
        A recording of a phone call, where the speech only needs to be understood
        A spreadsheet of exam marks

          Show the completed table
          SituationSuitable method (lossy or lossless)
          A text document of an essaylossless
          A computer program file, where one changed instruction could stop it workinglossless
          A holiday photo for a web page that must load quicklylossy
          A recording of a phone call, where the speech only needs to be understoodlossy
          A spreadsheet of exam markslossless

          Apply it

          A fictional bus app must send a route map to a phone over a slow connection. Maps are a picture with large areas of a single colour and thin lines. The lines must be exactly in the right places. Which method suits best, and why?
          Show the answer

          Answer: C. Lossless, such as RLE, because the lines must be exact and one-colour areas make long runs.

          The maps have long runs of one colour, so RLE shrinks them well, and RLE is lossless, so the thin lines stay exactly where they are. Lossy compression would risk blurring them.

          Apply it

          Maya says: “I reduced the sample rate of my recording to make the file smaller. When I decompress it, I will get my original recording back.” What is wrong with Maya’s reasoning?
          Show the answer

          Answer: A. Reducing the sample rate removes samples for good, so it is lossy and cannot be undone.

          Lowering the sample rate keeps fewer samples. Those that were discarded cannot be recovered, so the process is lossy, and only a lossless method can be reversed exactly.

          Go deeper Beyond the specification: other kinds of file, and real formats

          At A level you meet how different kinds of file can be compressed. A text file has to be compressed losslessly, as the essay showed: RLE helps only if there are long runs, so other lossless methods replace common patterns with short codes. A bitmap image can use RLE, which is lossless, or a lower resolution or colour depth, which are lossy. A vector graphic stores a list of shapes, which is already short, and can be compressed losslessly. A sound file can be compressed with a lower sample rate or sample resolution (lossy) or by a lossless method.

          Real formats choose their own methods. JPEG pictures and MP3 sound use lossy methods that remove detail that eyes and ears are unlikely to notice. PNG pictures, ZIP archives and FLAC sound are lossless.

          Stage: Consolidate

          Bring it together

          Think it through

          Without looking back, explain to a friend why compression is useful, and how run-length encoding differs from reducing an image’s colour depth.

          Show a model answer

          Compression makes a file smaller, so it needs less storage space and less bandwidth, and it is sent in a shorter time. Run-length encoding is lossless: it stores a repeated value and its count, and can be decoded back to exactly the original. Reducing the colour depth is lossy: it removes colour information for good, so the original cannot be restored.

          Check your understanding

          What is AAAAAABBBB after run-length encoding, writing the count first?
          Show the answer

          Answer: A. 6A4B

          AAAAAA is 6A and BBBB is 4B, so the result is 6A4B.

          • Compression makes a file smaller. That needs less storage space, less bandwidth, and gives a shorter transmission time.
          • Lossless compression loses no data permanently: the original can be rebuilt exactly. Run-length encoding (RLE) is an example: a run of identical values is stored once with its count (4A3B2C1D).
          • RLE works well on long runs, such as large areas of one colour, and badly when values keep changing: ABAB becomes twice as long.
          • Lossy compression permanently removes data, for example by reducing resolution, colour depth, sample rate or sample resolution. The file is smaller, and the original cannot be got back.
          • Use lossless where every detail must survive (text, programs). Use lossy where a small loss is acceptable for a much smaller file (photos, speech).

          Sources and scope

          • What this lesson is. The tenth lesson of the Data Representation module, written for this site. It teaches points 3 and 4 of Cambridge IGCSE Computer Science 1.3 (the purpose of compression, lossy and lossless methods, and run-length encoding) against the 2026 to 2028 syllabus (version 6). Its curriculum links are provisional: no link has been verified by the site owner. They show where the lesson may help with a course and imply no review or endorsement by any examination board.
          • Original material. Dalia’s bead pattern, the shared video, the bus app and Maya’s claim are fictional examples written for this lesson. The house is the one drawn in Representing Images. The numbers are chosen to divide cleanly.
          • Simplified on purpose. RLE is written with the count first; other books write the pair in the other order. The counts of an RLE file take space too, which is only mentioned. Other compression methods, and how a real lossy format decides what to remove, are left to the optional extension and to later study.