Video 6-2: §6.1 Tries

0:03 i briefly introduced tries last time already and i won't get into the discussion of where the name comes from again this time but i want to discuss the the second part now a bit more detail so you should think of of tries as trees where a note has as many children as there are symbols in the alphabet so we often want to use these for restricted alphabets like in in this case

0:38 the alphabet is binary it's just the letters a and b now i i realize that there's also this dollar symbol and we'll talk about that in a second a note can have two children one for each letter in the alphabet it can also have just a single child as this one

1:06 and so the idea in a try always is if you follow a path from the root down the tree like the one i sketched here and you read the letters that you find on this path then they give a string and if that path leads to a leaf then this leaf should contain exactly that string so if you want to search for a string say we search for [Music]

1:33 we want to know whether aba is contained in this try we would start at the root the first letter is an a so we go with the a branch then we look at the second letter which is a b so we would go to b branch then we find an a so we would go the a branch and at this point we would like to see this dollar symbol but there's no edge with a dollar symbol so here we fall out of the tree and we can report that this string does not occur in the dictionary that is represented by the try otherwise there would have been an edge with that label so this uh what i tried to draw here this was a little uh lightning bolt symbol meaning that we are kind of stuck but really what it just means

2:32 it's not in the symbol table it's not contained in the set of strings story represented by this tribe now uh if if you look at this um just this alphabet a b and if there were no dollar symbols then we could have had this this string aba that stops in the middle of this internal node and for various reasons that's kind of a nuisance and inconvenient so we will usually make this assumption for tries that the strings that we store the set of strings is prefix free so what that means is no string is a strict prefix of any other string and then you never have this situation that you have to stop in the middle of a tree and there's two simple sufficient conditions each of which guarantees the prefix freeness and you can have either of the two it depends which is convenient if the strings are all of the same length well if there is same length neither can be a prefix of another a strict prefix so by strict prefix i mean it's a prefix and it's not the same string

3:43 duplicates are not not not really allowed here anyways so if all the strings are the same length they're prefix free another option in general if you have any set of strings you can make it prefix free by appending an end of string character and i will always use this dollar symbol because it somehow became customary don't ask me why at the end everything comes down to dollars but the only real significance is it is some symbol that doesn't occur in the alphabet and it's convenient to have something you can type quickly so i guess that might be the reason

4:21 and so in this case the set of strings might originally have been a a and aab and a b a a b stuff to pronounce and then we append this uh dollar symbol and then it was it became prefix free whereas previously right this aaa would have been a prefix of aab

4:43 all right um what else can we do with tries we can insert a new symbol into the set uh i thought it might be helpful to do this once on this example

4:56 because many of you have never seen tries so let's let's pick um a string that's not already in the set uh how about we do something short bb dollar is not not yet in the set so let's try to insert this

5:16 what we do for that is we start at the root and now we try to search for this string which is a natural thing to check is it already in the in the dictionary in which case we would not have to do anything we know it's not in this case but uh we still do the search so we follow this path because the first letter of bb dollar is a b

5:51 let's call this s then i can say this was the first character in s so the character at index 0. then i reach this note there's another character so i can follow this link which is the character at index 1. and now the original string was finished here but we added this dollar sign so i want to add another i want to follow another edge with a dollar sign now in this case there is no such edge but that's good because we wanted to insert so we kind of want or expect that there is a missing edge at some stage and so i'm just making a new one and then add the string as a new leaf

6:36 okay and that happened to be the the sec character at index two that's how you insert in a try you try to follow the path as long as that works and as soon as it stops working you add new nodes and edges until you have inserted the new string this could have gone on for longer it could have been necessary to add more nodes and then you would have created such unary paths of we always have just one one character for each edge so we might add many more vertices deletion is is also simple if i wanted to delete say

7:28 a a dollar i would start at the root i follow a a dollar here it is i found it um and so deletion would just remove this and all the unary nodes above it in this case it's just a single edge if we had deleted this one we would have removed these uh three three nodes so the the the leaf and all the the nodes with just a single child above it

8:13 and next i want to see if you digested this it's a long question and let's say search means is this query string contained in the set represented by the try or not

9:39 okay 20 ish we're reaching number of people in the room but there's a few at home maybe we had 40 votes for the other question that was open for a couple of days but i don't want to wait a couple of days

10:14 someone pointed out that for some of the questions i stopped them a little early and because i'm giving you points for participation that's kind of mean so i try not to do it

10:25 but i also try not to show you the votes and influence in your you in your decision to vote so i'm not sure what to do i could either just wait a little longer which may be the easiest solution but i'm such an impatient person or i could show you the results and the dangerous some of you might just change their mind or or vote after you've seen the results i think the second option is better given that i'm such an impatient person uh so i'll i'll just leave the the polls open so you can still uh vote but yeah you're cheating on yourself if you wait for that uh it's quite interesting that there so first of all i was mean again i put in a lot of different options because i thought um i'll throw in anything you could potentially come up with misguided as you might be initially maybe so there's lots of lots of different options but you see some peaks but nothing really decisive it's really interesting

11:29 all right so let's discuss this a bit um [Music] i'll show you the the answer here the the one that i have in mind is this one beta of q so roughly as long as the as the query string is i think it's easiest to illustrate on on the example again so what we do with a query string is we traverse down a path so remember we use this red example here

12:12 okay trouble with my pen again uh we used this red example to walk down the tree and after four steps which happens to be the number of characters in the query so q we noticed oh we fell off the path if we're lucky we fall off the path already earlier if we notice say we're looking for just a dollar no a's and b's in front then right at the root we would notice there is nothing a slightly more interesting example could be it's a fairly full tree but maybe something that starts with b a and then goes on for millions of characters i would still notice after the first b and then an a isn't in the try so i can stop early so i can sometimes decide that something's not in the try early to decide that it is in the try i always have to follow the entire pattern down until i reach the leaf

13:11 and so um that's that's what's uh what's meant in this case i should probably narrow it down and say a successful search because theta of q is an upper and a lower bound and i just convinced you that if the pattern is not in the try you might actually stop after just one or two characters

13:33 on the other end we can argue this is the worst case over the data so okay there's a lot of um a lot of slack in how you interpret the question precisely but the usual way is you traverse down the try and how many steps do you go down as many as the query string is long okay now i want to take a step back here and say why this is so cool and exciting because the try could be really humongous this could be an index over a huge collection of texts think of a search engine for the entire web but the time to query for whether something occurs in this huge collection only depends on the length of what you query so if you look for you're trying to find a username and you want to see if that's unique if no one came up with then you just type that in and in the length of that string time you know whether someone has already used that on any of the websites that there are the trillions of websites i think that's quite remarkable even though there are some some strings attached to it

14:40 and that brings me to this second question again n strings each m characters over say latin alphabet and now the question is how many notes could a try have in this situation and by notes i mean the the little red dots right from the picture

15:43 so how many people did we really have last question 22 no that's now really 44. amazing guys where do you all hide okay 33. okay almost there but i guess i'll just not lock the question so i can show you the results it's a little more

16:22 more telling this time seems to be a clear peak and this is also the correct answer uh so why is it n times m it is a little a little tricky but uh that is effectively the the worst case what you what you should think about for the worst cases you branch out as early as possible in the strings so they have all a unique prefix and then they continue as these unary node chains so how would this look like roughly there's our root notes and we have some

17:13 it's not a binary tree it's a node where every node a tree where every node has 26 children the letters of the alphabet and you keep doing this for a certain number of levels well how many essentially log n levels

17:32 oh yeah i didn't change the screen thanks and now touchscreen went off again so here's my schematic picture you have a note then you have login levels deep then you branch out to n notes

18:05 and notes at this level and then you go in long chains until you reach the leaves at each point and so you have this n minus log and uh

18:24 levels that you still go down it's these are all binary all unary notes so you have this m times um sorry that's m m minus log n and each of these chains is uh so you have n chains and each of these chains has length m minus log n and so you multiply out the dominant term is n times m okay

19:03 so that's only the unary notes in this in the second half of this long jellyfish or whatever the tentacles okay so again step back from this example uh is that good or is that bad it's terrible uh because that's a lot that's a lot of space it's a lot of notes and if the alphabet is big each of these nodes has to somehow at least allow to store all these children it could have whereas most of these of these nodes they only have a single child so it's a huge waste of memory if you say every node is represented with an array of 26 possible child links then that's 26 times the length of the of all the strings together so that's a huge overhead for storing this this structure so i don't i don't think google wants to store an index that's 26 times the size of the internet and that's not even taking all characters into account remember unicode was more like 150 000 characters so that's kind of a no-no so tries have this big problem that they're space inefficient

20:22 in at least in a way here this this seems seems inevitable in the tree structure like if you have to store these strings that differ in the first few characters and then go on whatever for a long time you have to some somehow store them so it seems you can't avoid this with this kind of tree structure

20:44 but there's a way out by modifying the data structure and that's what people call compact tries the the bad thing in the worst case example i've shown you was that you have these long tentacles of unary notes what if we avoid those all together so we whenever we have a unary node like in this case we remove that node and make it into one long edge so this unary node was gone it's consumed into one edge and became this edge okay

21:25 and you can do this further down so here as well long unary chain became just one edge this one now there's a few things we have to talk about first of all does this help second how can we still search

21:49 and part of the second is what do we write on the edges here we have only space for a single character but i have bb on the path down that i contracted and so the rule is we just use the first of these characters and we forget about the rest they're not really forgotten because they're still stored in this leaf so we can recover but we have to pay attention now if we follow down a path that we compare the right characters and that's why the compact try additionally stores these numbers in the nodes they tell you what index you're looking at next so at the root there's a zero which means you first compare the zero position the zero index of the string and if that's b you go that way now the next node says two which means you ignore what's at position one and you start immediately with position two

22:50 so what that means for a search if you were to search for uh b a b-a-b dollar it means you start here zeroth character here is a b so you go down here second character is a b so you go down here and so you found a leaf and you say yeah the word appears but not so fast this time you still have to compare the string that you're searching to what you find in the leaf because we skipped this middle character and in general we can skip many characters so you still have to at some point check those that's why we still keep the strings in the leaves but the the search can shortcut take shortcuts now back to the second point did this help what we achieved by removing all unary notes is that every note that remains in the compact try has at least two children and that helps a lot because it means we never have more notes than there are leaves that's the same argument that we've used for binary tree counting before whenever you add a new binary node or whenever you add a new node that has at least two children it adds at least one more leaf because it branches into two so you can plug it into some path

24:08 so it might take one leaf that was previously there and take it in one side but then it has another side so you have to create a new leaf whenever you add an internal node so if you invert that argument the number of nodes is at least is at most the number of leaves minus one

24:26 and that's the number of strings so now the number of nodes is order n now where n is the number of strings and not n times m okay we still store the strings in the leaves so we we still need this times n times n times m space but the constant factor is much better because the number of nodes is smaller we just store the strings we don't store something 20 times as big 26 times as big

25:05 so we'll usually work with compact tries because they're much more space efficient and usually also faster even though they're a little more complicated to do the searches and that brings me to the end of this first part if you want an inverted index you can use a try to implement that and get very efficient searches it's relatively simple at least conceptual you you need to implement a try there's tricky parts inside how do you represent the nodes you have you have basically two options you can say every node stores the space for all possible children child links that is a little based in space but it's fast another option could be each store each node stores a little dictionary of a symbol table of child links that uses less space but then you need the time inside the symbol table to search for the child link given a character so that's a little more space efficient but slightly slower and you can there's there's nice uh trade-offs there but it's overall a relatively uh conceptually simple data structure still and lookup is is almost as fast as it can get you just need the time to read the pattern but there are some downsides and these are not not really restricted to tries but to inverted indices in general

26:33 what if you are searching for just a part of a word and you haven't spelled it out might be less of a problem in english but languages like german where you can create compound nouns that can grow arbitrarily long

26:51 if you haven't seen that there's a nice youtube video maybe i'll post this uh which is probably a little tough to follow unless you speak german but the thing is you can make words arbitrarily long and you can essentially tell the story in one single word if your inverted index contains that word that's great but you can't search for parts of the word and the other restriction is if you want to search something slightly more complicated not just a single word but a sequence there's no easy way to do this efficiently in the try

27:25 you need to store extra things for that and then the second bigger disadvantage what if there's no words to start with if you have just some binary string that you would like to search for patterns there's no way to build an inverted index and similarly for these biological sequences dna or rna sequences the genome of the coronavirus all these things there's no word boundaries so it seems like this doesn't work well for this