Run Length Encoding & Dictionary Coding (OCR A Level Computer Science)

Exam Tip

• RLE and Dictionary Coding serve different needs and have their advantages and disadvantages

• RLE: More effective when data has lots of repetition

• Dictionary Coding: More versatile but may require more computational resources

Worked Example

A survey focuses on the kinds of vehicles travelling on a motorway. For each vehicle that passes, a letter is noted:

• For a car, 'C' is entered.

• For a motorbike, 'M' is entered.

• For a lorry, 'L' is entered.

• For any other vehicle, 'O' is entered.

It's decided to compress the data generated.

Run Length Encoding has compressed the following sequence:

3C3M4C

Show the result of decompressing the sequence.

[2]

How to answer this question:
Run Length Encoding (RLE) shows the number of consecutive occurrences of a character in a sequence. To decompress, repeat each character the number of times indicated by the preceding number.

Answer:

Example answer that gets full marks:
CCCMMMCCCC

Worked Example

The following sequence represents the raw data collected during the survey:
CCCCOLLLCCCCCMOCCCCC

Show the result of compressing the sequence.

[2]

How to answer this question:
To compress using RLE, count consecutive occurrences of each character and append the count before the character itself.

Answer:

Example answer that gets full marks:
4C1O3L5C1M1O5C

Worked Example

Write pseudocode for the function "longest", which takes in a string of characters as an argument and returns an integer representing the longest continuous sequence of 'C's.

[6]

How to answer this question
Write pseudocode for a function that iterates through the string, counting continuous sequences of 'C's and keeping track of the longest such sequence.

For example, in ABCCCBAACC the longest consecutive string of 'C's is 3.

Answer:

Example answer that gets full marks

How this answer might look in pseudocode:

Function longest(s: String) -> Integer:
   max_count = 0
   current_count = 0
    
    For each character in s:
        If char equals 'C':
            Increment current_count by 1
            If current_count > max_count:
                Set max_count to current_count
        Else:
            Set current_count to 0
    
    Return max_count

How this answer might look in Python:

def longest(s): 
      max_count = 0
      current_count = 0
      
      for char in s:
            if char == 'C':
                  current_count += 1
            else:
                  current_count = 0
                  if current_count > max_count:
                        max_count = current_count
      
      return max_count

How this answer might look in Java:

public class Main {
    public static void main(String[] args) {
        System.out.println(longest("ABCACCCCCABAC"));  // Output should be 5
    }

    public static int longest(String s) {
        int maxCount = 0;
        int currentCount = 0;

        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);

            if (currentChar == 'C') {
                currentCount++;
                if (currentCount > maxCount) {
                    maxCount = currentCount;
                }
            } else {
                currentCount = 0;
            }
        }

        return maxCount;
    }
}

Acceptable answers you could have given instead:
You could use different variable names or loop structures, but the logic should be the same to get full marks.