Video 8-1: §8.1 Motivation, inverted indices, tries

0:02 so one more time welcome back to comp 5 to6 efficient algorithms and we start another new unit this is indeed my favorite unit so I hope you like it too uh because it it combines a few uh things that we've seen before and it has a few really remarkable Solutions where when when you see the problem first you're inclined to believe that it's not possible to do it as fast as as we'll see um but then along the way each individual step to supports that solution isn't really uh anything magic happening it's just combining all those things together where suddenly you make this huge leap U we'll see an example where indeed a famous computer scientist also uh conjectured that something isn't possible uh but he was proven wrong in the end um so it's on the one side it's it's a cool puzzle where it seems there's no solution but we'll we'll see the solution indeed uh it also is the unit where we get closest to uh to The Cutting Edge research some of the algorithms are from this Millennium uh which maybe doesn't sound so recent but um much of the things binary search trees and some of the very basic things these are among the oldest achievements of our field in computer

1:18 science whereas here we're getting much closer to the to the state-ofthe-art and that's another reason why I like this module it's also say one where there's lots of uh research still going on so what's this about uh it's about text indexing which is um a way of saying we try to prepare a text to be searched quickly and I I put this subtitle of searching in genomes uh because that's one one key application where this is used uh but also is a an example where some of the other SIM simpler techniques just completely fall apart and we'll we'll see more of that uh the goal is for you to know some uh some key methods for text indexing and these are listed here we'll we'll cover them in detail um there's a a specific uh data structure that is is just useful to know um which is used inside of these in some sense um as always I don't just want you to learn the algorithms by hard I want you to know uh what the performance characteristics are so that when you use them where you usually won't Implement them from scratch because there are standard methods there's good libraries available but you need to know how they behave to use them effectively uh same story as we had in

2:42 in many other units um and then going a little bit beyond what's already there I wanted to be able to combine things in in a simple way at least um solve solve new problems using similar techniques combining things from what we've seen what we will see in this unit

3:05 it's a fairly long unit but um we'll go through it step by step and we'll we'll start today with uh some background on these mysterious tries that I asked you on slido before the start and then we'll we'll also see the main star of the unit the suffix

3:26 trees let's first set the scene a little bit where where we are and why we do this uh this unit the problem that we focus on is is called text indexing and uh it's basically the same as string matching that we've seen in unit 4 uh but in this case there's an important distinction namely we call it offline string matching because the text is is static it doesn't change so uh it's it's similar as as in unit 4 we have a pattern that we're trying to find in the text but the text is fixed and given to us in advance so we're allowed to pre-process the text um spend substantial time there at least reading the text uh might take a long time think of this as being a really long text whereas then we're given the queries uh for patterns uh one after the other and uh we expect to answer many such queries so it it's it's well spent time to uh to pre-process the text thoroughly and then be fast on the queries that's the

4:37 idea all it's uh from from the terminology we can say this is more of a data structuring problem than an algorithm we're not looking for one single procedure we're looking for also a way to remember something from this pre-processing so we'll build uh what's called an index of the text uh well that's that's Latin for um one who points out your index f finger comes from the same route uh we I'll talk a bit more about this in a second uh there's many application areas that that use indices in one way or another uh the most prominent I guess are web search engines while they're still around and not replaced by large language models but even if they might be uh we'll we'll still have search engines in the classic sense because they're so much faster and cheaper um online dictionaries in this in the classic sense of a a word dictionary so you're you're trying to look up a word uh there you also don't want to start reading the the plain text of all the words in your dictionary from from scratch from the beginning whenever you search something and then all kinds of other uh search functionalities on websites I'll point out these genomic uh kinds of data data types or text types

5:58 uh we'll come back to those you can generalize it to uh also not just a single a single text but text documents and uh that's essentially these nosql databases use that kind of data model so doc document oriented databases um they usually also allow you to search and they build an index in the similar

6:27 way the first way uh to do this and uh a standard way that would be implemented in this last example if you if you use a document oriented database like mongodb uh they all do something like this uh they use an inverted index so the idea that comes from from books um a standard index in a book if you remember what that is that means this list of keywords at the end in alphabetic order and uh it tells you where you find that keyword in the book now these are usually done manually and it's a kind of a craft or an art to make a good index which words do you include you don't want it to be too long but you also don't want to miss important things so in uh in books this is usually done

7:16 manually there's one key assumption here which becomes comes obvious if you look through an index we only search for entire words so uh we the whole thing is uh is hinging on this notion of of breaking the text into words and depending on the language or depending on the situation that is that is often a useful

7:41 assumption so what does an inverted index specifically look like um conceptually you go through your text once you collect all the words in the text by splitting the text around some uh whes space characters or others um I'll ignore this more linguistic aspect of it that usually you don't want to um treat all grammatical variations of a word separately but instead you want to um stem them down to uh the uh well the word stem they come from so avoid plurals avoid uh other tenses and so on uh but we'll we'll mostly ignore this step um so it could be as simple as take your text split it by whites space and then build one large map from words to the list of occurrences so the list of indices in the text where this word starts that's exactly what we've uh what we would have found in a textbook at the end in a manually made index except that this is this is taking all the words we don't care if they're important or not we include and if we want so it's um complete list of words question becomes still how do we do this so the going through the text and breaking splitting it up at whites space that's easy and uh programming languages

9:07 might even have a function for that uh but how do we maintain this this mapping so that we can quickly find if I give you a word and that you can look in a in in the T in the table I'll tell you a suffix and you want to find that how do we do

9:34 in uh so if you haven't had a chance to vote on this you can do now but probably most most people will have cast their vote so the thing is called a try pronounced like in I try to be a good person um I'll comment on the atmology in a second as

10:06 well well I take it that um the majority hasn't seen it or if they've seen it it's not quite fresh so we should spend some time on it but let me go back one step here so the key question now for for inverted indices is how do we make this fast especially the query time but all that this really asks for is uh a standard symbol table same as we had so in a way it's just a symbol table where the

10:52 strings other than that um the conceptually the the abstract data type is the same we just need a mapping from strings two lists of in of indices so in particular we could use a binary search tree and it would work okayish uh it's not the fastest possible option but it's at least way faster than searching through the text from

11:24 scratch I just want to mention this in case you wonder why we don't just stick with it it's an option but we can do better and uh one way to do better is is these tries and the reason why they can do better is that they exploit that we have strings the binary search trees would have to work with any kind of data uh whereas uh we can now exploit that we have strings as

11:53 keys so the the name is traced to come from retrieval that's why it's spelled in this awkward way but then tree is kind of taken already and would confuse the heck out of people so instead we say try I don't know if that's a smart move but it kind of became the convention and so once something is a convention it's hard to to change I also don't have a really uh don't have a better suggestion I think so that's that's just what it is uh but you should you should try to be able to recognize when someone says try what that what that could be in essence it's it's a dictionary or a symbol table where the keys are strings as in the past will mostly ignore the values when rep when discussing the implementation of a symbol table U but you can handle it in the same way as as we've done for binary search trees and uh instead of doing comparisons between entire strings we'll work on individual characters so uh to make that clean and nice we'll make an assumption about the set of keys that we store you can work around this but for this unit it's not necessary it's the most convenient way to do it anyways uh it's also not usually a

13:12 problem uh so we make the assumption that our set of strings is prefix free so no string is a strict prefix of another one uh we've seen this before we've seen this when we discussed compression and wanted a prefix free code right halfman codes for example um and there I already mentioned the term code try if you remember um we've had the the term there and I told you forget about it for now we'll cover it later uh this is now

13:49 so and you'll understand in more detail why this prefix free was was the The key thing to require but uh there's there's two simple ways how you can enforce a set of strings to be prefix free even even if it wasn't from the start uh either if the strings are all of the same length then well nothing can be a a strict prefix of another if they all equally long so they're either equally either identical or or they're different at some at some character the other option is we append this end of string marker and we'll use this doller again again something you've seen before in in unit six um just an arbit create convention but when you append this character to all the strings you ensure that there's no prefix that occurs or anywhere earlier so here's an example of uh what this try looks like and uh the way the way you should imagine imagine using this is reading a path down to one of the leaves and then just depending all the symbols you find along the way if you do that here you find b b e a dollar and that's what's written down in the leaf and that's in general the construction uh we have internal nodes for example the root and they have

15:11 children which are labeled by characters so it's not like in binary search trees left is smaller right is larger nothing like that it's just all the characters in the alphabet can occur on these uh child labels child edges and uh the leaves store the entire string which is a little redundant but it's convenient for at least for drawing them here uh so you can build such a try by uh essentially um let me uh illustrate this with a smaller example with these two so if I want to try for just AA doll it would just be one long chain of of things like

15:58 this AA dollar if I take the other one with three A's and then the dollar this would be individual tries for just a single string and if you want to get the try for both of them then you fuse them as long as they share paths so these two are the root then they both go down with an edge labeled a so we fuse these two into one one node then we fuse these two into one node because they also are reached by the same Edge label but then things Branch off the one on the left goes down with dollar and this one continues with a so if I just wanted a try for for these two strings it looks like this you have two times an edge with a then you have the edge with dollar for a a dollar and you have another a and then the dollar or Triple A

17:10 dollar no credit rankings okay so few observations is um it doesn't matter in what order you insert things the structure of the try is predetermined just by the set of strings that you store that's unlike for binary search trees remember we always needed to talk about uh inserting things in a good order

17:37 question oh I forgot the B okay and this example is just for two different strings so if you had the B then there would be another Edge but uh I'm running out of space on the slide so let's let's leave it with the um smaller example here

18:03 um yeah anything else right so how do you search in a try the operations on a try would be as in a symbol table so you can for example check is a given string part of the set that we store and if it is then you can store a value associated with it and so to find a string let's do this example with a a a dollar and what you do is you start at the roots and you Traverse down the string by reading one character after the other first we want to see an a that's fine we can go with an a to here then we find another a in our in our query string so we have to again again take the edge with a we find another a so we go down here now our query string is is finished so we would want to see a dollar the end of string symbol but here there's no dollar so that that would be the point point where we can conclude that string AAA dollar is not part of the set of strings that this try represents whereas if you end it up in a leaf then you would have found that string and you can look up what value is associated with

19:25 it um let's also do an insertion just uh to show that um to show how this how this looks in a larger example um let's insert um a short string ba dollar so as as always almost always you you start by searching for this thing so we start at the root then we read the B so we Traverse in that direction then we read an a but there is no a at this point so we just add another child here with the new label a and then of course we don't have this note before so we also need to add uh the next Edge and we append a new um a new Leaf let me draw these a bit straighter okay that's how you insert things and uh you should you should think of of course all those lines are represented as pointers in some um in some object and so uh adding a new line is essentially setting a pointer to new object that you

20:59 bit so specific concrete suggestion situation we have this The Standard English alphabet or Latin alphabet we have n strings overall and they're equally long so we don't even have to worry about end of string characters uh but now the question is how long does a query take so you're querying with a string Q which is potentially shorter than m and the question is how many notes in the TR are

22:32 okay I'm not allowed to make it smaller to fit all the answers on the screen so we've had around 110 for the last question so I want to want to give you a second maybe let me go uh back to the to the example

24:10 all it seems most people are done um so let me show you the Vates and again they don't all fit but almost and so the right answer is is this one as many if you

24:34 found here's bit cleaner to see why is it Q uh you have to visit as many notes as there are characters in The query and that's pretty much it sometimes you're lucky that you can stop early um and the example is set up so that you usually don't um you can't usually stop early uh I guess so I guess it it it asks about the worst case and in that case you cannot stop early but uh the important bit here that I want to stress is uh the running time is only depending on the pattern the length of the pattern that you search determines how long it takes it's completely irrelevant how many strings there are and how long they are right and in a way that's that's that's remarkable because you would assume you have to somehow read them all or at least pay some login cost or something but no it's not not nothing like that uh if you look for a short pattern you pay exactly just this cost Q uh which will will be very cheap if Q is reasonably

25:50 small but let me ask a second question it's essentially the same situation but the question now is asking for a different thing it's asking about the overall number of notes in this tree so uh these little the question asked about these red blobs that I've drawn in this

27:37 uh let's wait till 60 but I see there's some somewhat reasonable agreement on on an answer yeah in case it matters you can assume that n and M are fairly big so it's an asmic result that I'm I'm looking looking for so here here are the votes and uh indeed the the majority vote is is correct um let me briefly explain uh why that's the case um well what's what happens in a worst case is that essentially all the strings differ very early on as as early as they possibly can so the try would look like this you have a a fan out of 26 for each of the possible letters I'm not going to draw this in its entirety and then each of those can again fan out 26

28:43 fold up onto a point um so you need to go down this for log base 26 of M levels then all the strings can be unique and from them on you just Contin continue with with long chains of nodes that end in a single leaf okay so you do this all the way

29:15 through so that second part it looks in the picture like this is almost equally tall but it's uh if you make M big enough then that's essentially M minus

29:30 this and this log M log 20 log base 26 of M if M becomes big that's a a Vanishing fraction so most of the uh all of the M all of the N strings it's the other dimension I could draw so the the number of strings that you have here is n n leaves in the end each of these n strings contributes M minus a tiny bit of nodes that it doesn't share with any any other string so if you just look at this uh rectangular part at the bottom this these tentacles uh they contribute essentially ASM totically they contribute n * m nodes and that's where this worst case comes from so what does that mean is that good or bad uh that depends a bit um but it it kind of is annoying in one way it's not as bad as it could be because n * m that's the over that's the total length of all the strings and arguably we have to store the strings so maybe it's inevitable to pay that space in this case on the other hand it feels very wasteful especially this worst case why do we have all these long chains they seem to be wasting space and they also seem useless from a search perspective

30:53 as soon as you're on this long track you kind of know there's only only one string that will be the match or it's not the match but there's only these two options okay so overall um in in the general case you may not be able to avoid space similar to that uh but we're not quite happy because it seems to leave potential on the

31:20 table and the answer to that is called a compact try uh it's a very very simple little trick that just gets rid of these these long tentacles at the end uh whenever you have in a try um a path where one node has just a single child you get rid of that node you eat it into the parent so here's the example from before um which was the or we call it standard try to distinguish them and it has a bunch of these um Parts where it has un nodes for example this one and so what you do do is you um you contract that into this Edge so that becomes just this this one Edge I'll I'll talk about the labels on the edge in a second but let's do a another example here so could be one of these long branches down to a leaf these will also compact down to a single edge here and you do this all all the way in the try so whenever you have a note that has a single child you contract it into a single edge now that loses some information we lost for example this character B here there's a single B on this Edge we can't really throw away that information uh but in in this case we

32:47 still have the entire strings at the leaves anyways so we don't really lose the information it's stored somewhere else uh but we we lose something else uh when you think about searching the try suppose we're trying to find

33:11 um whether uh ba is in the try okay it's the same example that we inserted earlier so if I do this in the standard try I move down to B and then oh there's no a so fine it's already over the game I know ba is not in the try if I do this in the compact try I find the B I missed that the second part of this Edge should be a b and I might conclude oh maybe I have ba a in this case uh there's no no way to continue with uh dollar so let me modify my example to B

33:47 A and then the dollar so same same story here B and then I already fall out of the tree so I know it's not in there if I do it here B and then it continues with a B at this at this later position I'm I'm skipping one character I might mistakenly think it's it's this guy and second problem I need to know which character I'm comparing so that's why in the compact try the internal nodes have these numbers which tell you what is the index in the query string you're looking at we didn't need that here because we always went down one Edge and we we knew we always go to the next index always plus one but here because we have these contracted edges we might jump over some characters so that's the two two caveats that we need they need to take into account in compact tries because we're Contracting edges we need to remember which index are we comparing next and we need to keep in mind that we're throwing away some information on the edges if we're doing it like this um it's more extreme on this case even where we just keep the first a and then all the remaining characters are just stored in the leaf

35:02 so that makes the searching in in the compact try a little trickier but not not overly more complicated let me do the example um here properly again with the explanation we start at the root and we have the indices of the characters we started the root we look into the root and ask what character are we supposed to compare next in this case it's character Zero so we look at the so the next Edge down from there is determined by whatever that first character is in this case b so we go from here down to that one now that node tells us index two is to be looked at next so we just look at this and we go down here in that case we find the leave and then we still have to do a last check where we compare the entire query string to the string in the leaf and in this case we would find that bab is not the same as BBB so we would have to declare the key is not contained in the in the symbol table in this case but that's how the search works so this uh slightly trickier is just these two things you have to check the index you're comparing and you have to compare

36:13 the entire string at the end because it might be that you jumped over some of the characters what we get from this is that all internal nodes have at least two children because the ones with a single child we got rid of what does that mean well that's a uh a classic little argument of counting in in a tree the number of nodes is at most the number of leaves because with every internal note if you think of starting with n leaves these are n little slots that we somehow have to connect into the root at the end and every internal node at least takes two leaves and has one parent pointer going up so I think of it as as this if you have four leaves they all stick a thing to the top and we have to somehow put something to this half pointer I take any internal note it has at least two slots going down and produces one up so at least it goes down by one and that's true for every internal Noe it's even better if they have higher degree then they eat more than one but always we get this inequality the number of internal nodes in the tree is at most the number of leaves the number of sleeves is the

37:30 number of strings so we get that the number of internal nodes is linear in the number of strings so we get Space n instead of n * m for the try we still have to store the leaves uh we'll worry about that later uh but the number of nodes is linear so linear in the sense of order n in the previous notation

38:00 uh let me also briefly comment on what we have to store for each internal node we have to store a number for the index that's fine that's a a single word uh and we may have to store all the all the outgoing edges but we we're assuming that the alphabet is is fixed and small so uh we can just list those all and um it remains uh linear but technically for storing the child

38:36 pointers we get a contribution of n * Sigma overall where Sigma is the size of the alphabet because I might have that many child edges for each note you can try to be clever on that but uh um with the general overview that's that's enough that's that's pretty much what you need to know about tries there's two two versions the standard and the compact one we'll often think in terms of the standard try for the algorithms uh but what we really want to store is the compact try because it's more space

39:15 efficient and you can use tries as they are as I've shown them as a an inverted index and they would perform reasonably well as long as this fits in main memory that's that's pretty fast and there are arguably quite simple compared to um other options and the lookup is is as fast as you can get because it's just depending on the crey length and no other contribution even if your index is the Google search index the entire web the search query might only have to look at as many notes as there are symbols in your query string and that's super small the Simplicity comes at the price that that you can't do some other General things um if you want to search for just a part of a word that's just not supported from the get-go we said split the text into words so we can't do that uh for search engines you would also want to search for phrases of several words and that's not clear how to do that easily or efficiently with the try in the way that we presented it so far but we'll focus on on the first problem that for some texts there is no such thing as a word boundary to start with and so the whole process of the

40:33 whole idea of using an inverted index seems to break down and two examples would be biological sequences so your your genome your genomic sequence the DNA sequence looks I mean this one I think I made it up but it looks something like this and if you have a binary file you might also want to search for patterns like a essentially a virus scanner would do and there's no words in there either so for that it seems we need entirely new