Preview

20 - Run length Encoding

 1. What type of data compression technique is Run length encoding (RLE) ?

  Lossless

  Minty

  Uncontrolled

  Lossy

 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

  code word, which always begins with 'x'

  run length encoding bits

 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 identical bit and binary sequences present in the display

  lots of areas with the same colour

  lots of areas with repeating text patterns

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

  run

  ascii bit

  repeater

  repeato

 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 _________________________________ 

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

  two Ws, two Bs, two Ws, etc

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

  None of the above

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

  True

  False

 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 no. of bytes in the whole file

  the no. of bits in the whole file

  the value of the character or pixel

 8. The aim of RLE is to….

  double the number of bits

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

  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.
 

  8 bytes

  15 bytes

  12 bytes

  4 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

  binary level, hex level and ascii level RLE

  None of these options are valid

  computer level, person level or image level RLE

 12. Looking at the example shown below fill in the blanks:
datarep_rle_q1.png

  10 bits

  3 bits

  12 bits

  24 bits

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

  a single bit

  a double byte

  a flag byte

  a single byte

 14. Typically speaking, the longer the run lengths the better the compression

  TRUE

  FALSE

 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

  None of the above

  run length byte, followed by the three bytes