Video 7-2: §7.2 Character Encodings

0:00 Intro

0:02 with that said [Music] let's have a look at the first part where we look at character frequencies before we start with something more fancy uh let's look at the simple ways how we represent strings in a computer in the first place and this is all about computers work with binary but we like our alphabets with latin letters or whatever other scripts and so we have we need some way of going from these alphabets to a binary representation in the computer

0:44 Character encodings

0:47 and so what we need is an encoding function which assigns to each letter of our source source alphabet say the english alphabet some representation in binary now we can't just use one bit it will be a string of bits

1:04 we often have many more characters in our alphabets in particular if this is binary that's that's kind of always true one piece of of terminology we'll call the binary string that encodes a single character the code word of that character

1:23 and what we'll first look at is a fixed length code where every character gets the same number of bits assigned a code word of the same length for every character and then we'll we'll generalize this to cases where this is no longer the case

1:43 and here's probably the simplest most maybe was most well known uh fixed length code that's the the ascii character set a character encoding and it's just given you on the slide so here's a binary pattern and then behind the pattern is what letter it represents the sensible letters start around here so uh this is a space right that's why you can't see it and then there's some some punctuation marks the digits uppercase lowercase letters that's pretty much it if you try to represent some some other european languages or non-western languages you're pretty much out of luck there's two columns of these weird control sequences that comes from the fact that ascii was invented when people had needle printers and you used this these are tool to to are used to tell the printer where to move the printing head and things like that so many of them don't make a ton of sense anymore but we still use carriage return for find starting the next line a new line is there somewhere too uh well can't find it this is line feed well you will know text files on unix windows and mac are encoded differently in that the line ending the new line character is a different one in each case that's using some of those

3:15 apart from these weird control characters it's pretty much a mapping from the length the english characters to a bit pattern each character is mapped to 7-bit so you can represent 128 different things

3:33 Fixed-length codes - Discussion

3:36 what's good about these they're very simple and so encoding and decoding is almost instant you can you can do this very close to the hardware so it takes literally just one processor cycle

3:51 in terms of compression this doesn't really compress much it doesn't compress at all if you have a text that consists of just all a's it would need the same space as some complicated shakespeare play whatever is also not really flexible if you notice you need other characters you're out of luck and so you have to invent a bigger alphabet and find a new encoding and this has plagued much of the computing industry in i guess the 70s 80s before people started with unicode

4:33 if we don't want to upfront fix the code length we can do something else and that also is not a new idea we can assign code words of different lengths to the characters if we're a little careful and here's a very old variable length code that's the morse alphabet or as i learned there's different ones but this is the international morse code which has just the latin carrot latin letters and digits and so i guess you know this uh you can you can use this to send letters over like a wire or just by making sounds and then the dot is a short note and then the dash is a long one and so uh one way to say if if you want to encode then you want to use this table on the left where you find the next character that you want to encode and you produce that a sequence of of tones if you receive something at least in your head you probably want to do rather what this this tree says uh with is tree shows you start in the root and then you either see you either hear a long sound or a short sound and that makes you go into a different branch and then there's the characters if you end up at a certain point

5:51 then the characters tell you what letter that corresponds to okay it's quite typical that we have two representations of a character code where one is is convenient for encoding and the other is convenient for decoding and so if you were to implement a compression method you often represent the code in different ways in encoding and decoding

6:18 Clicker Question

6:20 a cute little little side remark and to wake you up as well what's the coded alphabet size in the morse code so this is testing the terminology and the nitpick of noise of morse code

7:09 we had an amazing 41 votes for the first question so pay close attention to which alphabet the [Music] question asks for okay we're getting close to the number of people from before

7:44 okay let me show you um what you've voted and it's a few more down there it was a big peak for 36 and some votes for pretty much anything um so if you if you read the question carefully it's about the coded text so we're not asking about how many characters can you represent not a to z plus the 10 digits um

8:16 but why is the correct answer three and not two because we have dot and dash that sounds like two uh the the thing in in morse it is a little cheating there's a third character which is pause end of end of a character if people use morse codes they leave a little silent period between the characters so that you know when one character is over if you look at this decoding tree you see immediately that you need this suppose i hear as one short sound how do i know whether i should continue from here down when i hear the next thing or whether i should stop and say oh that was an e there's no way for me to tell unless the other person gives me the pause to signal that this is the end of the character so morse code really uses three characters the two shown here and

9:16 a break end of character okay and yeah you need this if you have a tree like this that's another thing we'll come back to there's one more variable length code that i prop i bet you all know and i bet most of you don't realize its variable length but if you thought about it for a minute you notice it has to be

9:43 Variable-length codes - UTF-8

9:47 and that's a utf-8 or utf-16 is similar that's the standard way to code text files these days since at least 20 years i guess it took a while on the web to convince everyone but it's a way to represent text files that can contain any unicode character and remember there's some 150 000 of them although most of them are not used very often and so utf-8 is designed around the idea that most of the time people use just the ascii characters with a few extra characters from the full alphabet like all your emoji they're all just one code point in the unicode alphabet but you if you send texts maybe the fraction of emoji is rising but yeah you still by by and large on the text have more of the traditional characters at least that's the assumption utf-8 is built on okay it can represent any unicode character and there's more than 100 or more than 256 so the utf-8 8 stands for 8-bit

10:55 it hopes to represent most characters with just 8-bit but that would mean you can only represent 256 different ones doesn't work for all of unicode so it has to do something different and what it does is it uses between one and four bytes for one character

11:15 the ascii characters are encoded in one byte and there's a leading zero remember ascii seven bit add a zero in front that makes eight bit uh so that's that's fine for representing all those with just a single byte if you need any of the non-ascii characters then things are slightly more complicated and in a sense there's there's different regimes there's the unicode alphabet is broken up in different different ranges and depending on where it is so this is the unicode character in in hexadecimal

11:50 if it's ascii then it fits below this so 7 and f that's seven ones written in hexadecimal if you're above that but below the next next more for more bits then you get represented with two bytes and the x's are replaced by the actual uh code point

12:22 and so on so it's uh i know it's a bit tedious to read and you see that there's um a special way to signal how many bytes each character will take so if you read unicode the next byte if it starts with a zero you know it's just a single byte character an ascii one if it starts with two ones and then a zero you know it's two bytes that are coming and you have to puzzle out the axis to get the character and each byte that is not the first one is starting with one zero and here you have three or four ones to signal the small bytes coming uh what do you think do we need this one zero here to signal that this is uh why do we do this in the next bytes we could have just left it out because this already tells you how many bytes are following any guesses

13:30 so people do this for convenience if you jump into unicode text at a specific byte index and you see that the byte starts with one zero you know you're not actually looking at the beginning of a character but you're somewhere in the middle of the previous character so you know not to start to decode from there and instead you skip over all the bytes that start with one zero it's just a way to trade space for convenience you could have done a few fewer bits if you were just after compression but since this is also used as a way to represent strings in memory and compute over them it turns out it's more convenient to spend a few bits here to make access more more efficient all right so utf-8 combines the the space efficiency of ascii for the characters where you just need this english language letters um but you have a way to represent any other characters when they occur just using a little more space then for those so that's one example of a variable length code that you've probably been using all the time without maybe thinking about it too much

14:39 Pitfall in variable-length codes

14:45 the flexibility does come at a price if you use a code that has variable length code words you can get into trouble and i want to illustrate the trouble on an example suppose you have this this code so uh that assigns to the four letters in our alphabet some codeword now i can use this to encode a string like banana into this binary representation and you see uh the b corresponds to 1 1 0 so i write 1 1 0 then comes in a single 0 and so on and so forth okay i hope the encoding step is clear you just concatenate all the code words for the characters now if we try to decode this bit pattern there's another way to read it we can say this could be ba but then ss instead of na na because 1 0 zero is also the code for s and for um

15:49 n and a concatenated so there's two ways to decode that's not good so it's um it's an ambiguous code and of course if you look at this you immediately see that if you write an n a it leads to the same code as a single s so there's trouble ahead of for for sure but if i just showed you this code and asked you is this code good or not it might not have been completely obvious that it is flawed in this example of course it's clear but how can we how can we avoid creating codes that have this ambiguity we can't tolerate this it's not a way we can live with uh we want to be able to reconstruct the source text exactly

16:35 in general this is this is relatively hard but there's a simple sufficient condition what made this code nasty is that one code word one zero is a prefix of another code word 1 0 0. so when you decode and you read this 1 0 0 pattern

17:06 you start reading one is not a code word so i i can't stop one zero is a code word so i could stop but i could also continue and at this point the decoder doesn't know what to do unless you help him out

17:24 if by contrast our code has the property that no code word is a prefix of another code word then the decoder never gets into this problem it always knows as soon as it has found a code where it can stop and it's unique where what it decodes to and so if the if the code is prefix free which means no code where is the previous of another it is what people called instantaneously decodable so as soon as you read one code word you can decode that and go on to the next one and that also implies that it is uniquely encodable i just want to point out that there are uniquely decodable codes that are not instantaneous so you can come up with some complicated code where after 10 characters later you discover oh this is a dead end i shouldn't have gone this way but if i take the other way the other option of parsing this i would have succeeded you can't build something like that but it's not really any good it only makes decoding slow so we will not look at those we'll only look at prefix free codes but i wanted to point out that uniquely decodable is a weaker assumption than prefix free but we'll we'll live with prefix free

18:42 it's it's good enough and you'll see um in the next section what good enough means if we have a code that is prefix free there's a convenient way to represent it graphically and that's the code try so here's another another example of a code and this one is prefix free as you may try to check briefly no codeword is a is a prefix of another code word and an easy way to check this is to draw the try so you just take the code words and build the try off of this set of strings remember we talked about tries last unit at length so in the terminology of the last unit this is the simple try without any compaction no suffix trees right nothing fancy the notes in the tree just have one child for each possible alphabet character and you advance with one character on each edge if you do this for this code you will see that all the code words lead you to a unique leaf and that is the signal that the set of strings is prefix free and if you remember from the last unit that was pretty much exactly what we did there as well we enforced prefix freeness by adding this dollar sign at the end and here we say no we don't want to add

18:49 Code tries

20:07 another symbol to our alphabet we just want to pick carefully a set of strings that already happens to be prefix free okay so the way to check if a code is prefix free is draw the try and check if all the code words are in leaves

20:28 and the code try is also a convenient way to decode let's do an example if we want to encode this this string then we want to use the table up here because there we are given by the character what is the code word so a goes to 0 1 then n is 0 0 1 and space is three zeros and so on and so forth okay i think that direction is easy enough the decoding is a little more interesting so let's do this example at least we process this text left to right but we traverse in the try while doing that so we read the first one and then the second one and that brings us to a t so these two correspond to t and as soon as i reach the leaf i know i found the first character so i cut off these first two

21:27 and then start at the root again for the next character this time i see one and then zero and then zero so it has to be an o one zero zero that's the next cut and there's the o one more we started at the root zero zero zero so the next is a space

21:53 notice there was never ever any chance for going wrong there was no choice there was no ambiguity i just followed the path i ended up in the leaf and then continue at the from the root again okay and here are the examples in little detail just to check

22:15 so that's the way we want to think about character codes i'm only really interested in the prefix free ones so it's the same as saying i have a code try of the code words and that's that also happens to be convenient for decoding as a as a data structure to represent the code

22:37 okay um if in in general there's the question uh how can decoding know what code to use and that is a real problem if you think about text files and character encodings you may have seen websites where certain characters just render as some gibberish and the reason for that usually is that whoever wrote the website was still living in the 90s and used some non-unicode encoding of of the text characters and your browser being from 2022 thought everyone has to use unicode or utf-8 encoding unless they tell me something different and so it interprets the file as if it was unicode but it actually wasn't and so some characters look up wrong it doesn't work it doesn't break the ascii characters but it breaks some others the reason why this went wrong is someone has to tell the decoder what code was used to encode so that it can apply the right decoding and for ascii or utf-8 at least everyone in the world agrees what ascii is and what utf-8 is so it's kind of easy you just have to tell someone use utf-8 and you'll you'll see you'll know what's going on if we use a code like on the previous slide a custom code like this i have to tell the decoder what the code

24:03 was otherwise it wouldn't know what to do and it turns out this is really a question of the application whether the code is part of the coded text or not if the code is fixed and known outside externally that's what we use for text files and for morse if you send your sms by by beeping then you assume people will recognize that this is three short three long three short then we don't need to transmit the code we just assume everyone knows the encoding if we use what we'll call static coding where we use the same encoding for the entire text then we might have to transmit the code because the code is custom for the specific text but at least it doesn't change while decoding there's even wilder things that we'll call adaptive coding where the way you encode the character keeps changing while you're going in that case uh you you'll have to somehow tell the decoder how the code changes and this will often be implicitly in the code but this is what makes these codes a little more tricky now we'll see example of each of these um so it's just for the the distinction of the of the terminology fixed versus static so fixed coding means everyone in the world knows what

24:07 Who decodes the decoder?

25:33 that code is static means it's the same code for the entire text but the code still depends on the text and adaptive is anything else