Today we're going to talk about data compression. Now this is a family of
algorithms that, everyone uses. and it's based on, many of the classical ideas,
that we've covered in terms of, implementing basic algorithms. we'll start
with a introduction, just what data compression is. So the idea is to reduce
the size of a file. really for two primary reasons. One is to save some space when
storing it. and the other is to save some time with transmitting it. And often
having significant savings is not too difficult because most files have, plenty
of redundancy. but of course we're interested in efficient algorithms that
can guess, get the best savings possible. so, you might think that with the way that
technology, has been improving over recent years. That we wouldn't really need
compression, we can just buy a bigger, faster disk. but the problem with that
idea is, that even though. Moore's law tells us that we're going to get, twice as
much space every one and a half to two years. It's also the case that we,
whatever space we have, we're going to want to fill it up, with, better, higher
quality, data. so you want a higher resolution movie if you get more space.
And if we can remove redundancy, you're always going to want to do that. So it's a
cheap way to, save space, that allows us to do more with the space that we have
available. this is a report last year on big data. Every day we could create 2.5
quintillion bites of data, so much that 90 percent of the data in the world today has
been created in the last two years alone. if we can use data compression to cut that
amount of data in half then that's all the data in the world created in a year. So
this is a very interesting topic to consider from an algorithmic point of
view. Because the basic concepts some of them date back to the 1950's. when it was
extremely important to save time when transmitting information cuz of, or space.
because it was so costly. but some of the best technology, algorithmic technology,
has devel-, been developed recently, and much of it uses, the data structures that
we've considered for other applications. And we'll see that as we get into the
topic. so, just specific applications that, maybe are familiar for file
compression. All file systems and, and disks have built-in, compression
technologies. Such as, as zip, and b-zip and many others of similar type.
Technologies. And the multimedia, everybody's familiar with, the JPEG and
MP3 and MPEG, and all those sorts of things for images, sound and video. Those
are all about data compression. and for communication, now, that's, what has, what
enabled, fax, and also enables new technologies, like Skype, the ability to,
reduce the, amount of data that you actually need to send. for any kind of
technology, is gonna, help, improve things, and improve the quality of what
you can do. . Also, the types of massive amounts of data that, people are saving,
nowadays. Google and Facebook and other, , other web giants are saving lots of data.
And they're going to be able to save more, because of data compression. now from a
theoretical point of view the type of compression that we're going to consider,
lossless compression is very simple conceptually. So we think of a, we talk
about a bitstream rema, everything can be encoded in bits, so we might as well just
consider a, a stream of bits that we want to compress and we'll call that B. In a
data compression algorithm it's going to be a black box that goes ahead and takes
those bits and produces a compressed version, which is many fewer bits. and I
will call that C of B. But we hope that it's many fewer bits. and so that's what
we save or we send, but then we need a companion algorithm, an expansion
algorithm, that takes C of B and produces B back. That's lossless compression. We
want to get back precisely the same bits that we put in. And that's very important,
in many applications. It's not so important in some applications, like
images and video where you're happy with an approximation and the original a bit
strained but we're not going to consider that kind of algorithm. We're just going
to consider a lossless compression, where maybe it's a program or that you can't
afford to lose a single bit. Now it turns out that where we talk about in terms of
evaluating our algorithms, it's what's the compression ratio. Now, we also care about
efficiency. We don't want to spend a lot of time creating CFB, but the compression
ratio is the measure that we use to compare algorithms; and we're interested
in knowing the percentage of bits, a percentage of the size would be that we're
able to save. And surprisingly even for natural languages texts we can get, 50 to
75% or even better compression ratios. Now just in the larger context, data
compression has been with us since antiquity. it's always better to try to
express what you're doing concisely. Mathematical notation is an example of
that, or number systems, or even natural languages. Communications Technology has
evolved; it definitely has to do with data compression from braille to morse code to
the telephone system. Those are all ways of trying to, they depend on, trying to
achieve good data compression. In a modern life, everybody's trying to get pictures
or movies on their devices, and it's definitely enabled by good data
compression. So, something to think about, what role data compression is going to
play in the future. But, it's really hard to see it going away. Number one, it is
effective. Number two, it is not that difficult to implement, and it's in
software. So, you don't have to buy a bigger disk to have a good compression
algorithm in many situations. here's a simple example that sprung up just in
recent years. so we've talked about in other applications that genome is a string
over a four letter alphabet. and the string might be huge. It might be billions
of letters. And so, and there might, and there might be lots of them, for different
individuals and different species. so the huge genome data base is out there with
these very long strings of the alphabet A, C, T and G. Now, the standard way to store
them in standard programming language, standard computers, is to use ascii, and
there's eight bits per character, and so if you have an n bit genome, genomic
string, it'll be eight n bits. If it's a billion, characters, it's eight billion
bits. but just look at the problem. really there's only four characters. You can get
by with just two bits per character. So, that's one quarter the storage. if you
spent X dollars on this space to store your stuff, you could spend X over $four.
And that might be a significant number. And, the fact in general, if you know you
have a small alphabet you can get a savings in this way. This seems very
obvious and straight forward, but it's amazingly true that in the 1990's when
generally, data basis started to emerge there were four times too big. They used
ASCII then, didn't think to use this trivial coding that could have cut costs
by one fourth. so again, if it's so easy to do, why not do it? If you can cut your
cost by a factor of four. And where else, would you give up, reducing cost by a
factor of four so easily. So that's why we're interested in data compression. Now
we're going to need some tools that are slightly different from the tools that
we've been using in order to write effective data compression algorithms. And
so we've got , extensions to our standard in and standard out libraries that work
with bits. so, these are what we want to, what the methods that we're going to use
to write bits to standard output and standard input. So, these bit streams are
different than a standard in, standard out. They're binary standard in, binary
standard out. And so, what we can do is read Boolean, which is just read one bit,
or to save some processing, we can read eight bits of data and put it in a care.
Or in general, R bits, where R is less than eight, and put it into a care value.
And we can also, if we want, put it into nth values long and boule in a similar
methods. And we don't have to read all the bits if we've got some. , a scheme where
we only wanna use a certain number of them. but the idea is that, we can read a
variable number of bits, and get'em ready for processing easily, by putting them in
one of Java's, primitive types. And conversely, we have binary standard out,
where we can write a bit. or we can write, eight bits, or we can write any number of
bits from a care value or from an int value, or any others. So this allows us to
take in bit streams and to write out bit streams and takes care of all the encoding
between Java primitive types and bit streams. And it's not too difficult to use
and it's very intuitive. And you'll see when we come to code. just to, give an
example of how just having this, can save space. this is just a simple example of
representing a date. So if you, represent the date, 12/31/1999, as an ASCII
character string, in Java. then, when you write out the string, you've got one, two,
three, four, five, six, seven, eight, nine, ten characters. in each one of the
characters is eight bits so that's a total of 80 bits. so the standard ASCII encoding
is to just look up the ASCII of the one and that's 00110001 and then the two and
so forth. So in the slash 31 and so forth. So for each character we've got eight bits
and we put them up and that's 80 bits. If it was Unicode there would be even more
bits. So that's one way that you might consider representing a date with bits.
Now if we represent it as three nth values, that's not so effective a way to
do it. The month is a nth, the day is an nth and the year's an nth and each one of
those is going to be 32 bits. and that's the total of 96 bits though that's, that's
actually even worse. by the month in all these things are within small ranges. So,
with binary standard out we can say, well, we're learning right out the right most
four bits of the month end cuz that give us a number between zero and sixteen and
months between one and twelve. And the five bits of the day. And you input that
again, and that's, between zero and 31. And that's going to cover any possible
day. and then twelve bits for the year. And if we do that .
Then we have a total of 21 bits. and there's a little bit of extra at the end,
because our byte streams, our bits really are implemented, reasonably in most
situations as byte streams. so they're going to get carved into chunks of size,
eight by, hardware or, their drivers. And so, we always round up to the nearest
multiple of eight to get the proper alignment on bytes. but that's still
pretty, significant savings from 80 to 24, just by having, the ability to, write out
portions of, INT values. And if we had a billion dates, then that would be a huge
cost savings that would translate to dollars, as well. the other thing, that we
do to give some visual impression of our effectiveness of our compression
algorithms particularly in the text, is to look at different ways to examine the
contents of a bit-stream. so we have on the book site A binary dump program that,
prints out, the bits, sixteen bits at a time, rows of sixteen bits at a time. And
then the total number of bits. so, this file aver.text is, a standard character
stream. so everything's encoded with, eight bits. and so there's twelve
characters and it's 96 bits. And you can see what all the bits are. Or, sometimes
it's convenient to use a hex dumpler. We just read the hex digits considering the
bits, four bits at a time. And so those 96 bits are twelve bytes, or 24 hex digits.
And we print it out so that we can see them. Another thing that's useful
sometimes for big files is to look at the bits as a pitcher where we just do a. Give
the width and the height of a pixel window and just map the bits to white squares and
black squares. So this is the same aver.text. It's just that you can see that
they all start with zero one much more easily. This visual representation
sometimes gives an interesting perspective into what a compressed or what a bunch of
bits looks like. So, this is just the hex to ASCII conversion table that, that if
you are not familiar with it it's a quick way to find the hexadecimal corresponding
to an ASCII character. So, you look up sa y R in the table and that's in row five
and column two. So it's 52. So this is a 52 for the R in Abracadabra. And so those
are the basic tools, that we are going to use when we talk about compression
algorithms. Now there's one thing that's, really important to think about. and
that's the idea that, you cannot have a compression algorithm that can compress
every file. despite the fact that, somebody has, patented that. And, and
there's a claim that, methods for data compression is capable of compressing all
files. and, also, this, this is another, thing that came out of Slash Dot a few
years ago, where a company had announced a breakthrough in data compression that does
a 100 to one losses compression of random data. And unfortunately, they do say, if
this is true, our then withdrawals got a lot smaller. Cause, there's no way that is
true, and lets look at why that's the case. Proposition is no algorithm can
compress every bit string. Here's one easy way to prove it, not by contradiction. So,
let's suppose that we have an algorithm MUI that can go ahead and compress every
possible bit string. So we take a bit string and we use our algorithm to
compress it, to get a smaller bit string. But since our algorithm can compress every
bit string. Why not use it on that one? Use it on that one, you get a smaller one.
Then we keep going. Since it's a compress, can compress every bit string, eventually
we get down to a bit string of size one. And since it can compress that one, it
gets down to zero. So if you can have an algorithm that compresses every bit
string, it means that you can compress all bit strings to zero bits, and that's
absurd. So that's a proof by contradiction. Or another way to see the
same thing is just by counting. So let's say you've got an algorithm that can
compress all 1000 bit strings, just to pick a number. Now there's a lot of 1000
bit strings. There's two^1000 of them. but how many of those, can be encoded with 99,
999 bits or fewer. Well. Just one plus two plus four, and the powers of two up to
two, and out to the 99, 999. Or, like less than 500, that's. so that's way fewer than
the total number of, of possible bit strings. Well, it says it's one if you add
up the sum that's 2,501. So, there's one that can't be compressed. So, that's it.
So, if you want to say do fewer bits, you have much worse problem. only one out of
every two forty ninth can be encoded with less than 500 bits. It's just the smaller
number of git, bits gives you way number, way fewer possible bit strings and You
have to, be able to get your original bit string back. So, the smaller number of
bits gives you, a limit on the number of, bit strings that you can possibly
compress. so, we can't have universal data compression. And if you want to convince
yourself of that, now just try running your favorite compression algorithm on the
, result of what it produces. Say for a photo most good compression algorithms
will figure out that you're doing that, and just give you the same file back. So
at least it won't make it get larger but there's plenty of, of methods out there
that will make your file larger. there's another kind of basic idea. and, and that
is that there's no way to find the best way to compress a file. And if you think
about it, it can be extremely complicated. This is just an example that illustrates
the point. But it's also a relevant example, cuz it applies to so much of the
data that we deal with. So at the top is a picture dump of a million bit file. So
that's a million bits and it's, those are random bits. Well they're not random,
they're pseudorandom. what do I mean, pseudorandom? Well we talked about that.
they're generated by a program. And, this is a Java program that uses a pseudo
random number generator to generate bits. And, that's where those bits came from.
But if you think about it, this program is representation of those million bits. It's
only a couple of dozen characters, so, you know, if you want to find the optimal way
to compress those bits, one of the things you would have to consider is this program
T hat's a pretty compact way to represent a million bit. And, if you think about it
so much of the data that's out there actually was created by a program so,
compression amounts to finding the program that creates, created the data. And,
that's obviously a pretty difficult problem in fact it's known that it's
undecideable. So, let's not think that we can find the best possible compression
algorithm. and the other point that I want to finish with in the introduction is, to
realize that when we're talking about, compressing, say English language, it's
amazing to see that actually there's a lot of, redundancy in the English language.
and so this is, a, . A perturbed version of an English language paragraph that
shows that you can change letters and even delete letters and still figure out what
it says. and actually at the end, it's you really need the first and last two
letters, in a lot of situations to, really, figure out readability. so, there,
there is a lot of freedom, because there's so much redundancy. And since there's so
much re, redundancy, we can actually do, really well on, on compressing English
language texts, for example. So that's an introduction to data compression and we'll
take a look at algorithms next.