Video 7-5: §7.5 Run-length encoding

0:00 Intro

0:02 in the second part of of the compression units i'd like to look at repetitive texts in a different sense the first part was about characters of different frequencies and then we saw how huffman can exploit that and now we'll try to look at repetitions on a bigger scale i want to motivate this a bit with this uh maybe well-known example i don't know i don't know if this is qualifies as a natural text um but uh more sensible natural text also has the the feature that they appear the same words many many times where it's like the and and well you know the the frequent words in english and in other languages they just occur many times but that doesn't necessarily mean that the character frequencies reflect that in exactly the same way and in this extreme example i think this becomes quite clear

0:19 Beyond Character Encoding

0:59 suppose this text keeps going over pages and pages and it's always the same sentence repeated again and again so if you compute the entropy which we've seen is is a good predictor of how well huffman will compress this you will see that the entropy of this text is not so low

1:24 in particular you will have some contribution for each character and that contribution is the same for every character no matter how long the text is that's how entropy works after all it goes character by character and it doesn't in any way recognize that after a certain length the whole thing just keeps repeating so if you want to capture that kind of redundancy anything that's based on huffman or individual characters just won't work you have to put in context several characters at once to get get this compressed reasonably so it seems like um the whole notion of of compressing one character and replacing it with some code word is is not strong enough instead we have to use what's called phrases so that's just substrings of the text and replace a whole phrase by some code word in this case we would want a phrase that is just this sentence and then there's some way of saying just use this code word all the time and hopefully the code word is much smaller than the sentence or maybe there's even a smart way of saying let's use this code word now so many hundred times okay and we'll see some examples of both of these ways of compressing now the the challenge of course is most

2:45 texts don't look exactly like that they have some sort of repetition but it's not as obvious as this and not as extreme as in this one the first example of a code that can achieve something like this is a very simple one that's called run length encoding and that's the simplest form of repetition one could think of it's runs of the same character so it's just the same character repeated several times in a row and it might make sense to have to expect something like this if you think about black white images that come from a scanner maybe it's scanning some some page with a high resolution you want to see all the characters nice and detailed but if you restrict it to two colors we will see many runs of zeros and ones like in this example

3:39 for this for this section we'll restrict the source alphabet to binary which is not necessary to do in run length encoding it just makes the the algorithms a little cleaner we'll i'll comment on this at the end again of this section it's not a not a very substantial restriction the method can generalize

4:04 the idea of run length encoding is to use as phrases the runs of this character so in this case we have five zeros three ones and four zeros that's slightly more succinct than saying zero zero zero zero zero one one one zero zero zero zero right

4:23 now if we want to store this you can of course not simply simply list the numbers you have to somehow convert that to binary again and so we need a smart way to do that but what one-length encoding consists of is a little bit more structured we have to tell the decoder what is the first bit do we start with a 0 or with a 1 in the entire string and then we have to tell it how long each run is we don't have to store anything else because you always know if i start with 0 and then there's a run of 17 zeros the next run will be once otherwise it would be the same run so in our example we store a zero for we start with a zero and then five three four for the length of those runs okay easy so far

5:19 the question that comes up is we have these numbers that we want to store these are some integers and and well at least in principle these can grow without any bound it could be that we get an input where there's a run of zeros of arbitrary length could be the entire file so we have to be prepared to store an integer that we don't know how big it is it could be as big as uh well we don't know we don't know up front so we have to be prepared to store an integer of arbitrary size how do we do that how do we do that in binary

5:57 and as a start think about how programming languages do this that's where the question gets at programming languages have to solve a similar problem all the time they store strings and their strings have variable length but computer memory is just long sequence of bytes there's no specific boundaries how does a programming language handle this problem how can it store strings of variable length

6:49 so think about low level uh if all your computer has is this think about a word ram okay you have one big array and each cell can contain a number how can you store a string so that a user program can know this is hello world and then it stops without knowing how long the string is in advance it could be as long as the user gives you an input

7:25 okay i'll show you some some of the suggestions uh okay this is you just see the most frequent one yeah i know you will start this game again of course

7:50 all right always jumps back i can't scroll fast enough i think the two main solutions that i know of have been in the list um shockingly they're not not emoji okay i'll keep you play and let you keep playing but so the two solutions i know of option one you start you prefix the string with the length of the string so the first the first entry says now comes a string with 500 characters so you know the next 500 cells contain characters that belong to this string now there's a slight caveat here you need to somehow restrict the strings to a length that fits in one word now right you have to fit that number in one word so it's kind of cheating but it works fine in practice because we don't need strings that are absurdly long if a word on the computer now is 64 bit 2 to the 64 is a really long it's a really big number your computers don't usually have 2 to the 64 bytes of memory not even close to that and so it's fine yeah it's a little unsatisfactory in theory maybe the other solution is you reserve from the alphabet a special character and say this is the end of the string and well c you traditionally use this

8:09 Clicker Question

9:18 null term so the character that just consists of all zeros the null character is the marker for the end of the string it's part of the ascii alphabet but it's not allowed to be used inside the string if you use that convention which is a restriction and so you need to make sure that the programs obey that or you enforce it by adding another bit or something like this okay these are the two options now what can we do for for our integers of arbitrary size it seems both are at least from a theoretical perspective not completely satisfactory and also we want to do it in binary okay there's a really nice way that is called elias coding and what we need just rephrase that a bit in different terminology we want a prefix free encoding for integers why prefix free because we want to decode it and that has has helped us in the past so let's stick with that property but we wanted to allow arbitrarily large integers there should be no baked inbound like in this store the length of the string first version and we need to know when we're done that comes with the prefix freeness but this essentially means we cannot simply write down the binary representation of the number because

10:00 Elias codes

10:43 then we wouldn't know when one number stops and the next begins what you probably didn't think about but is completely obvious in hindsight maybe is there is a simple encoding that satisfies both of these properties fine that's the unary encoding that's if you make ticks on the board to count something i can represent a number by that many zeros followed by a one to signal the end if i'm if i have two symbols and i only use one to represent the numbers i have another one free for the end of word symbol it's just that we don't like this encoding because it gets really long or even moderate numbers so that's not great but it it exists right it's fine now it's much too long and in a in a sense the output has long runs and we want to use this for compressing runs so that seems to get us nowhere

11:47 now the trick in elias codes is the unity encoding of the number itself is crappy long but what if we take the binary represent binary representation of a number which didn't work by itself because we don't know how long it is but we know to store a number in unary so we store the length of the binary representation in unary using exactly that idea and then append the actual representation that doubles the number of bits that we need compared to just the binary representation but it it makes it prefix free and that's that's called elias gamma code

12:27 and okay i lied a little bit elias gamma code is a very slight refinement of that idea because immediately if you do that you notice two things the length of the binary representation is always at least one we only represent natural numbers starting with one so we might as well store the length minus one instead of the length saves a bit and the second observation is the binary representation of the number always starts with a one because we don't want uh leading zeros and so we don't need the terminating one of this run length encoding either just because there is always a one coming with what we append next so but with these two slide modifications this idea is is what's behind elias gamma codes so here are some examples um one is just mapped to one now how's that one in binary is a single one the length of that is one we store not the length but length minus one so we store zero zeros followed by the binary representation which is just one zero zeros one one okay uh how does three work three in binary is one one the length of that is two take off 1 means i have to put 1 0 in front of it so 0 1 1.

13:58 let's do 5 as well 101 is 5 in binary and so i prepend two zeros one less than a half digits and for 30 well you can hopefully figure out that one one one one zero is is 30 in binary uh yeah 31 is is 5'1 so that looks good and so we prepend four zeros because we have five digits in the binary representation okay apart from the brutal task of computing the binary representation of numbers this is not too hard to do

14:37 let's see if you got this one let's do the opposite we decode and to make it not so boring i added more bits so what you see here is is a string that contains a number and other garbage after it and you're just supposed to decode the first number that's encoded with this elias code okay i think you have the string in the question so let me maybe go back to the slide with the instructions

15:08 and please send me the number in in decimal not in you know whatever whatever that is how did you make one one answer appear in colored is this also in that view okay i haven't shown the ah okay a few more minutes

16:20 okay i'm not not sure what the color code means i'll show some answers because i want to get through uh some more exciting stuff too i think the colors are just how often it was it was answered uh various various things um let's just go through this so that we do it once together how do you start first you check how many zeros do we have three zeros that means the number i'm reading has four digits so i have to take these four sorry

16:59 that's the number i have to decode so what is okay you don't see it all right sorry for that uh the first three zeros tell you you need to read four bits these are the four bits now what's that number in decimal uh four ones would be 15 so take off 2 would be 13. that's among the options at least

17:35 you will get some more um practice for this one um and here are some examples how this is used in run length encoding uh remember what we do in run length encoding is we store the first bit starts with zero or starts with one and then is this the what follows is a sequence of these run lengths encoded using our new our new favorite toy the elias code

18:07 Run-length encoding - Examples

18:12 okay let's uh go through some examples we store a one because the first run here is with ones not zeros how many ones are this uh seven ish so we need to store the number seven let's do this one more time seven is one one in binary so i prepend two zeros to signal that the length is three okay now we have two zeros that's in binary one zero written prepend to zero for length two a one is mapped to a one we've seen that example before these are twenty zeros i believe my slides um twenty i hope is is this in binary five digits so i prepend four zeros okay got the idea uh one more for eleven eleven is this in binary prepend three zeros and there you go

19:10 let's try to see um [Music] well in this example it worked quite well uh compressed it down to 63 let's do one more example of decoding so first step the first zero

19:29 always this pin the first zero says we start with the run of zeros then come three more zeros so the length of the number we're reading is four so we take these four that was 13 so we produce 13 zeros in the output let me keep going the next two numbers uh we have two zeros so we need the next three bits that's one zero zero otherwise known as four so we prepend append four once

20:13 we read zero zeros before the next one so we reach as one bit and that is a one so we append one whatever the next thing is zeros there you go and one last one we read one zero that means we read two more bits one zero which is known as two so append two once that's how running encoding and decoding works okay

20:41 Run-length encoding - Discussion

20:48 now if if you don't have a binary alphabet uh this alternation between zeros and ones no longer is enough instead you have to say which is the next character there's probably no way around this and then you need to maybe come up with a smart way how do you best encode that other than that run length encoding also works for bigger alphabets you can just write down a pair now comes character a so many times and the so many times is again elias gamma coded and this is used in in isolation to be honest run length encoding isn't that great but it's used in some old formats at least it is a quite simple a quite simple algorithm and so can also be implemented very quickly to run very quickly and it's a part other than the the huffman code which could essentially always just cut the text down to some smaller constants times n for a fixed alphabet the run length encoding can be extremely effective if the input is extremely boring and the uh ultimate case is if you have a a file that's just n zeros then uh run link encoding would find a single run and encode that using two log n bits right log in for writing down n in

22:10 binary and prepend as many zeros minus one so that's a reduction from n to log n as a really com really strong compression but of course it only works in these very extreme cases if you have very few runs

22:29 more realistically for most types of data in isolation the compression is negligible and so if you compare exactly how many bits you use up to runs of length six you don't save anything and for the specific numbers 2 and 6 the gamma code is longer than a run of that length so you have expansion for some inputs and you have compression for ones that have very long runs more than six remember this was this no free lunch theorem that you will look at tomorrow in the tutorials today or tomorrow uh no maybe so compression can't always work you will always have for each compression method some inputs where it only makes things worse