Run-Length Coding

Loading...

En provenance du cours de Princeton University

Algorithms, Part II

420 notes

Princeton University

Algorithms, Part II

420 notes

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms.

À partir de la leçon

Data Compression

We study and implement several classic data compression schemes, including run-length coding, Huffman compression, and LZW compression. We develop efficient implementations from first principles using a Java library for manipulating binary data that we developed for this purpose, based on priority queue and symbol table implementations from earlier lectures.

Introduction to Data Compression22:27

Run-Length Coding5:59

Huffman Compression24:14

LZW Compression27:33

Rencontrer les enseignants

Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Computer Science
Kevin Wayne
Senior Lecturer
Computer Science

As a warm up, we're going to look at run-length encoding, which is actually

an effective method in many applications, a simple method that's very effective.

And it's based on the idea that it's very often the case in

a bitstream that you have long runs of repeated bits.

So in this case there's a long run of 0s followed by a medium-length run of 1s,

another medium-length run of 0s, and then more 1s.

So there's 40 bits, but only switches from 0 to 1 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 0s than 1s, very simple method.

So in this case, there's 15 0s, 7 1s, 7 0s, and 11 1s.

And with 4 bits to represent each one of these counts, we can just write 15,

7, 7 and 11, to get instead of 40 bits, get down to 16 bits.

That's effective when there's long runs of 0s and 1s in a bitstream.

Now, I have to decide how many bits to use to store the counts.

It's not necessarily a good idea to use a 32 bits and maybe 4 is too small.

So, in our code we use 8 bits, so that'll handle runs up to 256 bits.

We used 4 in the example above, but in a realistic thing it's fine to use 8.

And then if we have longer runs, then we have to figure out what to do.

If the run-length's bigger than the max count,

well, we can just intersperse runs of length 0.

And there's one way to handle it.

But there's other ways to handle it too, but this is the very simple scheme

that covers all the bases and can be very effective.

[COUGH] For example,

consider a bit map representation of this slide.

There's huge long runs, say, with black and white, there's huge

long runs of white that depending on the resolution might

be hundreds or a thousand bits but could be represented with just a few counts.

And so many applications of bitmaps of text and other things like that, this is

very effective in its use in all kind of technologies like JPEG and fax and others.

It's very simple to implement, so this is our warm up 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?

And so, 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 int, whatever the value is, so we put that into the int run.

So that's a number between 0 and 256,

which is the maximum you can get in 8 bits.

And then starting with 0, the first count, that's the number of 0s we need to write.

So we just write them out one bit at a time, 0s one bit at a time.

And then we flip the bit to make it 1 and read the next count.

And now, we write out that many 1s and so forth.

So, this is a ten line program that does expansion for run-length encoding.

And you can think about or look at the book for how to do compression.

It's just as simple.

So, this is just an example of the effectiveness of run length encoding for

one letter, the letter Q, in a typical black and white scanned image.

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 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 8.5 x 11 piece of paper with 300

pixels per inch, that would be 8 million bits.

But most of those are white and typically with run-length encoding

you can get a substantial savings simply by basically counting the white bits.

And even when there's letters involved, you can get, say,

maybe there's only 3,000 characters.

That's another example.

If it's all text then maybe the text itself is a great way to compress it or

the programmer or the document processor that produced the text,

but now we're starting to get into undecidability issues.

So let's think more in terms of a page that has 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 as possible.

And then run-length encoding is going to be very effective.

That's our warm up case for data compression.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play