Video 7-3: §7.3 Huffman codes

0:00 Introduction

0:02 in the next subsection i want to introduce the first non-trivial compression method and these are the huffman codes huffman codes basically exploit the observation that some letters some characters occur more frequently than others and we would like to take advantage of that what we'll do for huffman codes is that we'll fix a binary alphabet so we will only consider these it's possible to generalize huffman codes to other alphabets but the most the most important application anyways is to represent characters by binary bit strings in the computer so we will focus on this part and that means we can just write sigma for the source alphabet and drop the the subscript s now if you look at english text then you find roughly these um frequencies for characters i guess that is uh i think the numbers sum up to 100 so what that means is these are only the characters ignoring punctuation and space etc also spaces are probably even more frequent than e but even if you remove all the punctuation you see that this first column makes up the majority of all the text and then the last column hardly ever occurs just i don't know 1 in 20 characters maybe a bit more but not much so we would like to assign

1:39 to these infrequent characters a much smaller a much longer code so that we can use a shorter code for the ones that occur very often and indeed this is also what uh the the morse code did it had the shortest code for e if you remember and a was also short so the the frequent letters got a short a short code because people realized this very early on that this is just more efficient more convenient but the the task now will be to do this in a more um in a more well-founded way and this is what huffman codes can do

2:23 Huffman codes

2:27 so huffman coding starts with a source alphabet and weights now these weights could be frequencies from a given source text so we just go through the text and count how often each character occurs or it could be probabilities if we have some assumption that the text is generated randomly and we know roughly how often each character occurs how likely each character is to occur so what we assume here just for for making this formal is that we have a function that assigns a weight to every character in the alphabet in the source alphabet and that this is a non-negative number

3:08 the goal is to compute a prefix free code and by what you've just seen in the previous subsection that means compute a code try for this alphabet that minimizes the length of the coded text if each character occurs that often so what we do is we sum over all the characters in the alphabet we take the weight of the character and multiply that with the length of its codeword and so if we choose w of c as the number of occurrences

4:00 then this term is exactly the coded text length okay and that is what usually huffman codes are used like you determine the frequencies of characters and then you compute a huffman code for these frequencies so this is also where you see this is adaptive to the source text but it's a single code so it's the static the static character code case from previous subsection

4:31 Character by character

4:36 that's what i just uh said so it's a a best possible encoding if we want to encode character by character and want to be able to decode character by character if you think about it this sounds really ambitious right we want the best possible encoding for the text from this fairly white class of all possible character character encodings so knowing that kolmogorov called mogarov complexity is so hard that we cannot even compute how small we can compress something

5:17 we might we might feel that this is quite ambitious and doubt whether it's even possible at all let alone efficiently but it turns out in this case restricting to character by character encodings is a substantial restriction that makes a very efficient algorithm possible so the answer is yes and even more a greedy approach is enough so if you've seen an algorithm design class you might have seen the the greedy um the design paradigm of greedy algorithms where you're always taking a locally optimal choice and fix that and then continue that usually doesn't work for many more complicated problems this does not give you an optimal solution but here it actually does and in some other cases it actually does so what does huffman's algorithm do the first step is you find two characters that have smallest weights so these are the least free the least frequent least important characters so those are the ones where we're happy to give them a long code word because they don't occur often anyways so you find two of these the one with the lowest frequency the lowest weight and then the one with the second lowest weight and we will encode them using some shared prefix their code words will be the same except for the last bit where we distinguish them but they

5:37 Huffman code

6:51 will share some prefix u that we don't know yet u is still to be determined but we will fix for now whatever u will be we will encode a as u0 and b as u1 okay

7:07 and this choice or this decision restricts the choices for the other code words as we'll see in a in a substantial way but it's it's done by choosing the two lowest weight characters we never lose the optimality of the overall code the next step is now that we've decided how to distinguish a and b we no longer need to keep both characters around instead we create this this super character that stands for a or b and so i'll just draw this by putting a box around a b and we assign this super character the sum of the two weights because it actually stands for both a and b and once we've done that we made the input smaller we reduced the size of the source alphabet by one we combined two characters into one so we can now recursively apply the same algorithm and it will terminate because we always get rid of one character when this recursive call terminates when it returns it will have computed some code try for the remaining alphabet so for sigma where we replace a and b by the super character in particular it will find a code word for this a b character and that will be our u that's the algorithm let's see a small example in a second i just want to add one

8:49 remark here this description is very high level doesn't tell you how to do these things especially the first step how to find the lowest weight characters but one easy way to do it is using a priority queue so this is again jumping back to unit 2 fundamental data structures we talked about priority queues and binary heaps back then and this is one application for such a priority queue you initially throw all the characters into the priority queue using their weight as a key then the first step just executes two deletement calls on the priority queue that automatically gives you the two characters with lowest weights and step two where you compute this this sum of the super character you compute the sum of the weights you just insert a new character the super character a b and use the sum of the two weights as key and if you keep doing this you will as soon as the priority queue has only one element left you know that you're done and by keeping track how you paired things up you can reconstruct the tree but let's see that in an example

10:07 Example

10:11 so here's a small example we start with the source text lossless that means the alphabet has four letters a l e l o and s and we can count how often each of these characters occurs so we have one e namely here we have two l's we have one o and we have four s's so we initialize our priority queue this is the queue all the time you see what it contains um it contains the original characters and their frequencies and will contain the super characters while we're going so we first find the two with smallest weight that's e and o and now we combine them now what we will draw here are actually little code tries and indeed a single character is a valid little code try namely a single leaf that contains nothing else now in each step we take the two little coat tries that have the smallest weight in this case it's these two leaves and we create a new code try by taking those two the old two tries and we add a new root

11:29 to form a new try that contains both of these so if we do that here we take e and o form a new try out of these by creating a new root and adding these tries as children and the weight that this new try has is the sum of the original weights so 2 in this case

11:53 and that's how this algorithm continues we again find the two tries that have the least weight the two deletement calls here it gives us e o and l and we put them together by taking those two here they are these are the previous ones and uh adding a new root to it and that gives us the try for the super character eol

12:22 so maybe this is worth noting here in the old notation i would have said we create this super character eo okay in the next step we create a super character out of the super character of eo

12:39 and we add the l so we have this little nested super character and indeed the super character still encodes the entire shape of the tree but you can also draw the tree um that's a more natural way to represent it we have one more step to do there's still two tries but not much more of finding minima to do it's just two tries left so this is easy again we combine the two here are the pre this is the previous try this is the previous try add a new route and then we have a code try for the entire thing let's draw again the super characters just to make that explicit and that's a format that i also used for the tutorials so it's convenient if you already know it this was the previous this was the s from the other try and then we just draw a box around this again okay so that's the super character that represents uh this entire try

13:49 and that's the final that's the final result that is the huffman tree for this alphabet with this with these weights that is the code try for this huffman code and if you now encode lossless using this code again for encoding remember it's more convenient to list the codes as a table where you list the characters and then the code

14:26 so let's just briefly do this e is three zeros l is zero one o is zero zero one and s is just a one once you've done this encoding is fairly easy l is zero one that gives you this then comes an o that's zero zero one then come two s's so that's just two ones then we have uh another l so zero one then we have an e three zeros and two more s's if you correctly count then you would find that these are 14 bits that we use to represent lossless now whereas previously we had eight characters out of a a four character alphabet so we could use two bits to represent each of these characters that would even work out nicely because it's a power of 2 but that would need 16 bits in total so what we've achieved with huffman coding here is a compression ratio of 88 which is not too bad for such a tiny example there's a caveat though we would have to also transmit the code or the the try in one way or another so this is um i don't have that on the slide but i think we should add this as a remark

16:24 if we don't do that then we wouldn't be if we don't store the try as well then the decoder wouldn't know how to decode this text because it doesn't have access to the character frequencies now having said that you can decide whether it's more efficient to store the try or store the frequencies

16:51 generally um the tree contains a little less information so um usually storing that the try um the code is more efficient but if the frequencies are as small as in this case maybe it's more efficient to store the frequencies indeed

17:11 now when it comes to huffman coding you will notice that [Music] huffman's algorithm is is in a sense ambiguous or non-deterministic because it doesn't tell you in this step here

17:32 in case there are ties several characters with lowest weights it's not necessarily clear which one to take and also let me like let me make this green so just to signal

18:00 so in this first step um huffman's algorithm doesn't specify which minimum weight character to uh to use and here when forming this we could as well have used b first and then a now in this tiny example it looks like um it's obvious because a is before b so it would make sense to use alphabetic order but remember this is in general a whole code try so you have to find um it's not always so obvious which one makes sense so these are ambiguous any choice gives you an optimal code try but it's often convenient to fix a certain rule so that we all all get the same try then you can only transmit the frequencies for example and everyone executing the algorithm would end up with the same code and in particular for our module if should this arise at some point should someone be asked to do this in an exam say it would be important to follow these rules so we break ties as follows when selecting the two characters in step one we always use the ones that come first in the alphabetic order or the little try that contains the smallest alphabetic letter and you can trace the example that this is also what we did

19:46 so in step one we break ties by using alphabetic order and we use the smallest character in the entire try for step two when we combine two trees of different values uh when we combine two trees when they have different values we break ties by the value so we put the lower weight the lower valued tree on the left the only case that remains is if the two tries have the same weight then we place the one with the smallest letter to the left okay so this sounds complicated it's just spelling out all the potential cases where ambiguities could arise and this is one way to break ties in this case there there could be others that are just as sensible but please uh stick to this one whenever um it comes up in in this module uh you will have a an example on the tutorials for next week where we practice this a bit and that also will will follow this convention so just adhere to it

21:02 Sketch

21:02 now uh we've claimed that huffman's algorithm finds a best possible code but i want to briefly sketch also why this is the case so formally we have a theorem that given any alphabet and weights for that alphabet huffman's algorithm computes the best possible code and formally it computes a prefix free code that minimizes this l of the code words which is this this expression the sum from before summing of all characters their weight times the length of the code word

21:51 i want to sketch this proof um just very briefly because this is not the focus of this module um basically you start with any optimal prefix free code because it's a try it has to have two leaves that are somewhere at the lowest level and our siblings

22:19 so this is somewhere deep in the tree and these are at maximal maximal depth now because it's uh because it's a huffman code and a in a try um notice that we can always swap around the letters we can replace one character by another uh and it remains a prefix free code so what we can do is we swap characters that have lowest weight in the total alphabet and put them in place of x and y because we take lowest weight characters and we swapped them for x and y and these were at maximal depth that can only make the code better overall make this l smaller but because we started with an optimal code it means that we still have an optimal code so it's an alternative optimal code

23:17 now if we combine these two things and essentially replace this so we don't have these two but instead we put here the leaf x y that makes the alphabet one smaller and any optimal code for this smaller alphabet where we use the super letter yields an optimal code for sigma when i just replace these again because we could start here with any optimal code and we could modify it in that way so we can get uh whenever we with any optimal code for the reduced alphabet we get back an optimal code for the entire alphabet by expanding out the the xy supercharacter

24:12 and then finally because the recursive call yields an optimal code for the smaller alphabet by the inductive hypothesis that means we also get an optimal code for the bigger alphabet

24:31 that was a very brief brief sketch why half man's code is actually optimal it's very much following the the algorithm through and the the magic thing here happens because we do an induction i left out the induction bases if we just have a single character but that one's easy too because huffman's algorithm doesn't really have to do anything in this case so with that sketch um let's leave this theorem 7 1 for now and just conclude that huffman's algorithm always computes a prefix free code that has the minimal expected codeword length as defined here