Exercises: Data Compression

Define lossless compression and lossy compression in your own words. Then classify each as lossless or lossy: (i) a ZIP file of a spreadsheet, (ii) an MP3 version of a song, (iii) a JPEG photo saved at low quality.

A 12 MB file is compressed to 3 MB.

1. a) By what percentage was the file size reduced?

1. b) Can you tell from these numbers alone whether the compression was lossless or lossy? Explain.

A law office wants to compress a scanned contract before emailing it, and every character must stay exactly the same. Should the office use lossless or lossy compression? Explain your choice in two or three sentences.

Run-length encoding replaces repeated characters with a count followed by the character. For example, AAA becomes 3A.

1. a) Encode the string AAAABBBCCD. How many characters does the original have, and how many does the encoded version have?

1. b) Decode 3X5Y1Z.

1. c) Is run-length encoding lossless or lossy? Justify your answer.

Olivia has a phone plan with a monthly data cap of 6,000 MB. One hour of video streams at 1,200 MB at high quality and 450 MB at a lossy "data saver" quality.

1. a) How many full hours of video can she watch each month at each quality?

1. b) Describe one trade-off she makes by choosing data saver quality.

Sofia has a 24 MB original photo. The photo-editing app offers these lossy export settings:

1. a) Compute the percent reduction in file size for each setting, rounded to the nearest tenth of a percent.

1. b) Which setting would you choose for a thumbnail on a website? Which would you keep for printing a poster later? Explain, and say what Sofia should do with the original file.

A message has 1,000 characters, and each character is one of four letters: A, B, C, or D. The letters appear with these frequencies: A 50%, B 25%, C 12.5%, D 12.5%.

1. a) How many bits does the message need if each character is stored with 8 bits? With a fixed 2 bits per character?

1. b) A variable-length code uses A = 0, B = 10, C = 110, D = 111. Compute the average number of bits per character and the total bits for the 1,000-character message.

1. c) Is the variable-length code lossless or lossy? Explain why no information is lost, and explain why a frequent letter should get a shorter code.

A music streaming service stores each song in two versions: a lossless version of 40 MB and a lossy version of 4 MB. A user's library has 500 songs.

1. a) Compute the total storage needed for the library in each version, in GB. Use $1\text{ GB} = 1{,}000\text{ MB}$.

1. b) Recommend a version for (i) a casual listener who uses earbuds on the school bus and has a phone with limited storage, and (ii) a sound engineer who archives recordings to remix them later. Justify each choice using the size and quality trade-off.

1. c) Explain why converting a lossy file back to lossless format does not restore the original quality.