Video 5-2: §5.2 Character Encodings

0:02 in the first part of of this unit on compression we'll try to exploit uh character frequencies and before we get there let's talk about uh encoding characters in binary uh from first

0:20 principles it's the simplest form of encoding and we need it anyways whatever kind of string we want to store in a computer we have to somehow encode it as bits and a character coding just means that we have a certain code for each Source character for for each character in The Source text so you can represent it as a function e that maps from The Source alphabet to potentially several um characters in the coded alphabet right it can be a code word that's what we call these um the representation for a single character is the code word for that character and in this case we'll usually assume the source alphabet is fairly big whereas the coded alphabet might be just binary in principle that's uh all of these things are called character encodings um there's two types that we distinguish one where all the code words have the same length and these are just simple to work with because you can uh you can compute where exactly the I character in the coded text starts um but there's also variable length codes that have better compression uh properties so we'll we'll look at both

1:36 briefly the most widely known example of a fixed length code probably is is this ASI character encoding stands for American Standard code for information exchange and is a little dated as I alluded to earlier it just has the Latin alphabet plus a few extra characters and that is it it has a lot of these weird control characters that's that's from the time of of needle printers where you had to tell the printer to go to the next line and all that so a third or so of the encoding that we use is completely useless because it uses movement commands that our devices don't use anymore but that's how standards are they tend to stick around uh aski uses seven bits for each character uh in files it's often added there's an e bit addit that is uh in the strict sense for aski is always zero um well just as an aside this this extra bit is then used for extended ask key so U there were extensions of this for various European languages where you had a few extra characters but it would still be 256 so not enough for many scripts anyways uh standard aski is just these these one 128

2:56 characters it's very limited but it's very simple that's the good thing about it so both encoding and decoding are as fast as you can possibly get you can do it by table lookup and it's it's very regular it will probably use SP um more space than necessary unless all the characters are equally likely to occur and of course it's super inflexible what if uh you invent your new favorite emoji then you can't represent it let's have a brief look at variable length code and also start with an a historic example namely um Morse codes so it might look that like variable length code is a new invention but that's not the case um and it also here um for for morse code I think people usually list things like this that's um a translation from standard characters oh by the way there's more than one Morse code this must be super confusing if you're like a you're lost on some remote island which Morse code should I use uh this is the international Morse code allegedly used uh where with ships um at C but uh don't quote me on this but this list tells you what character maps to what sequence of short and long tones right so you know

4:19 this for SOS and so on right uh what you often don't see is this is convenient for sending code but for decoding back from the patterns to the letters is actually not very convenient because you would have to find what does dot dot long mean again short short long ah it's a u because it's just enough for me to walk around there's another representation of the same information that's much more convenient for decoding and that's uh this kind of tree where yeah there we

5:12 good fire alarm still works so relieved uh so we we can represent the decoding as this tree where at each point you have to decide is the next thing you hear a DOT or a dash or a long uh and then you just follow along so if I have dot dot long I end up at U without having to search in this table so one piece one piece of information encoding and decoding sometimes can use different representations uh to be more efficient right what what to take away from this slide is just oh these these representations have different lengths so it's a variable length code uh quick fun

6:03 how many characters are in the coded texts in the coded alphabet so remember Source text is the thing you start with coded text is what you end up when you encode

6:36 I'll go back to that that slide I haven't listed anything here so Source text is usually the thing that is useful for humans right and then the coded text is something for computers to deal

7:00 with okay we have lots of votes in let me show show the distribution quite a spread um not so many picked the right answer um I know it's a tricky question so first of all the source alphabet isn't even specified explicitly but it's kind of listed here so the source alphabet would be uh just the capital letters and the digits and that I guess adds up to 36 but that's the source alphabet because that's a part that's useful for

7:49 humans the coded alphabet well it has to be the short and the long but there's actually a third character that's hidden it's not represented here which is a pause you can't actually use Morse code if you just use shorts and Longs and if you try decoding here you see why if I sent you dot dot dot I could mean three e or I could mean One S or one e and one I or vice versa so it's totally ambiguous I have to leave a pause between each letter that's not represented in the table but it actually is needed here otherwise the code wouldn't make sense it's not ambiguous at least it's not

8:39 unambiguous that's why three is the right answer for this one okay uh you're probably not going to be uh in the Navy so I'm not sure if you need to know Morse code um this slide is more important for us now interestingly utf8 still is a variable length code despite right this eight looking like it should be 8 bit each time it's a little bit misleading utf8 we covered this um yesterday or when it was uh it is it is an encoding from from the Unicode standard that uh is able to represent pretty much any kind of symbol um Humanity has invented 150,000 different ones utf8 is a specific way to encode those that's used for text files all AC Ross the web uh okay that's out of date I have to update the slide a keeps changing so it's more like 150,000 well and Counting is the important bit uh now it's a variable length code because it needs between one and four bytes for one character um it reserves the short code word of one bite for the asky characters because still by en llarge a lot of text is using those characters uh and the nonas characters um are encoded using using that kind of scheme so uh they're classified into different different um

10:13 categories and some of them are encoded with two bytes where you specify how long the sequence will be in the first bite by having two three or four ones at the beginning followed by a zero and then each subsequent bite has another code that wouldn't be strictly necessary but this is for making it um so that you can for an individual bite recognize whether it's part of a larger symbol or is an individual character so again the details of this encoding are not so important I just want to point out that it is a variable length code uh the benefit of of leaving ASI as part of this is whenever you use just the asky characters you don't actually waste any space you would have rounded up to 8 Bits for alignment anyways um but you can include arbitrary Unicode characters in the middle and those need a bit more space but if that's English text with a few emojis sprinkled in it's a very efficient

11:22 encoding now this has uh the fact that this is a variable length code has some consequences that most programmers tend to ignore most of the time and get away with most of the time um but not always if you have a text that's encoded in utf8 and you want to know how many characters there are you can't just take the length of the file or the number of bytes you would actually have to read through all the btes all the text and check uh which of the bytes are part of actually the same character and likewise if you want to jump to character uh 1527 in the text you don't know exactly where to jump to so uh the variable length code nature of this makes algorithms much more complicated uh which is one reason why Java tries to avoid this a bit by using utf16 instead so you have only very rare exceptions but even there it's a variable length code if you strict all

12:26 right so much for the uh real world examples for now um from a more theoretical perspective uh there's one thing in variable length codes that you can trip over and uh that's that's worth discussing a bit in detail because the various examples we've seen have different solutions for this uh say we have this kind of code uh it's a small alphabet and there's one code word for each letter so we can take a word like banana over this alphabet and code it like this okay and uh you see how how the this matches um the letters but the same coded text can also be decoded to another word a different Source text and uh that's equally valid in a sense under this code and in a sense this is uh this is indicating that the code is broken it's fundamentally broken because it's not Ambiguously decodable it's not un uh it's ambiguous it's not unambiguously decodable so we don't like that kind of

13:36 code um one indication that there might be a problem in your code is if one code word like one zero is a prefix of another code word because then when you decode you don't know whether you should stop and Report the letter you currently have or keep reading now this is not always a problem if you have this prefix property maybe there is a way to disambiguate it later but uh a sane sane choice is to pick a prefix free code that forbids that situation no code word is ever a prefix of another one that in particular this class of codes is also called instantaneously decodable because if you scan through uh the the coded text you can immediately uh report a character as soon as you've seen a code word you don't have to think ahead of time oh maybe I I'll have to backtrack or anything like this as you would like in this situation um as soon as you've seen a code word you can spit out the source character so often uh for variable length character encodings we restrict our attention to prefix free codes because they're fast to decode um and they avoid ambiguity by

15:03 now it it sounds like this is maybe a inconvenient thing to check whether a code has this property of being prefix free um but there's a a nice way to do it um by representing the code words in a try now uh a try is a data structure for storing strings that will come back to in much more detail in Unit 8 and this was the only the only place where re ordering the units caus something to be a forward reference that would have been a normal uh recall this from the last unit otherwise but I think it's fine uh for this unit just think of a try like in this example you have internal nodes and then you have different letters on the child edges and such a tree is representing a set of strings by reading the path down from the root to uh the leaf repres representing the string so for example 0 0 0 gives you the space character or 1 0 1 gives you e and that matches these code words now here's the trick if you ever had like in the previous example um like here this ambiguity where was it e n was one Zer and S was

16:27 111 one z0 if you had a situation like this and you were were to insert those into a try you would start by going to the right with a one then you would go left with a zero and then here you would want to say ah this is character n but then I also want to go right with another zero and go to S so you can recognize this this situation that one code word is a prefix of another one by running into the trouble in the in the tree that there's a letter associated with an internal Noe vice versa if we say all the code words or all the letters are only allowed in the leaves of this tree we definitely have a prefix free code okay that's why um we often represent these these codes as a code try because then it's it's obvious that they are prefix free is also convenient for encoding and decoding so if you want to encode something you want to use a table like this so if I want to encode an end right I just look up a is 01 n is 0 01 space is triple 0 then another a

17:53 01 another n01 and a t for one one but if I want to decode I don't want to search that table that's inconvenient instead I I use the try so we start at the root at the beginning and then we read following the steps so we read the first one then we're here we read another one brings us from here down there Anda we have a t so the first letter stops at this point then we start at the root again we read a one that brings us down here we read a zero brings us down here read another zero brings us down here ah an O and so on and so forth okay so for the next one you read 0 0 0 so you have the space then you read one 0

19:00 1 CH then uh 01 a and one one a t Okay so again two different representations of the code one is more convenient for encoding one more for decoding uh last last part of this just a general uh Point again if if you pick your favorite encoding for your characters you have to somehow tell the decoder the person who decodes what that code was otherwise they cannot decode so the question is uh kind of who watches the Watchmen who decodes the decoder um and there can be different choices it can either be a fixed coding that all all people in the world know for example mors and utfa are of that type you may have to tell your program that you're using that encoding but then it knows what it is because it's a a public standard or you can use um a way to store the uh character encoding as part of your coded text that's called Static coding where um uh we'll see an example next time you basically first send the the encoding and then the coded text using that encoding um and the last option is don't even have a fixed code that doesn't work with our character encoding so well but H you can do it with adaptive hman coding as a as an aside um here the idea

20:26 is that you build up the code along the way and you don't actually have to tell it up front the decoder just retraces your steps and will'll always arrive at the same point in between