Preview

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

  Lossless

  Minty

  Lossy

  Uncontrolled

 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.

  sequence of numbers

  single data value and count

  run length encoding bits

  code word, which always begins with 'x'

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

  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

  absolutely no areas with the same colour

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

  repeato

  ascii bit

  repeater

  run

 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: 
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW 
With a run-length encoding (RLE) data compression algorithm applied to 
the above hypothetical scan line, it can be rendered as follows: 

12W1B12W3B24W1B14W 

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

  False

  True

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

  the no. of bytes in the whole file

  the no. of bits in the whole file

  the value of the meta data in the file

  the value of the character or pixel

 8. The aim of RLE is to….

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

  double the number of bits

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

  reduce the no. 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.
 

  4 bytes

  8 bytes

  15 bytes

  12 bytes

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

  FALSE

  TRUE

 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. 
datarep_rle_q1.png

  12 bits

  3 bits

  10 bits

  24 bits

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

  a double byte

  a single bit

  a flag byte

  a single byte

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

  FALSE

  TRUE

 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. 

  None of the above

  single bit, followed by the three single bits

  run length byte, followed by the three bytes

  single byte, followed by three run bytes