16 - Run Length Encoding

 1. What type of data compression technique is Run length encoding (RLE) ?
Note: The video on run length encoding is useful but it is not necessary for you to watch it to answer the question





 2. Read the definition of RLE (Wikipedia) and fill in the blanks
Definition of Run-length encoding(RLE)
Run-length encoding (RLE) is a very simple form 
of data compression in which runs of data 
(that is, sequences in which the same data value occurs
 in many consecutive data elements) are stored as a 
_____________________, rather than as the original run.

  code word, which always begins with 'x'

  run length encoding bits

  single data value and count

  sequence of numbers

 3. RLE depends on repeating patterns in the data to be compressed e.g. bitmap files often have:

  absolutely no areas with the same colour

  lots of areas with the same colour

  lots of areas with identical bit and binary sequences present in the display

  lots of areas with repeating text patterns

 4. Run length encoding looks for blocks of repeating data. This repeated data is called a …



  ascii bit


 5. Fill in the blanks for this example of RLE
Example of RLE
For example, consider a screen containing plain black text on a 
solid white background. There will be many long runs of white pixels 
in the blank space, and many short runs of black pixels within the text.
 A hypothetical scan line, with B representing a black pixel and W 
representing white, might read as follows: 
With a run-length encoding (RLE) data compression algorithm applied to 
the above hypothetical scan line, it can be rendered as follows: 


This can be interpreted as a sequence of _________________________________ 

  two Ws, two Bs, two Ws, etc

  twelve Ws, one B, twelve Ws, three Bs, etc..,

  None of the above

  fourteen Ws, four Bs, twelve W's, etc..

 6. Run-length encoding schemes were employed in the transmission of television signals as far back as 1967



 7. RLE compresses data by specifying the number of times a character of pixel repeats followed by ……

  the value of the meta data in the file

  the value of the character or pixel

  the no. of bytes in the whole file

  the no. of bits in the whole file

 8. The aim of RLE is to….

  exactly half the number of bits by one 'run' (run = four bits)

  double the number of bits

  reduce the no. of bits it takes to represent a set of data

  increase the number of bits it takes to represent a set of data

 9. Read the excerpt and fill in the blanks: The compressed version requires only __________
Example: aaaabbbbbbcddddd 
There are 16 characters in the example so 16 bytes 
(assuming ASCII is being used) 
are needed to store these characters in an uncompressed format:  

Example as ASCII: 97 97 97 97 98 98 98 98 98 98 99 100 100 100 100 100  

However, RLE can be used to store that same data using fewer bytes.  
There are four consecutive occurrences of the character ‘a’ followed 
by six consecutive occurrences of ‘b’, one ‘c’ and finally five 
consecutive occurrences of ‘d’.  This could be written as the following 
sequence of occurrence-character pairs: 

Run-length encoding for the above Example: (4,a) (6,b) (1,c) (5,d) 
If this text is then compressed using RLE we would end up with: 

04 97 06 98 01 99 05 100

The compressed version requires only __________
a reduction from the original 16 bytes.

  12 bytes

  15 bytes

  4 bytes

  8 bytes

 10. Text with very few repetitions will compress very well.



 11. The three main ways of using RLE on Bitmapped images are:

  bit level, byte level and pixel level RLE

  None of these options are valid

  computer level, person level or image level RLE

  binary level, hex level and ascii level RLE

 12. Looking at the example shown below fill in the blanks:
The original bitmap used 32 bits whereas the bit level RLE of the bitmap uses only _______ This compression works due to the relatively long sequences of consecutively-coloured pixels. 

  10 bits

  12 bits

  3 bits

  24 bits

 13. Read the example to answer the question. What is used to prevent negative compression?

  a single bit

  a double byte

  a single byte

  a flag byte

 14. Typically speaking, the longer the run lengths the better the compression
..and the shorter the run lengths, the less compression we achieve/



 15. In Pixel level RLE (fill in the blanks)
Each pixel is represented by multiple bytes, ie four bytes, 
for an RGB bitmap. Each pair would consist of a ___________________________ 
that represent the pixel colour. 

  single byte, followed by three run bytes

  single bit, followed by the three single bits

  run length byte, followed by the three bytes

  None of the above