Homework 17: Shrinkage

Write a program that compresses data. You can choose to implement one of the existing popular algorithms, if you’d like, or you can try to invent your own.

If you invent your own, you may choose to tailor it to certain kinds of data (for example, sound, text, images, etc) or you may try to invent something that works well for a wide variety of data.

You should also write a decompressor.

A simple testcase (in pseudo-code) is:

while true:
    data   = random_bit_string(random_length)
    data'  = compress(data)
    data'' = decompress(data')
    
    assert( data == data'' )

which reasonably ensures that your compress function composed with your decompress function is the identity function.

Bring your solution to our September meeting.

Feel free to discuss the problem or any other topics you are interested in on our mailing list (accessible via our Meetup Group).