Video 5-5: §5.5 Run-length encoding

0:00 Limitations of character codes

0:02 in this second part of the compression unit we'll look at compressing compressing using methods that exploit how text is repetitive in a different way not just single characters being more more frequent than others and let me start with a maybe not super serious um example why this makes sense if you have a text like this um of course it's inkish text so it will have something like the character frequencies that we've seen in the Huffman chapter and they are not completely uniform so you can compress it a little bit but if you if you make that text much much longer and the uh in The Shining he does H it feels like this should be compressible much more but if you just take the character frequencies and you double the length of the text you still double the length of the the coded uh text even if it's completely predictable like in this case and that feels a bit wasteful so any anything that works character by character and uh looks only at how frequent specific characters are will not be able to capture such repetitions and so that's a it's this um intrinsic limitation of character codes if if you only look at single characters so what can we do um I guess obviously we have to encode more than

1:28 one character if if that's an inherent weakness of character codes so the the term that people use for this in the context of compression is a phrase that's a substring of the source text that's represented by a single code word and the hope with that is that we can somehow capture these kind of repetitions where uh halfman couldn't do

1:59 that before we come to uh methods that do that more effectively we'll look at something that seems very very limited but is is a good stepping stone um and also building block uh I mentioned this several times maybe it's a good point to uh take take a a step away from concrete topics and mention this many compression methods especially the ones used in practice are not one single textbook method they combine different things and they often use them one after the other so they apply some pre-processing and then another step and then maybe at the end they do some Huffman code or they have some phase of run length en coding that we'll we'll cover next in it many of the methods are in isolation not as strong but they can be combined uh we'll come back to that idea at the very end but for now I want to start with um a first type of compression method that's very simple but still shows you how powerful exploiting repetitions can be in the extreme case it's a is a simple one okay so what's the simplest form of repetition we could have in our source text just words that consist of the same character repeated over and over and we call Those runs here that's where the

3:01 Run length encoding basics

3:14 name comes from not to be confused with runs in the context of sorting where this was a sub secet or subw of the input contiguous segment that's already in order um that's not what this stands for here it's just several times the same character um you can easily imagine how you can obtain some something like this if you have an image that's just monochrome just two colors say uh a simple scanner that only does black white um then maybe a if you have a high resolution image you will have many of these runs so that's one one application where this naturally arises uh we'll simplify our life here and look basically at binary alphabet's only but much of what run length encoding does can be generalized to arbitrary Source alphabets uh the binary alphabet has has one nice additional feature that we'll come back to that makes this a bit a bit cleaner but it can be

4:20 extended the basic idea of a run length code is to split the input into phrases that are just runs so if my source text is this I'll I'll decide I'll have these uh three phases uh these phrases and I can say this is five times a zero that's three * a one and that's four times a zero even just writing it out like this if you're imagine these are a bit bigger of course that's much more concise to write the length instead of repeating zero so many

4:55 times so if you look at this a bit more closely what do we need to store to reconstruct a source text that we have split into phrases like this well we somehow need to know what the first bit of s was so we we store one bit for the first bit of s and then all we need for the rest is the length of the subsequent runs because by definition I never have a run of zeros followed by another run of zeros that's that's useless I can just make that one run bigger so I can always alternate between zero and one so we don't really have to store the character that is repeated because there's only one other choice that's what I said earlier where binary is nice if you had one run of zeros it will be followed by ones um for General alphabets you would have to store the the new character on top of that that's the only change so our example from before would then be zero because we start with a zero bit and then the lengths of the runs are 5 three and four and that's enough to reconstruct that Source text so that's basically all but we've cheated so far I've just used this this list of numbers and I

6:10 used the comma and all that uh to kind of separate where one number starts and where the next one stop or where one number stops and where the next one starts uh we'd really like to encode this with few bits so reserving something like a comma character and so on is is is not is not really what we want and so um we have to somehow deal with the fact that these numbers can be arbitrarily large we don't know up front how big the run is and still we want to not have a separate character like a comma that separates it so we would like to have more specifically the the goal would be to have the coded alphabet as binary as well and if that's my restriction the question becomes how can I store arbitrarily large integers if I just have these two characters right

7:09 Defining string termination

7:12 um and to work up to that uh let's collect a bit ideas because you I don't know if you ever thought about this the question here is asked in a slightly more general form not just for numbers but you have this same question for any kind of strings if you have a programming language like uh like python you can write down strings and there's no limit on how big they are I mean there's a limit practically on how big your memory is it blah blah blah but not conceptually how does how does python do that how does python know when one string stops and when the next one

8:08 I'll just leave it open okay many many many people aren't sure it's something you don't think about it um unless you have some low-level programming course you're you're not forced to think about it but it's obvious right this is a problem that somehow and someone who implements a programming language they have to solve that problem you need to know when a string stops right it's quite obvious how how would you do it okay now I I didn't follow some of the some of the answers um

8:41 yeah okay it's too fast can I zoom bit I love run length encoding um but we're we're having covered that yet okay I think I've seen the two main Solutions scroll by uh I haven't pointed them out so I don't know if you spotted

9:23 them there's basically two two options okay if if you if you want an arbitrarily long string you can either before the string starts write down how long it is and then you have so and so many um characters following uh that's a convention I think Pascal this old I don't know if uh do people still know Pascal nobody's using that anymore it's a programming language that fell a bit out of fashion uh but I think Pascal used this convention uh people know dely that's something uh that was still a little bit in use when I started programming uh that's that's based on it but I think that's that's uh it fell also this solution with prefixing the string with um a number of for the length is also not the most common solution uh the other solution is having null terminated strings so you do receive a special character even in ASI the all zero bits is the universal sign of end of string it's a kind of convention it's not enforced but um uh C and C++ uh Java they I think they all use that kind of convention I'll take it I'll take it back for Java I think Java is essentially a an array which stores its length so maybe Java also does the

10:44 Pascal convention oh I have to look this up okay basically two options and I won't comment further um on which ones are more common you can either store the length before you start than the characters or you store after all the characters a special character that tells you that's the end of string okay okay thanks for playing along um maybe I can collate the the answers a bit uh okay try it its best to that's a that didn't work so well they have to polish their AI

11:25 more maybe some of you should go and work for slido okay more seriously going back um two options maybe uh should should write down what they are one option

11:40 is start with the characters option two I just call it null terminated strings that's the terminology that c uses and so you write this as back slash zero the zero character okay maybe now you remember maybe you have encountered this um but um in a high level programming language it's it's so convenient that you don't have to worry about it that you um you ignore it now I don't know if you called me on this but option one is still cheating if the number if the length of the strings can be arbitrary how do I store the length of the string that's kind of the same problem we started with right all right so what we really need especially for run length encoding is a prefix free code something that's decodable unambiguously for all of the integers arbitrarily big is that even possible for an infinitely big set

12:41 Elias gamma coding

13:03 um maybe another question where when you first see it you wonder can you do this at all but obviously yes because we can just use unary encoding we write as many zeros as the number H is that we want to represent and follow it by a one right that obviously works it also obviously is not that great it's very long and space uh wastes a lot of space even for 30 this becomes really big so we don't want to do that but it's a theoretical possibility what we like much better is writing numbers in binary right the standard binary representation or the decimal representation is essentially a same same kind of trade-off that is fine if only we knew how many bits how many digits the number

13:57 has so that alone is way too long and the simple trick is combine those two things use a binary representation for the number but prefix it with the unary representation of how long that binary representation will be that's pretty slick right so we store the length of the binary representation in this kind of code and then we append the normal binary representation of the number so the numbers will be twice as long roughly as they would have been if we just store the binary bits but that wouldn't be a prefix free code we didn't we wouldn't have known when to stop whereas now we do and that's called the the Elias gamma code um because you can play the game further but we don't need that um it's basically these two ideas but if you look at it closely you can shave off one bit uh or two all the numbers that we represent um are are positive so they will always have length at least one so we can store the length minus one instead and uh sometimes save a bit a bit from that uh and also if you combine these two things the binary representation of any number starts with a one if you restrict it to the meaningful digits so we don't need to store that one

15:21 or expressing the same thing in a different way we can omit the terminal one of this Unity representation because we know the binary representation will start with a one anyways and so what what comes out of that is is this encoding and um that's something um okay we'll we'll practice it in an example in a second so again what what is it the length of the binary representation minus one that we write in unary and then followed by the binary representation so let's do the example of of five okay what's five in binary well it's 101 because it's four and one okay everyone uh awake the length of that is three so L is three L minus one is two so I'll just stick two zeros in front and that's the uh gamma

16:30 right let's practice that a little bit to make it not too easy for you guys this is a longer stream of bits and I just want you to decode the first number that's encoded in elas gamma code in that in that stream so you'll have to figure out when to stop that's my point

17:04 Encoding and decoding practice

17:06 so you have the bit string on slido which means uh I can go back and show you the instructions I've seen the right answer come in I've seen other answers come in

18:47 still a good bit away from the 100 that sent the attendance code okay so bit oh my God some of you really think I'm cruel like the big numbers you send that would be really really really

19:34 let's get to 70 at least and then uh I'll show you what you sent okay there we go uh lots of numbers and the free text polls can't do correct answers but um let's do it together very briefly I haven't really told you how to decode I only showed you how to encode and you had to figure out for yourself right how to invert that uh remember the first the first is a run of zeros that tells you how long the binary representation is but that's the length so it's three zeros but the length is one more so you have to take the next four bits H and decode that in binary that's one and four and8 that's 30

20:35 okay and yeah many many sent that um and then you continues with more stuff so also notice that this this kind of code um is uh is surjective this is onto so you can any any kind of bit string has a meaningful decoding as a sequence of integers you can always take random bits and practice this if you want you will usually get small numbers but that's that's what it is

21:06 okay uh here are a few systematic examples again just to practice the whole uh run length encoding so run length encoding again it uses this GMA code to store the length of runs let's do the the full run length encoding on two examples first for encoding remember the first thing we store is just the first bit because we uh we need to know what we start width so that's that's the one then we find the length of the first run that's 7even 1es and we encode that in gamma code again just I'm doing just only one more uh seven is 111 that's a binary representation of length three so I put one less zero in front two zeros that's my gamma code the next run has two zeros but I don't have to store the zero just that the length is two and in gamma code that's that's that then we have a single one the gamma code of one is just one that's convenient doesn't make it uh longer for example then we have a very long run decodes to this and finally a run of length 11 uh encodes to that you can go through those in in detail and and double check the calculations if you want but you can can practice it uh but that's what happens

22:26 now just visually you see that we made the string shorter right if there are substantial runs like this then run length encoding is effective uh let's practice decoding as well um it's the same same game we first find the first bit that will give us the the the character that we start with so it's a zero then we find after this first bit excluding this first bit the length of the first run it has three zeros that means we read four bits to get the binary representation of the Run length that's 13 so we start by outputting 13 zeros and then we keep going next number is a two zeros so we read three bits as a binary representation and that's the number four so we produce four ones I guess now you you get the hang of it so after this there's no zeros so we just read one bit and that's a one so we uh append a single zero at the end here and then we have one more number we uh read one zero so we read two bits for the next binary number oops and that's a a two so we append two more ones at the end of

23:58 this I hope the process is clear um if you practice it a few more times it's actually fairly easy to do um taking a site that you have to compute the binary representations uh as I said earlier you can extend the same procedure to larger alphabets conceptually it's it's the same thing you just have to store the character that you repeat as well so you need a character code alongside this um but we'll we'll usually only use the binary version here it's in use in direct form in some old formats for scanned images where essentially you had monochrome images but at higher resolutions it's a little less used in isolation now but it will come up later as part of a bigger pipeline what what do we like about it it's simple and fast because of its Simplicity it's fast to it's can can be implemented to be very fast um and it can do something that the methods that we've covered so far it could never do Nam it can compress something that has n Bits down to essentially a logarithmic number of bits if that input is just all zeros for example right there one long run and then you store the length of the Run instead of the actual many bits so

24:03 Evaluation of RLE method

25:14 the best case for compression here is extremely good Huffman would never achieve something like this um it's only a or depending on how big big the alphabet is it can be a super constant reduction but it won't go down to log n now of course the the negative is it's a very simple scheme it only picks up exact runs and you hardly ever have those in particular you don't have any compression unless the runs are of length at least six you can work this out by comparing the numbers um the length of the runs and the representation of the number in in gamma code and there's two cases interestingly just two for lengths two and lengths six writing the gamma code is longer than spelling out the run for all the others it's doing no worse but remember the free lunch no free lunch theorem we have to have something like this we cannot always compress uh the best thing we could do is never make it worse by leaving it as it was but you can never achieve strictly better sometimes and never worse that's impossible so we have have to have something like this and it's just two numbers so it looks pretty good um but it can mean that run length compression makes the input longer if

26:36 you have uh these kind of run