Lossless compression (1.3.1 b)

Question 1

What is dictionary encoding?

Answer 1

replaces common phrases with a reference to the original data
e.g Romeo_Romeo_where_art_tho_Romeo = Romeo_ _where_art_tho

Question 2

What is run length encoding?

Answer 2

turns runs of identical data into a single value and the number of repetitions
e.g AAABBBBCCCCDDBBBBAAA =3A4B4C2D4B3A

Question 3

Run length encoding

Answer 3

simplest compression method
also works with images

Question 4

Run length encoding limits

Answer 4

does not work with files of natural origin
englishrarely features words with lots of repeated character
images often don’t have regions of identical colour (especially photographs)

Question 5

Dictionary encoding

Answer 5

replace repeated values with pointers to the original data
I am Sam Sam I am
token | data
———|———- 231123
1 | Sam
2 | I
3 | am
aren’t limited to individual words or characters

Question 6

Dictionary limitations

Answer 6

dictionary and compressed file can have a larger file size than the uncompressed file
need for a dictionary and pointers is a major overhead
if the file doesn’t have sections that repeat the efficiency reduces

Question 7

Real life lossless

Answer 7

often combine multiple compression approaches
e.g ZIP files use both dictionary encoding and variable length encoding (Huffman encoding)