As a warm up we're going to look at run
length encoding, which is actually an
effective method in many applications.
Simple method that's very effective. It's
based on the idea that it's very often the
case in a bit string that you have long
runs of repeated bits. So in this case,
there's a long run of zeros followed by a
medium length run of ones, another medium
length run of zeros, and then more ones.
So there's 40 bits but only switches from
zero to one in three places. And so what
you can do is rather than write out all
the bits. We can write counts to represent
alternating runs of zeroes and ones. A
very simple method. So in this case,
there's fifteen zeroes, seven ones, seven
zeroes and eleven ones. And, with four
bits to represent each one of these
counts, we can just write fifteen, seven,
seven, and eleven to get, instead of 40
bits, get down to sixteen bits. That's
effective, whether there's long runs of
zeroes and ones, in a bitstream. now, you
have to decide how many bits to use to
store the counts. it's not necessarily a
good idea to use, say, 32 bits. and maybe
four is too small. So, in our code, we use
eight bits. So that'll handle runs up to
256 bits. we used four in the example
above, but in a realistic thing, it's fine
to use eight. and then if we have longer
runs, then we have to figure out what to
do. if the run length is bigger than the
mass count, well, we can just intersperse
runs of length zero. And there's one way
to handle it, there's other ways to handle
it too. But this is a very simple scheme
that covers all the bases and can be a
very effective. and . For example,
consider a bit map representation of this
slide. There's huge long runs, saved with
black and white. There's huge long runs of
white that, depending on the resolution,
might be hundreds or 1000 bits, but could
be represented with just a few counts. and
so in many applications of bit maps of
texts and other things like that, this is
very effective and it's used in all kinds
of technologies like Jpeg and fax and
others. and it's very simple t o
implement. So this is our warmup data
compression algorithm that implements
run-length encoding. Actually we left the
compress for the book. this is just the
expand. so I'm given a bunch of counts.
how do I reproduce the original
uncompressed text string into . It's as
simple as that. So log R is the number of
bits per count. and so basically what we
do is read log R bits at a time into an
end, whatever the value is, so we put that
into the end run. So, that's a number
between zero and 256, which is the maximum
you can get in eight bits. and then,
starting with zero the first count. That's
the number of zeroes we need to write, so
we just write them one, one bit at a time.
Zero at one bit at a time, and then we
flip the bit to make it one. and read the
next count, and now we, we write out that
many 1s and so forth. So this is a ten
line program that does, expansion for, run
length and coding. and you can, think
about it or look at the book, for, how to
do, compression. it's just as simple. so
this is just the, an example of the
effectiveness of, learning some coding
for, one letter, the letter Q, in a, in a
typical black and white scheme doing. Even
for a single letter, there's, lots of,
redundancy, lots of runs of 0s. so with a
relatively small, number of counts. we
can, represent a, a bitmap. and this is
the hard case. actually, most of a printed
page is all this blank space, as I said.
so, Typically. If you just don't compress
at all and you have an eight and a half by
eleven piece of paper with three hundred
pixels per inch, that'd be eight million
bits. But most of those are white, and
typically with run length and coding, you
can get substantial savings simply by
basically counting the white bits. And
even when there's letters involved, you
can get, say maybe there's only three
thousand characters. That's another
example. If it's all text then maybe the
text itself is a great way to compress it.
or the program or the document processor
that produced the text, but now we're
starting to get into undecidabi lity
issues. So lets think more in terms of a,
a page that has a, an image, a drawing,
and some text and so forth. so it makes
sense to start with a bitmap and then use
as few bits a possible. And then run
length encoding's going to be very
effective. that's our warm up case for
data compression.