Video 7-6: §7.5 Run-length encoding

0:00 <Untitled Chapter 1>

0:05 foreign to part two of the compression unit where we'll look at uh repetitive texts and basically part one was fairly short and simple because it had a definitive answer there we looked at the character frequencies and Huffman codes gave the best possible answer with little really to um really little open to wish for uh so in this part that will be not quite the state um it's it's even having a definitive lower bound that would be the equivalent of entropy is is not quite available yet but we'll see which parts we can uh say something definitive about

0:52 Beyond Character Encoding

0:55 to motivate this let's look at a text like this uh you may know where it comes from but it doesn't matter uh maybe this is not the most natural text but it's um somewhat prototypical if you look at the character frequencies it would be relatively even there are some characters a bit more often than others but overall you don't save so much from exploiting that whereas this kind of text in the extreme example definitely has a lot of repetition or a lot of redundancy that we could try to exploit with a compression method and half man just won't cut it here it doesn't seem to catch that type of redundancy at all

1:45 and um it seems as long as we stick to encoding each character out of one character at a time and each character the same no matter where it occurs so in what context it occurs uh we seem to be stuck in this so the only the only option that we have is to look at more than a single character at a time for encoding

2:10 as a first warm-up for this we'll look at run length encoding which will show you the the spirit of some of these but it's relatively restricted in the type of redundancy it can pick up on

2:28 it's a repetition in the simplest form namely runs of characters so just which just means the same character repeated many many times for Simplicity in this this section we'll look at just the binary input but you can generalize this a bit um and so here's some example that might show where this is relevant if you have a black white scanned image you represent this as individual pixels on or off then you might may have really long stretches of all zeros or all ones and I think at least some old formats use run length encoding for that

3:11 what run length encoding then does is say look there's instead of zero zero zero zero zero there's five zeros three ones four zeros so you compress the runs by saying how long it is and what symbol comes because we're in a binary alphabet we can actually do slightly better we can store the first bit once and for all and after that only the length of the rung because we know it's always alternating between zero and one there's no other character if you had a larger alphabet you couldn't do that then each run would have to say what is the character that is repeated now uh but for binary it's it's particularly convenient so we don't have to really store which grid it is let's look at an example um which is this one from buff it would start with a zero because the zero bit is the first then we have a runoff length five five zeros then we have a round of length three must be ones and then another four another round of zeros okay

4:23 but again um like before that shifts the problem how would you encode uh the length of such a run without making assumptions about an A maximal number that you can represent

4:42 and so I asked this question uh already during the break how would you represent an arbitrary string that can be arbitrarily long run length run length well what's the run one way that we discussed before is you could store the length of the string and then all the characters but again how do you store a number that could be arbitrarily long

5:14 yeah it's most mostly that idea in various forms exactly that's the the other option that we have we can have uh we can reserve one specific character as the end of string symbol we've used that all the time in unit 6 right so it has its pros and cons the the benefit is we don't have to worry about encoding arbitrarily sized numbers the downside is we have to reserve an extra symbol it's also a bit like what the morse code did right so basically these two options store the length or store a Terminator symbol and both are used in programming languages for Strings I think Java Pascal is more

6:18 don't ask me about python Springs in Java and and Pascal are essentially length and then an array of that length of characters and C C plus plus they use these null terminated strings zero terminated there's a special character the zero character that signals end of string now if we want to use this in in run length encoding and want to store an integer that could be arbitrarily long we can't really use this or we don't want to use this end of string symbol because then we don't have a binary encoding but it turns out there's a really nice and clean solution which works well for this use case where we get a prefix free encoding for all integers unbounded it works with arbitrarily big integers so that's the um that's the wish list we want to be able to store any integer well the natural numbers I should say and we must know it must be instantaneously decodable we have to know when we have to stop

6:42 Elias codes

7:35 now there is a very simple such encoding it's actually super easy just the unary encoding seven becomes zero seven zeros and then one that's essentially using an end of string character but I use only one character for the number which works fine it's just a bit long right so that's not a really good encoding but it is one that fulfills the requirements here so at least it proves it's possible but it's a really poor encoding way too long so we can store some numbers but it only really is useful on small numbers if n is too big maybe log n is not too big why do I say login the trick is we can use

8:27 we can write a number in binary but before we write the binary digits we use the unary encoding for the length of that binary representation so we first say in this really stupid silly code this is the number of digits that will come then there's the binary digits

8:52 that's known as as Elias gamma code the gamma comes from the fact so this this is essentially the first one you could keep iterating this you could say um instead of storing the length of the binary representation I could store the length of the length of the binary representation if I store the length in binary and you can keep keep going like this we will not do it we'll just use the this version we store the length of the binary representation in unary and then follow that by the normal binary representation of the number there's a few twists if you look at this closely you see you can shave off a few bits at a few places first trick is in our scenario we know the numbers start at one so a normal binary encoding um uh well we can we can just subtract one from L and store L minus one instead for the length because every number we are interested in will have at least one bit so no need to say oh it's always one uh you can just start with one less the other trick is the binary representation of any number if you leave out trailing zeros it has to start with a one and so the binary representation starts

10:13 with the one that means we don't need this terminating one in the unary representation because that's there's implicitly a one coming next anyways so that's two bits uh kind of saved

10:31 and that's the final Elias gamma code it's the length of the number in binary minus one that many zeros followed by the binary representation so example the number one written in binary is just one it has length one but we store one minus one many zeros so zero zeros and one one just a one number three in binary is one one has length two I store one zero and then the number zero one one Fife is 101 in binary length is 3 take away one two zeros and then 101. there you go and 30 uh well I know that 32 is a power of 2 so 31 is five ones if I take on one that's Thirty one one one four ones and one zero that's five I take one away four zeros and then this thing okay all you needs for this really is to convert between binary and decimal uh which I'm I'm confident you're you're in principle able to do with the question is how quickly or how slowly uh I'm also not the fastest in this

11:49 let's practice this a bit and I made it a little harder I don't show you the end of the number so you have to figure this out for yourself

12:08 so this is some stream of bits and uh it starts with an encoding of a number your task is to find that first number oh boy some of you came up with really big numbers you must you must think I'm cruel

14:01 all right let's wait a little bit uh maybe for 20 people all right there's my 20. let me show show what people send in like this is I'm I'm not such a mean person right who would want to convert that to binary that's really really cruel no um let's briefly do it together um I didn't tell you how decoding works I was a bit of a meanie right but um I showed you how encoding works and you just have to do that in Reverse of course always um so encoding took a number and then first wrote the length minus one in zero so we start looking at how many zeros there are three zeros but that means I have to read four bits for the length of the number for the for the number so that means four bits and the next four bits are one one zero one otherwise known as thirteen in binary right it's eight plus four plus one

15:25 Clicker Question

16:15 so one one zero one base two that's that's how I learned write things in base two but yeah just annotation now of course you can continue decoding things from there on um and maybe a little uh little thing for you to think about is the code subjective is can you always find in a in an arbitrary spit sequence some prefix that decodes to a properly encoded number that's that's for you to think about um not so relevant for this but so we know now how to encode an arbitrary sized natural number in binary as a prefix free code the rest is simple now we just include that in our run length encoding so here's an example for encoding we have this one this long uh binary string with lots of redundancy runlink encoding says first the first bit is what's the first bit it's a one so we store a one that was this one exceptional bit and now we have to count the next the length of the run which uh the counting has conveniently be done on the slides so it's seven ones so we have to store seven in Elias gamma code I won't do that in in the full detail again all the time but seven is one one length is three two ones uh two

16:50 Run-length encoding - Examples

17:47 zeros in front okay uh one more then the next run is of length two two zeros so we store two inelias gamma code two in binary is one zero one less zero in front gives you one zero one one zero one zero sorry

18:14 one more the next run is a single one and that in Elias gamma code gives us a single one we've seen that example a few slides back now here's a really long run 20 apparently here's one zero one zero zero in binary and then four zeros at front tells you how long it is foreign last run 11 11 written in binary is one zero one one that's length four so three zeros going to run

18:51 now you can work out the compression ratio in this case but already visibly it got got smaller of course because of these really long runs it's quite effective let's also look at an example for decoding

19:07 so for the full run length decoding the first bit is special remember that's just telling you whether you start with zeros or ones the first bit is zero so we start with a run of zeros and now we start Elias gamma decoding we find three zeros in a row that means the length of the binary number we are reading is one more than that four the next four bits of this which is again 13. so we produce 13 zeros in the output then we go to the next run we flip the bit now we produce a run of ones we see two zeros in a row there so we will have to read three more bits for the number that's one zero zero that's four so we produce a round of four Once

20:00 and one more time the next will be a run of zeros there's no zero before the next one so we'll read just a single bit and that'll decode to a run of just length one

20:18 and last round we again have a random length of ones we find one zero so the length we have to read is two so these two encode the number two as well so we uh finish off with a run of length two of ones okay

20:39 Run-length encoding - Discussion

20:43 as I mentioned before you can use it on larger alphabets but then you have to say which which character is repeated that makes the compression ratio a bit worse okay this is the image format I mentioned before I don't think it's used much anymore but it used to be a format for fax machines uh I mean no one's using these anymore it's a very simple and also quite fast encoding scheme and it achieves something that Huffman was never really able to in the extreme case of an input that's all zeros of all ones you can get exponential compression with running encoding because you can encode n all zero bits with a single zero at the beginning and then essentially the number n written down it's two log n Bits that you need because we have the length and the number but it's still uh within Theta log n Bits that's a really dramatic reduction however it's for only this very extreme case of all zeros when you go away from that and have something more interesting you very quickly get much much worse compression indeed for many types of of data that occurs uh the compression is negligible and remember the no free lunch theorems it's not possible to have a code that always gets every bit string shorter

22:11 so at some point we have to suffer we have to make some bit strings longer and it turns out the the the bitter spot the the the place where it gets longer is when we have run lengths two or six that's the two numbers where the gamma code is strictly longer than the number written out in unary and so if if your input has lots of runs of these lengths then it will get longer by this compression algorithm