AP CS Principal : 2.2 Data Compression

Lossless text compression

Which sequences could be replaced to compress the text?

Choose all answers that apply:

• am

• like

• you

• sam

• eggs

run-length encoding (RLE)

Here's the second row of the bitmap for the heart icon:

0011110001111000

How would that row be represented in RLE?

Choose 1 answer

• 0,2,5,3,5,3

• 0,2,5,4,5,3

• 2,4,3,4,3

• 0,2,5,3,5,3

• • 0,2,4,3,4,3

RLE decompression

The following is a compression of a 6x6 black and white icon, using RLE

2,2,2

2,2,2

0,6

0,6

2,2,2

2,2,2

What mathematical symbol does that icon resemble?

• +

• -

• /

• X

Lossless bit compression : Huffman coding algorithm

Decode the following bits using the optimized binary codes.

111001

• • tgtct

• • tttct

• • ttcta

• • ttcat

Compression algorithms vary in how much they can reduce the size of an image.

Which of the following would likely be the easiest to compress?

Choose 1 answer:

• 
• 
• 
• 

Byte pair encoding is a compression algorithm that replaces repeated pairs of characters in a string with a character that isn't in the data, and creates a table of replacement mappings.

Here's a quote from Dr. Seuss:

"Think left and think right and think low and think high. Oh, the thinks you can think up if only you try!"

Which of the following character pairs would the algorithm replace?

Choose 2 answers:

• nl

• ft

• th

• in

Tess is creating an alarm clock using an LCD (liquid-crystal display) that looks like in the picture:

Each digit will be 5 pixels wide and 7 pixels tall. She decides to save space by storing the pixels for each digit using run-length encoding (RLE).

RLE is a data compression technique that replaces "runs" (sequences of bits with the same value) with a number representing the length of the run.

Here's the RLE for one of the digits:

1,3,1

0,1,3,1

0,1,3,1

1,3,1

0,1,3,1

0,1,3,1

1,3,1

• 9

• 0

• 8

• 3

Consider these two files:

• A 1-minute video of a cat pouncing ferociously on a twisty tie.

• A download of "The Lion King", a 1.5-hour animated film

Is it possible for "The Lion King" to have a smaller file size than the shorter cat video?

• Choose 1 answer:

• • Yes, as long as "The Lion King" video is compressed with an open non-patented standard.

• • Yes, if "The Lion King" video is compressed with a lossy compression algorithm.

• • No, "The Lion King" video will always take up more space than the 1-minute video.

• • Yes, but only if "The Lion King" video is produced by a major company like Disney.

Pixar is a company that creates a huge amount of images, audio recordings, and videos, and they need to decide what compression algorithms to use on all those files.

When would Pixar most likely use lossless compression?

Choose 1 answer:

• • (Choice B)  

    When saving the videos of film trailers for uploading to YouTube.

• • When saving images of the characters for the film website.

• • When saving audio clips to embed in stuffed animals, like Buzz Lightyear's "To Infinity and Beyond!"

• • When saving the rendered 3D images that will become the film.

Tom is recording an album of songs using a digital audio recording application, and he wants the recordings to be high quality.

Which advice will best help him to achieve his goal?

Choose 1 answer:

• • He should save the file on a USB drive, not his internal hard drive.

• • He should add metadata to the file with the title, artist, and genre.

• • He should save the file using an open standard.

• • He should save the audio using a lossy compression algorithm at high quality setting.

• • He should save the audio using a lossless compression algorithm.