A text file contains the same phrase many times.
Explain how lossless compression can reduce the size of this text file.
Mark scheme
Award up to two marks for a linked explanation such as:
- The repeated phrase is stored once (1) along with a count of the number of times it occurs (1)
- The repeated phrase is replaced by a shorter code/reference (1) and the original phrase is held in a dictionary/lookup table (1)
- A shorter code is used in place of each repeated phrase (1) so fewer characters/bits are needed to store the file (1)
- Groups of repeated characters are replaced by a count and a single value (1) so the file stores less data (1)
For both marks, the expansion must follow/associate with the statement.
Allow naming of a suitable method, e.g. run-length encoding or dictionary coding, in place of a description of that method.
Award the marks once only where the same method (run-length encoding) is described more than once.
Do not accept 'it makes the file smaller' on its own without a method of compression.
Do not accept answers that describe lossy compression, e.g. that data/detail is removed or lost permanently, because lossless compression keeps all of the original data.
Do not accept 'it removes the repeated words/duplicates' on its own, as this suggests data is lost; credit only where the answer says the phrase is stored once with a count or code.
Example answers and how they were marked
The repeated phrase is stored once and a count of how many times it occurs is stored with it.
Why: Phrase stored once (1) with the linked reason that a count of the repeats is also stored (1).
It finds the repeated patterns in the text and replaces them with a shorter code.
Why: Shorter code used in place of the repeated phrase (1) but no linked reason about fewer characters/bits being stored.
It permanently removes the repeated words so there is less data to store.
Why: Describes lossy compression; the Do not accept line rejects removal of data because lossless compression keeps all of the original data.