Video 7-2: §7.2 Character Encodings

0:00 Intro

0:03 we'll now look at the first type of redundancies in source text that compression methods can exploit namely the character frequencies as a first step we'll look at general character encodings and these are the simplest forms of encodings uh and i as i said before whenever we want to represent a string over some alphabet we want we we actually need to represent it in in a computer in binary form so we necessarily need some way of encoding the characters of mapping the characters to binary strings and that's what these in encoding schemes do they separately encode each source character so they take each source character and map it with a function e to some code word so some sequence of bits in the ch in the typical case and we do this individually independently for all the characters and just concatenate their codes usually we think of the source alphabet to be substantially bigger than the coded alphabet so um that means we need several bits per character right there's no way you can lie away that informa that amount of information

0:15 General character encodings

1:29 another bit of terminology the uh this string this bit string e of c will be called the code word for c so that's the word that serves as a code for c in the coded text if you want and there's two we can distinguish two fundamentally different types of such character encodings they can either be fixed length of variable length and as the name indicates fixed length just means that the code words for all the characters in the alphabet are the same the code words are of the same length they have the same number of bits and any other code is a variable length character encoding

2:10 ASCII

2:15 there are well-known examples of fixed length codes here's one that i'm sure you've seen this is the ascii standard code for encoding all these 128 characters shown on the slide here you see this is a very old thing it's it's dated early 60s so a lot of these special characters are actually control commands for these needle printers that people had at the time but you also see there's the conventional latin alphabet in upper and lower case plus a certain set of punctuation and symbols i'm sure you're familiar with these this is uh what at the beginning of computer at the of the computer era everything had to be encoded in ascii and uh so what it does is ascii simply maps these 128 characters to a 7-bit code word each so for example the capital a is mapped to the number 65 in binary represented by one then lots of zeros and another one at the end five zeros in them in the middle uh that's a a simple mapping back and forth um between between these symbols and binary strings that's just enough for the english uh for english for text in english and some other well european languages um and that's that's about it so the the main downside is that this fixed code length is is very inflexible

4:05 there's no way to add new characters and there's no easy way to make the alphabet much much bigger without increasing the code words substantially the positive side though is because it's so simple it's as fast as it can possibly be to encode or decode individual characters and the the fact that it's fixed length means we can directly use ascii to represent the string as an array then the array is essentially a long bit array but i know if i need the 10th character i just have to jump to bit 70 onwards so

4:43 that's why encoding decoding is fast and allows random access so that means um i can jump to any any character right away without doing complicated address manipulations there's another downside unless the characters are roughly equally likely it wastes a lot of space and in particular you see with the exception of of a few of these these these control commands here are essentially useless today people included them at the time because they were useful then and now they've become totally obsolete but we can't really change the ascii standard without breaking a lot of existing systems so these are are sticking around and are not used for any good but they take up space because we have code words that are reserved for this

5:50 Variable Length

5:53 all right that's fixed length codes let's next look at variable length codes these are more flexible but that comes at a price they're also more complicated the idea itself is not at all a computer era idea it's it's much older and probably the most well-known is the morse code and so here here's the international morse code alphabet i've learned there's actually a different competing ones so good luck but sos is the same in all that i've found so that's the good thing and here's some a tree representation of the same thing so if you want to send an a you have to find it here so um well this the this tree here is is uh useful for decoding right you uh if you have dot dash then you know it's an a and if you have an a you know uh here dot dash gives you an a that's what you have to send that's for decoding all right um i suppose i suspect people have seen morse code or at least played with this a little bit in their free time if not it doesn't matter that much i don't want to ask a question about the little nitty gritty details here because that is indeed a little tricky so um what is the number of characters

7:21 in the coded text for the morse code and let me go back to just show the code without um much additional comment from my side i just want to give you a second to think about this

7:44 and yeah again this is not this is not very important for the rest of this module but it's a good way to practice the terminology and see if you're following this part so uh please have your vote on the question oh it's uh 13 people we used to have just 25 before maybe we can at least get

8:22 i see 15 votes now 16 17. great uh let me switch back and i'll show the results when we hit 20. is that right 21. great thanks a lot so here are the results and interestingly there's a lot of votes for many of the outcomes so that probably means we should potentially discuss this a little bit more let me state a few facts about this uh first of all the there are 26 characters in the latin alphabet as it is represented here there are 10 more digits so that makes a total of 36 characters in the source code in the source text alphabet right so i can start i cannot represent uh some some other punctuation marks etc and morse code there's just no code for it but there's 36 different symbols in the source text now i'm representing each and every one of these with dots and dashes and uh that sounds like um the right answer should be uh two because dot and dash is two different outcomes but the the correct answer is is three because what's not written here is you actually make a stop you make a break a pause between the

10:03 between the individual letters so if you send a you do dot dash and you make a pause because otherwise how would the decoder know whether you're actually sending an a so that you have to stop after dot dash or you're continuing and saying it's an r with dot dash dot okay so the trick here is morse code really uses a third symbol which is a blank between to separate individual code words all right um i think only one person only one person voted for this one so it was a trick question uh i'm a mean guy sometimes i wanted to trick you into this just to make this very clear if you have a try like this for decoding where it's valid to stop and it's valid to d continue that's uh something where an alarm bell should ring and we'll come back to that as well

11:10 Unicode

11:15 another variable length code that is a little more modern and maybe a little less well-known even though i'm sure you're all using it all of the time is is utf-8 part of the unicode standard so you will know just as a background unicode is is the modern way of fixing what ascii couldn't namely represent all characters in all languages of mankind not just the american version and in english and so it contains glyphs and letters for all languages on earth and a few others like klingon uh and all the emoji not to forget about those so uh well as of two years ago it was roughly a hundred and thirty thirty eight thousand i'm sure there's a few more by now so that's a large character set not one 128 but 128 000 and more so you would need a lot more bits to represent each character in this but utf-8 tries to avoid that for the still most common way still most common type of data namely english latin alphabet text or codes like on the web html etc essentially also use ascii characters most of the time with an occasional unicode smiley in between so utf-8 is a smart way to do this while usually saving a lot of space and what it does is it encodes each character

12:50 with one to four bytes depending on which one it is ascii characters use just one byte they start with a zero and then they have the seven bits from the old ascii code that i've shown a couple slides back any non-ascii character starts with one to four ones in the encoding this is also shown down here and that indicates how many total how many bytes in total make up the code for this character

13:26 so and you terminate this by a zero so you can either say zero only one byte you could say one one zero two bytes or one one one zero three bytes or four bytes and then the follow-up bytes start with a certain pattern to make the to make it obvious when you're reading this byte alone you know it cannot be an ascii character it's actually part of a longer code word okay so this is a smart little trick to help working to help algorithms work in utf-8 encoded text files

14:02 all right so um if you count the axis here you have a varying length of the actual uh code for the characters but it turns out that udf8 is is enough for the current unit unicode character set and a lot of additional new additions that might come so this seems to combine the best of both worlds we can for english text that uses the latin alphabet most of the time we get away with 8 bit instead of 7 but that's still pretty good and still we have the ability to encode all the other unicode characters as well of course then spending some more space on those

14:45 now uh what can go wrong with variable length codes maybe one one remark here that is in order if you have a utf-8 encoded text file you can no longer easily get random access to it

15:12 so maybe for text files this is not such a big deal but if you think of a computer like a programming language that represents strings you probably don't want to use utf-8 as the encoding there because how could you jump to the 40 second character in the text well you can only jump to the 42nd byte but how do you know that there's not characters before that that are actually used more than one byte so you you lose this capability of jumping to a specific character in the text if you use utf-8 for representing files it's not usually a big deal for representing strings in the programming language it might be a big deal and languages like like java have found a middle ground they use utf-16 and essentially ignore that sometimes the characters need several of these chunks that's just an aside in case you're wondering about how this could possibly work

16:10 Variable Length Codes

16:20 what can go wrong in variable length codes why do you potentially have to be careful here so here's here's the code for characters and let's encode banana with this so because we haven't done this before let's be super explicit about it i take the first character b i'll look up its encoding i put here it's code word one one zero and then i just append the next letter uh a has code word zero so i append the zero for a n happens to be 1 0 so i i write that a was a 0 1 0 again for n and another a that's a that's the coded text for banana in this variable length code it's obviously variable length because the code words have one two or three bits okay sounds sounds fine so what could go wrong the problem is the same coded text so 1 1 0 0 1 is the same text copied down also represents another source text because you can happily decode as follows you start with a b that's a so far so good then comes an a that's also good but then you could read the one zero zero as an s instead of n a and uh that's valid in this code but it is a problem because we really want to

17:46 have a lossless compression so we cannot tolerate this ambiguity here now remember this this looks similar to what the morse code did so if we added a third symbol that tells us whenever the code word of one character is finished this would fix the problem but we don't want to do that because computers are binary and adding a third possibility for each bit sounds a bit overkill so morse code essentially applied a hack to it that works fine in the real world if you're sending signals over a line you can add a pause and that's a reasonable thing to do it also helps humans as decoders for computers we don't want that so how can we avoid problematic codes like this we don't really want this this is a bad code how can we recognize this

18:45 we can recognize it because one code word is a prefix of another code word and in this case n the code word for n is a prefix of the code word for s and so whenever we read the code word for s the decoder is left wondering whether it should actually stop at one zero and decode it as an n or continue and decode it as an s so the easy fix for this is and this is what we will uh essentially always do in this class we forbid this situation and it turns out if that situation is forbidden uh no other problems are possible this ambiguity can only arise if we have this one thing is a prefix of something else

19:35 so we require the code to be prefix free no codeword is a prefix of another one and that means we can always instantaneously decode it if we see in the coded text a code word and that matches the code word of one character we know that ha it has to be the code word for this character and there's no other chance so we can parse that take that as the first character and continue so it's a greedy decoding and that's what we like that guarantees the unambiguous decoding

20:13 another way to represent this prefix free if you think back click click click unit 6 we've heard this before if you take all the code words and uh represent them in a try like so for this code here then you immediately see whether or not there is a problem if all the letters are in leaves then we're good there's no code word that's a prefix of another one if we end up like in the morse code with internal nodes representing characters then we have a problem then we would either need an end of word end of codeword character like in morse code or we in deep trouble

20:59 so it's good to think of prefix free codes the codes the character codes that we like as tries and that's why this has become known as a code try and has been given this name because it's it's used all the time

21:18 and you can think of uh this table that lists the mapping from characters to code words as a convenient way to encode and the try is a convenient way to decode so let's uh see that on the on a small example um if we want to encode this here a is 0 1. so we use the table to find the code word for a then we find the code word for n001 and we just append that then the space is three zeros then a 0 1 etc etc

21:56 we're decoding the table is inconvenient you would always have to search in here the try is much more convenient because now you can just walk down the try reading the coded text so we do that the one brings us here the next one brings us here and then we know oh it actually starts with a t so these two are t then we start at the root again we follow the one zero zero that leads us to an o and then we start at the root again 0 0 0 that brings us down here to the space and so on and so forth so if if you finish this you find these two codes

22:45 so the code try has has two main purposes it's convenient for decoding it's an efficient reversal in this try is an efficient algorithm for decoding second cool thing about the try is it makes it very obvious and explicit if a code is prefix free or not

23:05 Code Regimes

23:13 we've designed character codes and at this point you have to be a little careful in what exactly is done with this code and there are three different uh regimes here uh we can either have a fixed code like morse or utf-8 where you essentially assume the entire world and everyone who's working with this code knows the code knows the code try knows the the table that maps characters to code words if that is the case you don't have to transmit the code itself because it's already known by the other side

23:56 a different a different regime is static coding where static means that the code stays the same for the entire message that you sent but it's not known a priory it's constructed based on the source text so the code depends on the message so that means you have to transmit it as part of your coded text okay so you would first the coded text first begins with a pre with a a preamble if you like that says what comes now is encoded using this code and here's a code for the code we'll actually do this for huffman and the third regime is adaptive coding this is also you will have to send the code in a sense as part of your coded message but to make things worse the code also depends the code also changes while you encode so the code is not a fixed thing as as in the static case but it keeps changing and we'll see with lsw an example of adaptive coding