Video 7-3: §7.3 Huffman codes

0:00 Intro

0:03 and then in the next subsection i want to talk about huffman codes which will be in a way the ultimate solution to character encodings it all starts with the observation that characters come with different frequencies so uh here's um a list for for typical english pros how often each character occurs oh surprising set is less frequent than q um i mean this may depend on the text but if you take a big corpus of text you will get some frequencies and you see that they are are quite uneven so it looks like for compression you definitely want to assign e a short code word and something like these infrequent ones a longer code word you don't want to go completely crazy about making those 100 bit long or something like this but you should try to make them longer than the more frequent ones and if you remember what the morse code did it was exactly like that e was just a single a single dot and then the less frequent characters were longer up to five six six tones so huffman coding is all about getting a principled answer to how should you choose the code words

0:14 Character frequencies

1:25 Huffman coding

1:29 uh to make this a bit bit more clear suppose we have our alphabet so sigma is is the the source alphabet because the coding alphabet will always be binary now for our huffman codes and we assume we have some weights so we know these can be frequencies but in in principle here we just allow any real number so this just tells you how important this character is relative to others and you want those characters with large weight to have a short code word because they appear more often think of it think of the the weights as frequencies or probabilities

2:08 the goal of huffman coding is to compute a prefix free code so code words for all the characters in other words if it's prefix free it's a code try that minimizes now a specific quantity and that's the coded text length if you weighed each character with this with this weight w so we're minimizing this quantity we sum over all the characters how long is the code for this character times its weight if you think about a fixed text and you choose w as how often does the character occur in the text then that's exactly the size of the coded text right so to get this

2:59 we want to choose wfc as the number of occurrences i should say source text i guess but you know what i mean okay that's the same as i just wrote down and in a sense if we minimize this coded text size that's clearly the best possible characterizing coding we can hope for because we explicitly say let's pick the code that minimizes that so that's the code that gives you the minimal coded text size that seems like an ambitious goal and if you think about back to the lesson about kolmogorov complexity and how these things are all quite tough maybe this is asking for too much and then even if we can't find such codes can we find them efficiently that's even more ambitious

4:00 it turns out uh both both things can be done in this case because we restricted our attention to characterizing coatings the world is a bit more manageable so even um a very simple approach that is greedy or myopic suffices and

4:16 we'll we'll go through this in a second so greedy algorithms in general try to do a locally optimal move and then fix that for good and continue from there and we'll see how huffman's algorithm for computing uh the huffman code is doing exactly that the greedy step is you find two characters in your alphabet a and b so these are just called a b these are variable names right we find two characters and name them a and b that have the lowest weight among all the characters in our alphabet that's the greedy step now remember low weight means we want to assign them a long code word so what we'll do is we will encode them [Music] with some prefix yet to be determined and one extra bit that distinguish distinguishes a from b

5:10 and by doing this so we set the code words of a as u0 b as u1 but u is not clear yet so we'll we'll have to figure this out and the way to do it is that we replace in our alphabet the two characters a and b by an artificial character that consists of both so we i use the same notation for boxes of characters that we've seen for for uh the dc3 algorithm for suffix sorting this is just my way of saying this is a new symbol and it's supposed to represent a and b but it's just a name okay and important we assign this new character the weight which is the sum of the weights of a and b and then we recurse so we don't know what u is this prefix that we'll assign to a and b but we'll find out recursively because now we have made the alphabet one smaller we removed two characters and added one new so if we recurse and find the huffman code for the remaining alphabet and its weights it this will come back with a code word for this new character a b and that's our u that's the shared prefix that we add to them okay if you've seen this before this might

6:33 not be the way it was described there's another way that you'll see in an example in a second that you might might recognize before we go there i want to point out that you also know an efficient way to implement this strategy this step one sounds like you have to in each iteration so sigma times in total you have to find the two minimum weights characters but if you're smarter than just doing this iteration each time from scratch you keep the characters in a priority queue and then this first step is just to delete min calls so at the same time you get the two characters for the minimal weight and you get them out of the data structure and then you insert a new character with the sum of weights so that nicely fits the priority queue abstraction as we've learned about in unit two

7:32 Huffman's algorithm - Example

7:34 let's see a small example how this looks like and it's visualized here by computing this code try that's usually the way this is explained so here's a little source text it has these four characters and they appear with frequencies one two one four so you start with your characters each as a singleton leaf in the yet to be completed code try

8:01 the first step is to find the two with smallest weight so these two they have minimal weight in this example and now uh huffman's algorithm says recurse on this and this and the character eo that you form and then at some point you will know what is the common prefix of the code words for e and o another way to express the same thing is say we don't know where this is eventually ending up but as a code try there's one note where these two are branching off one with a zero one with a one and the fact that they share a prefix means this can later be part of a bigger tree but we're not there yet and we assign this entire tree now the weight 2 which is the sum of the weights we've previously had that's the first iteration second iteration is again find the two find the two partial tries with minimal weight these two and combine them into a single try where again you have a new note it has two edges zero and one and they both lead to the two previous little trees okay and here in this example one more step where nothing really is chosen so only two things left so you only have to lump

9:25 them together if you were to revisit this first step where we grouped e and o you now see that u is just two zeros but the way of constructing these tries or keeping these partially constructed tries and merging them is a is a convenient way to achieve this without ever doing the explicit recursion it's very natural to do this in an iterative way bottom up

10:00 um because we're using this notation in the tutorials i want to stress that this is just the the eo character as it was in the previous slide so that's the new character that corresponds to e and o but we can also do this at the next level so we have eo with a box around and then we combine this with l and put a big bigger box around i'm showing you this because this is a concise way to show the tree without drawing the tree so this might be convenient to quickly sketch this say in an exam right and then one more one we go uh we have our eo which is boxed together with l which again is boxed together with s and you can you can go from this representation of the tree to this nested boxes representation

11:03 by uh taking away the outermost box and then there's a left and the right part which have to be the biggest boxed parts so if you wanted you could draw a line but it's not really necessary so then the left box is what you reach with zero the right box what you reach with one and then you unpack those boxes recursively

11:32 so the result of this process is called the huffman tree which is nothing else but the code try for the huffman code so this contains all the code words for those four letters um

11:47 and if you want you could write down uh the table that we've had before remember for encoding it's more convenient to use this table so e has 0 0 0 as a code word l has zero one o zero zero one and s is just a single one and so if you encode lossless using this you would first put an l that's the zero one then you would put an o zero zero one that's where these come from and then you have two s's that's two ones and so on and so forth and if you were to decode this you want to use the try again as we've seen before in the other example so you walk down the try and find in the leaf what's the character it corresponds to

12:50 and what's interesting even on this tiny example if you compute the compression ratio as the number of bits we needed here turns out to be 14 divided by what you would need if you represent this this tiny alphabet with two bits per character the kind of the traditional or natural way if you have a an alphabet of four characters you use two bits per character then you would need 16 bits so even here you achieve a compression ratio of 88 percent even though this is a really tiny example so it seems huffman codes work

13:32 this is a remark that is essentially just relevant for assessments sometimes if you build the huffman tree there are ways where you have to break ties and either way would be fine it's just i want you to follow a specific rule so that you all arrive at the same result

13:56 for example even here at this first step there's the two elements they have the same minimal frequency so which way do you put them in the tree here i put e left and o to the right but i could have done it the other way around there's no rule in the huffman algorithm as i told you as i described it in the previous slide which way to go both is kind of fine there's a tie breaking rule for that which says

14:28 when you have two characters and you find the smallest when selecting the characters and there's more than two that have minimal frequency then we select the ones with smallest order in the alphabet that's the first rule

14:48 when we combine two trees of different values then we place the lower on the left and the third rule is what applies to this example when we combine trees of equal value then again we put we break the tie by what is the minimal symbol in either tree and so e comes before o in the alphabet that's why e was left okay so just practice these three rules uh we'll do this in in a tutorial question so you'll have uh ample opportunity to practice these that's just the the type breaking rule i want to follow for the course it doesn't make any difference you could you could use a different one the compression result would be the compression ratio would be the same but you get different codes and that's just confusing everyone

15:41 Encoding with Huffman code

15:45 so we've seen how to compute a huffman code uh what we haven't completely discussed is how to compress with huffman and it turns out there's this there's a few different options but the easiest one is you do a two-pass procedure over the text in the first pass you just keep a count of how often each character occurs after that you construct the huffman code as we've just seen it and remember you need the weights to go to compute the huffman code and so this first phase is about gathering the weights then we compute the huffman tree then we have to somehow encode the huffman code as well as part of the coded text and i omitted this here because you want to do this in a somewhat smart way to get good compression ratios but then it gets it gets quite intricate the practical solution is to further restrict what huffman trees are used so essentially you do another step after this i don't want to get into this detail uh but i wanted i want you to remember that you have to store the huffman code as part of the coded text it's not really something you can get around and then the second pass once you have your code you do a second pass through

17:05 the text and encode each character using its code word as we've seen in the example to decode this you read the code that someone encoded in the coded text again we won't talk about how to do this in detail there are simple ways and there are smarter ways that i don't want to get into and once you have the code you can start the decoding as we've seen in the examples you follow in the try down the path until you reach a leaf then you know the first character you jump back up and continue from there

17:43 i note something that will be reoccurring in other compression algorithms decoding is simpler or also faster than the encoding step and usually that's because in the encoding step we have to analyze we have to do this this recon stage where we have to find the redundancies in the text to exploit them whereas the decoding doesn't have to do that it's just told what to do

18:10 Huffman code - Optimality

18:15 okay before we finish with huffman i want to convince you that this is not just a random procedure that seems to work well on an example but indeed computes the best possible code as we as i said on the slide this is what we want i want to quickly convince you that this is indeed the case so we want to prove this this theorem i spelled it out here a bit formally but let's um digest it one and one bit at a time we start with a given alphabet and some weights then the statement is that the code that we've seen the algorithm for huffman's algorithm computes code words that minimize this expression same expression as we had it before i'll abbreviate with l of e because this will appear in the proof many times we sum over all the characters the length of the code word times the weight of that character that's what we want to minimize and we minimize this among all possible prefix free codes for this alphabet so as long as you insist that you want a code that encodes one character at a time huffman gives you the best possible way to do that

19:30 and the proof is is an induction over the size of the alphabet which is natural because the algorithm also is recursive over the size of the alphabet it recalls itself on a smaller alphabet so first of all we should do an induction basis if i have just two letters in my alphabet huffman will just assign one the code with one and the other code word zero and that's also the only prefix free code that we have so there's nothing really to do and huffman does what is claimed it computes the optimal code among one option so it works for two symbols now the induction hypothesis is suppose it works up to a certain number of symbols and now we look at the next bigger alphabet size sigma

20:24 and so this the sketch only shows the inductive step where sigma is at least three and now suppose we're given an optimal code this is a proof it's not a way to compute it so i get to say you give me the code and i'll work with it e star is an optimal prefix free code for my alphabet with its weights so because it's a prefix free code it can be shown as a try a code try and because it's a binary try there must be two leaves two sibling leaves in this stride that are the lowest level so no matter how how you stop the tree at some point there must be a note that has two leaves and that's at the deepest level otherwise there would always be a dangling a dangling edge left so we can always find these these two leaves x and y at maximal depth and that's true for any for any optimal code and now i'm modifying this code so remember a huffman code starts by picking the two characters of minimal frequency and makes those siblings the optimal code might not do that it might do something different so what we'll do next is we find the two lowest weight characters a and b as in huffman's algorithm

21:47 and we swap them with whatever's in x and y in the optimal code there could be other characters maybe the optimal codes found a smart way to put another character down there but if i swap these down if you look at the sum up here we make the encoding for a and b potentially a bit longer but whatever was in x and y before we make the code word potentially smaller because we move it up in the tree and this this net change is moving something up releases releases weight and moving something down costs us weight but the thing we move down has minimal weight so we definitely can only gain by doing this swap and since the code was optimal the new code must be still optimal it can't be better than optimum so we find the two characters a and b with minimal weight and we swap them with x and y and that still leaves us with an optimal code

22:53 and now comes the trick which is similar to huffman's algorithm we try to find an optimal code for sigma prime which is our alphabet where we take out a and b and we put in this new lumped together character and also assign the weights the weight of this is the sum of the weight of a and b

23:16 and so if if we have an optimal code for this sigma prime we can get an optimal code for sigma by just replacing this leaf for a and b with the little the little tree that branches out to um to a and b right so in in a picture uh there was some deepest note here where we have these leaves x and y

23:54 but this x and y lumped together and we can always go back and forth between these steps so this was for sigma this was for sigma prime the rest above this is the same tree so the only change i make in this optimal code for sigma prime is replace the leaf for a b again with this little tree that branches off to a and b

24:19 and so we assume uh we made the alphabet one smaller so we can use the inductive hypothesis that huffman computes an optimal code for sigma prime and so that together um gives us an optimal code for for sigma that is found by huffman's algorithm we exactly mimic how huffman's algorithm would have done the first step we picked the two characters from minimal frequency and put them together and so by the inductive hypothesis the code that huffman finds for sigma prime is optimal and the way it modifies it into a code for sigma leaves it optimal that concludes the proof for half men