Video 7-3: §7.2 Character Encodings

0:04 we continue our discussion of character encodings we've seen fixed length encoding variable length encoding and some practical examples now I want to point out that in general you have to be a little careful with this these being the variable length codes because you can get into trouble and what the trouble looks like is shown on this example so there's um an innocent looking encoding for a small alphabet here you have a code word for each of the letters all fine so you can encode something for example the string banana would correspond to this bit string the problem then shows up with decoding you can take the same bit string and decode it to an entirely different Source text that's not exactly what we wanted we wanted lossless compression so we should always be able to get back the precise Source text we put in if you just look at this code at the set of code words without thinking about deeply this looks fine right they're all different so where's the problem uh in this case uh the problem simply is you can decode some coded texts in multiple ways that is the core problem that's what we really don't like and in general you can think about how you can recognize if a given set of code

1:28 words has this property we'll fix uh we'll focus on a simple sufficient condition so a condition that's easy to check and if that condition is fulfilled the code is fine but there may be other codes that are still working fine if you look very close that do not satisfy that condition I just want to make that clear so you can design some some more complicated things and they might still work but we'll we'll execute those

2:59 okay let's um a what we want in this chapter is just the string and there's no semantic behind it if it's two different strings they are different and so uh I don't want to combine them in that way now sometimes that makes sense but then again I would say you're just shifting the problem you're saying I'm actually encoding something else namely the equivalence classes over strings maybe I don't have yet a convenient way to write them down as a single string but there there may be one lurking in the background now let me let me make some progress on the material here that you can do the tutorials and the last class test after today ideally um

3:47 um after today when we cover I don't want to release a class test that has material we haven't covered because then I can already see the 10 emails hey I don't know what to do on this yeah of course we haven't talked about it so I'll release it once once we have covered all that's uh that's needed probably the latest is to move to front so uh we might just not make it today maybe you'll have to wait till Monday

4:12 so here's here's the simple condition I promised that lets you easily decide if such a collection of code words is valid and that's um if they're prefix free same condition we had for tries before so the problem in this code can be seen as there's one code word this one that's a prefix of another one uh not including the second zero and so when you see uh one zero zero you're not quite sure at this point if it's an S so if it's a b it's the beginning of something else if we forbid that we definitely don't have this problem if we always have uh a code word that's not a prefix prefix of something else as soon as I've conf finished reading a code word I can decide this is decodable and I can move on I will never ever get in some dead ends so if we have a prefix free code then it is instantaneously decodable what that means is what I just said you read the code word and you can immediately decide that is this letter and there's no no backtracking needed of some sort and that implies that the code is uniquely decodable there are other uniquely decodable codes but we won't care about them

5:31 another convenient consequence of being prefix free is as I alluded to we can represent these code words as a try and that will be convenient for two ways one is you can just draw the try of all the code words to check if they're prefix free if you end up with something in the middle of an internal node or inside of an edge it's not prefix free and the other the other reason why the code try is convenient is for decoding you need exactly such a representation so let's um do a different example this is a code that is prefix free um and here's the the code try for that so you can follow any path down you never stop in an internal node you always continue to leave and then you find uniquely which letter that code word corresponds to

6:19 and so um well here's an example uh down here for encoding it's not so interesting for encoding you really want this table where you can look up quickly for each character what is the code word so a should be 0 1 and then n should be zero zero one and so on right you just uh concatenate all the code words and so here's what that looks like and for the decoding should put this on two separate slides for the decoding it's really much more convenient to work on the try so you start at the root of the try and start at the beginning of your coded word and now you just read along I read a one and I read another one and then I'm at the leaf level so I know the first two ones correspond to a T then I'm done with one letter and I start at the root again do the same game over start at the root you read a one then I read a zero and another zero so I reach one zero zero and that's an o and so on and so forth so zero zero zero the next three letters lead us to the space and one zero one gives us an e

7:43 uh okay we might as well finish the two and then one one was t okay and here's the uh the nicely typed version so again two things are convenient about prefix free it's always uniquely decodable you can draw the code try to check and you can use the code try to decode conveniently

8:08 uh and the uh the table of code words is for encoding now once uh once we've talked about various codes in particular these these ones which are something I just made up for the example the question upon decoding is how do I know which code to use and there's many options I mean what we're most what we're often used so far was a fixed code like the ASCII code it's a standard so that means outside of your specific application someone decided this is the code that we'll use and then everyone knows what to do hopefully and the same for Morse codes although there were different variants as I mentioned that's one option a fixed coding means you somehow externally know which code to use static coding is a subset is a generalization of that fixed coding is also static but static means the code could be part of the message so the the first part of the message tells you what code to use and then the remainder of the message is decoded using that code so in a way you have to decode the decoder first and we'll see an example in terms of Huffman codes for that uh there's also the option that there is no fixed code that stays the same but

9:35 instead the code keeps changing while you decode that sounds confusing and wild but you'll see an example later it's it's just an algorithm that implicitly constructs a code as you keep going as long as encoder and decoder do the same thing in it at the same position in the text have the same code in mind it works fine right it's uh it's not a problem that the code keeps changing as long as at any point in time you know what to do and it's the same what the encoder has done