CompSci//Media Arts - Compression, p2

CompSci//Media Arts

Computer Science 1

Compression, p2

Today's Goal

Deeper understanding of Compression

Completed

Encryption vs Encoding
Cryptography in History
Revisit Info Theory Concept
About Control Flow
Finish our Caesar Cipher

Today

More on Compression

Upcoming

Compression
Quiz eventually

A Bit Deeper

Let's learn more about how compression actually works inside and within our computer systems, starting with a bit of a refresher on computer files themselves.

pbs-p1.mp4

Let's pause for a moment there.

When we devise a way to compress something, we are creating an algorithm.

Just like we saw with the Caesar cipher, there are a variety of ways to do the same thing.

Not all compression algorithms are equal. Some do a better job than others. Some are designed for specific types of files.

pbs-p2.mp4

Part 2:

Let's write a bit of Python

Write a program that'll compress a string of given letters.

For each group of consecutive repeating letters, first record the letter itself, then record the number of times the letter is present. This should result in a compression scheme that is lossless.

Example 1:

Input: "aabbccc"

Output: "a2b2c3"

Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3". This example only saves one byte of data.

Example 2:

Input: "a"

Output: "a1"

Explanation: The only group is "a". The 'compressed' output is actually larger than the input in this example.

Example 3:

Input: "abbbbbbbbbbbb"

Output: "a1b12"

Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "a1b12". Even though a is stored in an ineffecient manner, this encoding scheme is still beneficial overall, as the original string was 13 characters long. Overall, we saved 7 characters.

Before we actually start programming, let's briefly discuss how I'm thinking about the logic of this program.

Now that we've done that, let's try programming it.

In a document for today, include screenshots showing you were
able to get all 3 test cases (the examples) to produce the correct output.

Page updated

Report abuse