Intro to the Text Compression Widget Computer Science Principles
(Aloe, Singer Songwriter): My name is Aloe Blacc.
I'm a singer, songwriter, and entertainer.
When it became more and more important for artists to have a presence on the Internet
I quickly developed the skill to build a website, get online, use my knowledge of coding to
make it so that people could learn more about our music.
Every bit of data or information can be stored digitally.
Whether it's numbers, text, pictures, or video all of it can be represented digitally.
That means, the information can be represented by electrical signals that are on or off,
or as ones and zeros so to speak.
Representing information in 1s and 0s can take up a lot of space.
For example, if you wanted to store a 3 minute song digitally, it would take up over 30MB
of space.
A 1 hour HD video would take 800GB.
In the real world, digital information is compressed to take up less space.
A 30MB song can be compressed down to 3 MB.
An hour long video can be compressed from 800GB down to just 1GB.
Sometimes compression is lossy, which means that to save some space some of the information
is thrown away.
For example, an image can be compressed to a lower resolution to lose some detail.
Lossy compression is useful because in many cases the human eye or ear can't even notice
the details that are being lost.
When you compress data without losing any details, that's called lossless compression.
This means the compressed data can be decompressed back into the exact original.
One way of doing lossless compression is to find patterns in the data you're trying to
compress.
As an extreme example, imagine a book about dogs with hundreds of pages using only 1 word.
Each page just says dog.
(repeats) Dog dog dog dog, over and over a million times.
Instead of writing it all out, you can just store the pattern dog x 1 million.
Now that's a silly example, but let's look at a more real example.
Instead of a book, imagine the lyrics of a song.
If a single word or phrase is repeated a lot, you can store that once and then re-use it
without repeating the data.
(Bemnet, computer science student): Let's see how this works with a simple text compression
widget.
This widget lets you experiment with compressing text.
You want to represent the original text with as few bytes as possible.
The widget lets you try compressing different ways and see it as it happens.
Let's see how it works!
The widget shows you some text to compress.
In this example, lyrics to one of Aloe Blacc's songs.
In the dictionary area, you can type patterns you see in the text.
For now, let's just look for words that repeat.
As you type in the dictionary area, a single symbol will be substituted in the main text
area.
In the example here you can see each occurrence of the words "I was" has been replaced with
the symbol of the sun.
And the word "I'm" has been replaced with an umbrella.
If you sent the compressed version of the lyrics to someone you'd also have to send
along the dictionary so that they can reconstruct the original text.
The question is, is the total number of bytes in the compressed text plus the bytes in the
dictionary less than the number of bytes in the original text?
The answer is "Yes" for our current example.
And the widget shows you how it's calculated.
We assume that every character that needs to be sent takes 1 byte.
So the display shows the compressed version of the lyrics with the symbols substituted
in it has 216 bytes or characters.
It also shows the number of bytes in the dictionary as 10.
This is to store the words "I was" and "I'm."
Also the symbols that represent those patterns.
This gives us the total of 226 bytes.
We can see that the original text had 240 characters (or bytes.)
So we've reduced the bytes needed to represent the song by 14 bytes.
Or, 5.8%. Not a bad start!
Looking for words that repeat is a good start.
But you can look for other patterns.
Sometimes a repeating pattern can be a sub part of a word or many words.
Here is where it really gets cool.
You can find patterns that include dictionary symbols you've just made.
For example, we've replaced the words "I was" with the sun symbol.
But now you can also see a new pattern "Didn't know [sun symbol] lost" You can type this
in the dictionary too.
As a side note, to enter the sun symbol you need to copy and paste it unless your keyboard
has a sun on it.
With that little change, we're now up to 26% compression.
Try it yourself and see if you can do better!
The repetition in a song lyric or poem is obvious.
But really, any form of information can have repetition or patterns in it.
They're just not as obvious.
For example, an outdoors photo can have a blue sky.
Instead of storing every single blue pixel, that can be compressed.
With the amount of information that's digitized and sent around the Internet everyday, there
are much fancier ways to compress the data.
Data compression is now built into how every picture, song, or movie is stored.
And almost every web page you visit is compressed as it's sent to your device.
All these compression algorithms have one thing in common: they all aim to represent
the information in the smallest format possible, in a way that can be decompressed to reconstruct
the original or at least something close to it.