Video 7-5: §7.4 Run-length encoding

0:00 Limitations of frequencies

0:03 in the first part of the compression chapter we talked about how to exploit character frequencies in this next part we will talk about repetitive parts in the text and how to exploit this and we will see the lampposif methods as one core representative of this family of compression methods

0:31 so it turns out that um many natural texts have a certain type of redundancy that is not well reflected by character frequencies here i listed some example of a text that might not be the very most natural one but it's definitely a very repetitive one but if you were to count how often the characters occur in this text you will find that it's it's not that not that um [Music] unbalanced in a sense if you make this very very long then all the characters will occur roughly as many times as if you were just looking at the first copy of this sentence and that's a standard english sentence with no no bigger redundancy than usual so we would essentially uh pay the cost of the number of copies times the cost for storing one copy well in fact the text is just the same very same sentence over and over again pages over pages so that doesn't seem to capture the redundancy in this case character frequencies are just not seeing this type of long distance redundancy

1:48 and we'll we'll see this often in natural language text but also in other types of data dna's dna sequences tend to have the same type of long range copies or almost identical copies and yeah free character frequencies don't capture this in a sense here what we would like to do is go away from character encodings as long as we're encoding every character in isolation using the same code there's no chance we will capture this sort of of redundancy of repetition

2:28 Run length encoding

2:30 as a first method a first simple method that falls into this category we'll look at run length encoding for for two reasons one because it's um the easiest method that does uh exploit repetitiveness in in in a certain way even though only in the slight in the simplest form but also it is another building block that for uh modern day compression you usually don't rely on a single method but you keep you chain things together in an interesting way to squeeze the last little bit of redundancy out of data and run length encoding is a fundamental part in the key in the the bzip pipeline that we will look at at the end so let's see what this is about a simple form of repetition is the same character repeated many times and uh an obvious application of this might be a black white scan of a text page say where you have well you have uh some text you can hopefully see this uh if you were to represent each pixel by a single bit for just black white that's enough not gray scale black white uh uh in the literal sense you would expect to see many runs of zeros for all the backgrounds and maybe even runs of ones because the resolution of the scanner is much

3:51 higher than uh individual widths of the characters of the cliffs so you expect to see many runs of repeated characters in such an application and run length encoding is is brilliant for picking these up indeed we will restrict our attention for for this unit here for this mod for the subsection to just a binary source alphabet already for huffman coding we were restricting attention to a binary coded alphabet but now we'll assume the same for the source alphabet just to make our life a little easier you can generalize the ideas to larger alphabets but indeed it's often used on binary inputs anyways because as i said it's used not as the first step but after other methods have already done their magic

4:51 so a simple example of run length encoding here oops is if we have this input text so i just want to illustrate the idea um the first step is we parse this input text into phrases which are just runs of the same character right okay so here we have five times the zero three times the one so we would always group these together as long as the same character repeated it's the same phrase that's something that um that we will use in in this in this section a phrase is a part of the source text that we encode as one step so we have to encode these phrases and well obviously for a binary alphabet it's enough to store what was the first bit in the source 001 and then what's the length of each subsequent run we don't have to store which bit it is because runs have to alternate between zero and one if the alphabet is binary so in our example we would write a zero for we start with zero and then five three four is the length of these runs there's five zeros three ones and four zeros again these four numbers completely specify this source text and that one has well um what is it 12 bits and this might be hopefully

6:20 be represented in fewer bits so that part of run length encoding is very easy the question that remains is how do we encode these run length numbers which can be arbitrary integers in binary for that we have to think a little and to get you started i like to ask you to think more generally how would you approach this problem of storing a string think of your favorite programming language it probably supports strings it would be a really weird language if it didn't and probably these strings can be as long as you wish you can specify a string of arbitrary length as long as it fits in memory and blah blah blah but there's no uh no built-in limit usually for the num for the length of a string how does uh such a language represent a arbitrarily long string

6:28 Binary integer representation

7:21 at the end of the day it has to reside in main memory it has to be stored in your computer so you have to have some way of encoding it in binary and that's the same question that we're asked here in run linkedin coding we have arbitrarily long integers at the end of the day these are binary strings so it's the same problem how can we represent a string that can be arbitrarily long if the only thing we have is a large large binary memory where we have two things we have to store things just using zeros and ones uh think about it for a second and a lot i'd like to see a few more answers maybe you can help me out and type something

8:09 think about your favorite programming language all programming languages have found a solution for this um so uh they all have solved this problem um maybe you wondered uh sometime before how they do it let me show what people came up with so far the first suggestion is a linked list you could use a linked list indeed provided that memory management is there for you um a linked list essentially solves the problem by reserving a pointer uh for each for each bit in the extreme case for each character and uh you would have um a special symbol that says this is the null pointer right that says there is no more next character that's a way to do it it would be inconvenient in this case because it takes a lot of space to store all the pointers um it is true that we can assume the length is is a multiple of four uh if we store the length in bytes or um well bit strings whose length is by definition a multiple of four uh why would every bit string have a length multiple of four anyways uh you could you could make that assumption uh my claim is it doesn't make the problem fundamentally easier if you have this restriction linked lists are great guys but they're

9:41 very space inefficient because you would need a way to store pointers and that pointer needs as many bits as you have space in your entire memory so that really grows beyond any bound using graphs

10:00 sounds like you use pointers unless you get more specific uh it probably has the same issue that pointers need a lot of space uh i'm not sure how kmp helps in chunks and join them that's a good um that's a good engineering trick instead of using linked lists for every character you definitely want certain chunks of a certain length and you could use pointers again but remember if

10:33 if you don't know any upper bound on the length of the thing you store uh pointers are a problem variable sized arrays uh that sounds good but how would you how would you do that um a variable size a string of arbitrary length is in a sense an array of arbitrary length how do you store an array how do you store an array of arbitrary size so maybe i keep thinking about this a little more

11:04 it's it's sometimes fun to think about these very fundamental problems that obviously have many good solutions because we use these solutions all the time all right um i'll tell you a solution for the special case that we need and uh we can revisit the other more general question i can tell you what the solution is in in java for example if you're curious what we need here is an encoding for integers so we don't really need zero so we can start at one but we need the encoding to be prefix free so that we can represent all possible integers and we can decode that unambiguously that's uh that's the key thing the challenge is to know when to stop reading well that's uh same same thing as saying prefix free if it has to be prefix free it must be obvious when you have to stop reading so how could you do this uh there's a very simple solution which uh i'm sure well this is not what you would come up with but it's actually very simple you can you can obviously do this you use the unary encoding which means to specify a number you write as many zeros as that number is finished by a single one that's a great encoding it works

11:14 Elias gamma coding

12:27 uh it's just super super bad in terms of space right it takes as much space as the number is big and you could actually represent 30 with just what is it five bits and now you expanded it to 31 bits and well we started with run length encoding to get rid of long runs now to store the runs we produce long runs maybe this is not the solution yet but we still build on this and the trick is to see this as the base case of a recursive construction not sure if this is helping you

13:16 the standard binary encoding of numbers is actually fine it's actually very efficient the problem is that it's not prefix free right if if i write 1 0 1 you don't know if that means 5 or it's actually the prefix of an even longer number like 10. but the encoding itself is space efficient so what we'll do is we'll store the length of the binary representation in this stupid unary encoding which is space inefficient but prefix free and then append the binary encoding now that we know how long it is it's no longer ambiguous okay that's the key idea of elias gamma code

14:02 once you start thinking about this you obviously you immediately find that there's some obvious ways to improve upon this uh first of all the length is always at least one bit so we might not have to store exactly seven bits here but we can store just six zeros because we never need uh just we never need the zero that's just not not needed in our application and also the binary representation of any number if you leave out all leading zeros necessarily starts with a one by definition otherwise uh you wouldn't have taken all the leading zeros away so there's no need to store that one we can start one later okay but that's uh that's just minor twists to the core idea which is store the length of the binary encoding in unary and append the binary encoding so what that leads to is uh for one the binary representation is a one just a one the length of that is one but we store l minus one zeros which is zero zeros so one is just mapped to one the number three is one one in binary that's what you see here this the length of that is two so we prepend one zero one less than two one more example five is 101 length is 3

15:27 so we have to prepend two zeros 30 happens to be this uh length is five you prepend four zeros there you go that's elias gamma code that's a way to represent an arbitrary integer it can be as big as you want in a prefix free way and as you might uh might might see from this uh we take the binary encoding and you make it roughly twice as long by adding another adding this bunch of zeros so the

16:22 k is um is log k to represent that number and then twice uh plus minus one um minus one i guess because of uh the one zero less than maybe minus two actually uh but this is roughly what you get whereas here it was linear okay so that's the important difference before we come back to uh the string question let's practice this one here is a bit string there are more numbers encoded here so you're just asked to decode the first integer in elias gamma code at the beginning of this bitstring i'll show you the the code again you have the bitstring in the question

17:17 i added more more bits to the bitstring so that you don't have the obvious separator so you really have to figure out the encoding um so your answer should be a decimal integer right i'm asking you to decode so this should be again a number in in capital n in in the natural numbers so don't send me the bit string you want to decode that further

17:55 okay you might need a second to do this and we'll go through an example after that okay lots of suggestions let me show you some of them together or um

19:01 i'll leave the question open and just go through the examples and then you'll try again if you haven't done it yet so let's see uh some examples and you can work out on the other one on your own first an example for encoding and this is the full run length encoding now which uses the gamma code for storing the run lengths okay so but you you'll see this uh involves lots of uh practice examples of gamma code so uh it's uh it works fine we have this long bit string we start by first noting what is the first bit 100 well it's a it's a one so we store this next we store the run length and this is seven bits so how do we store seven well seven is one one one in binary the length of that is three so i have to add two zeros in front and that is uh what has happened here that's the seven the next run has length two the two is one zero in binary prepend is zero that's what you see here

19:14 Examples and decoding

20:16 another one uh we have just the one so we remember uh that was just mapped to one maybe we don't have to do that one again okay good that i already counted this 20 zeros now uh 16 and four makes 20 so that's 20 in binary and adding four zeros in front gives you the code for 20. and another one 11 once at the end 11 is 8 plus 2 plus 1 so it's a 1 0 1 1 in binary and adding the three zeros to code the length gives you the result so that is the coded text for run length encoding of this bit string that's the entire method now uh in its full glory

21:08 uh let's see how um how well this worked uh if you can if you count here that was 26 bits of the coded text and 41 in the source text but that's down to 63 percent uh which which looks great but also of course this was a a fairly favorable example for run length encoding

21:30 now let's practice some decoding and again this is a run length encoded bit string so it will uh it will follow the same pattern the first bit is telling you what is the first bit in in the source text so it's a zero and now we have to start reading the next number so what you do is you look for how many zeros you find in this case there's three zeros so the length of the binary representation of the run length is four bits so you take the next four bits and decode that in binary okay that happens to be 13 8 plus 4 plus 1 so you know you have the 13 is the encoded number and so you write 13 zeros in the sort in the decoded source text okay and then you continue with the same procedure you count how many zeros do you find that's two plus one so you have to read the next three bits and decode that as a binary number that is four so you append four ones okay one more time you start how many zeros do you find well no zero so you just read one bit that's a one so it's one the next run length is just a one so you append one of the the next flip

22:58 bit which is zero and uh one more time you count number of ones there's one at the number of zeros there's one zero so you read the next two bits that's a two so you append two more ones and that's it okay um do people want to go back to the example from the question

23:31 so let's do this one more time here together this is not run length encoding so there's no leading zero one it's just numbers so we count how many zeros we find that's three so we have to read the next four bits as binary number that's these four that's a a one plus a four plus eight that works out to 13.

24:04 so 13 is the correct answer i see people need more practice for this i know this is this is really really um [Music] maybe you want to see these but i lock it i know this is really really detailed stuff you will have uh more um opportunities to practice

24:30 good um let me see if i can jump over some of the many slides for this example good so that is run length encoding it's um okay i thought i had some pseudo code but maybe it's not needed for this one you can extend run length encoding to larger alphabets but then you have to say what is the next character that is repeated for binary you didn't need that because there was only one other character it's actually used in in some older formats for for images except especially for for scans but again as i said in isolation this is not the method of choice um you usually use it as part of a larger pipeline of compression methods it is simple it's also fairly fast uh in the best case it achieves remarkable compression from n bits down to log n bits roughly factor two or so but this only happens if you have very few runs very long runs off of the same character but uh this is um the potential uh gain from run length encoding is is much much bigger than uh what we've seen before with the character encodings there's no way you get subliner with any of the character encodings whereas with run length encoding you could potentially get exponentially smaller

24:42 Efficiency and application

25:56 however for typical types of data if used in isolation it doesn't really give good compression you need if you work out exactly how many exactly how many bits you need to encode the numbers with the lias code you will see that if the run links are not bigger than six then you don't get any compression and you actually get worse you get expansion when ever you have runs of length two or six these happen to be the two numbers that are represented with more bits than necessary

26:32 or more bits than the unary encoding in the run in the original source text would have taken