Video 6-1: §6.1 Motivation, inverted indices, tries

0:00 <Untitled Chapter 1>

0:02 welcome back to com526 efficient algorithms and a new exciting unit unit 6 we'll talk about text indexing and that's it in a way a problem we've looked at before string matching finding a pattern in a long string but flipped on its head where this time we spent time on the text and then try to be really fast with the pattern it's also apart from this uh another area where we'll we'll dig relatively deep but we can build we can go there by little individual steps that uh where each step is is really easy to follow or is very fundamental but if you put them all together and you take a step back and say oof how do we get there this is amazing is some some of the the smartest and coolest ideas we'll see so I hope you enjoy this as well uh but we'll go slow and we'll we'll spend some time on it

0:56 Learning Outcomes

1:01 uh we'll cover some things that uh may have heard of so uh briefly inverted indices but then mostly suffix trees and their friends um if you haven't heard of those like then don't worry you will uh there's some generalizations of that I don't know I'm um I'm just listing these at the beginning so you can at the end refer back but some of them might not help you too much at this point as always I want you to know not just that these things exist but when they are good and what limitations they may have and we'll look at for some of these data structures mostly there are some nice tricks to use them for for more than the initial thing we designed them for

1:54 let's start with um setting the stage a bit for this um it's also sometimes called offline text search the idea is as in in string matching we have a text and we have a pattern we try to find in the easiest way exact matches exact occurrences of the pattern as a substring of the text but we pre-process the text and assume that we can reuse that index that we built many times so searching for many patterns

1:58 Text indexing

2:32 This this term index like index finger is is a very old one uh it's it has the word pointer in it which is really neat from a computer science perspective uh it's in a way um trying to to build something that points you to the right position right away and um

2:55 okay I think I'll have this later again but um traditional books uh at least monographs textbooks they often have an index at the end where they have certain uh key topics or key terms that are listed and then there's the pages on on which they occur that's very close to our task except that it's a bit more narrow and some person has to sit down to build the index meticulously the whole idea is much more more General all search engines basically do that uh if you if you look up some more specific databases pretty much everything now has a search and people expect that to be blazingly fast you type and you you expect within milliseconds to see some results it goes further than that these days you expect it to pick up mistakes you made in typing or you expected to find things if enough other people found the same thing by mistyping it the same way or using a synonymous word even it goes much beyond that for search engines uh we'll stay at the exact matching part for this unit all right another important area that during the pandemic has risen to much more Fame is is all the bioinformatics applications of this you can you can identify certain areas in genomes genes genes areas that get

4:24 translated to proteins and many other parts um now one one just as a fun fact if you want uh one week after the release of the sequence of the the Corona virus SARS covered II uh the virus genome uh one week after that moderna started basically putting their vaccine trials into production it took them one week to tailor their approach that they had developed to a new virus there's lots of computer science involved in that of course a lot a lot of other techniques and a lot of biology lab wet lab techniques as well um but there's uh a lot of searching going on for for pattern and comparing strings

5:17 Inverted indices

5:21 a classic solution is what in computer science we would call an inverted index it's inverted in the sense that uh a normal book has easy ways to jump to a certain page say and then you can find what's on the page and the inverted index says where do I find a certain word and it tells you where the page is so it's the opposite the normal normal book you go from page number to text what's on page seven and now you can ask I'm looking for this word on what page do I find it uh so that's a simple mapping of say a list of keywords to the pages where they occur that's in the classic book or of course computer science we might not just have the page but the exact index if that's one long string we can jump to a specific position in that string

6:16 there's some assumption that comes with this which is totally fine for many applications namely we know what strings are potentially searched for if you think about books again someone has to decide which words to put in the index and and the and all these uh like um very frequent words that also don't have a very specific meaning they are not usually included and if you would include them they would occur so many times it's basically useless and so um it assumes that someone decides what what words to put in and it assumes that there are words to start with so inverted indices usually go through the text somehow have a mechanism to split that into words say in the usual sense white space separates words for natural language text or say English text that would work fine and often we do an additional step that we won't talk further about it but there's libraries that do that for English fairly well automatically you go from a certain occurrence of a reflected word to the stem go from plural plural to singular go from conjugated verbs to the standard form you may know your grammar better than I do what the appropriate terms are in each case this is just to make sure that if you if

7:43 you look for go you also find all these other occurrences that are logically the same same word um now in terms of a data structure question how would you store this so suppose you have collected the list of words that you would like to find in your text and you're going through the text while you do this so whenever you find a word you know where it was because you're just reading that position in the text have you seen some data structure that would potentially be useful for that

8:26 yeah for example some binary tree uh in a way it's it's just a dictionary so you can use whatever whatever type of implementation for a dictionary you want it's a mapping right it's a mapping from words to say a list of indices of all the occurrences so for example a binary search tree would be one implementation and of course because you're all starting to prepare for the exam already you know that in the expected case at least that means logarithmic time or side node if you want that to be worst case you can use a balanced binary search trees binary search tree I haven't discussed how these work but I mentioned that they exist

9:14 and so okay just to make That explicit the keys are the words and the values are lists of indices okay as uh on a list of offsets maybe I don't want to use the word index again

9:34 so the starting position of An Occurrence of that word that's what it's what it's meant cool done so that's a short unit right there's a few things where we can improve on this

9:56 first of all we are having a very specific dictionary now I've already asked this question last time so let me maybe just pull it up again but you you will have answered it already and we already know what the result was namely a lot of you don't know tries okay you're changing your mind now you've looked it up

10:23 so uh why don't we stop with a binary search tree login is not too bad but we will be able to do better and the reason we can do better in this case is that we have a specific type of key we have strings as Keys the words and so we can exploit that this um this type of key is special to speed up the searches the simplest way to do that is called a try and so let me go over this slowly it's uh it's it's in principle a very harmless and simple data structure and it's worth understanding how it works and what the trade-offs are even though I mean the plain form we're discussing now nobody uses and I'll show you why in a second uh first of all it's a it's a dictionary data structure that has strings as keys I've already commented on this slightly uh slightly uh awkward naming convention it's spelled like in retrieval but pronounced like try to not have another word that sounds like tree um and uh it it's based on character comparisons with simple comparisons as we had it for for string matching now there's an assumption to make our life a little easier namely that all the strings that we store are prefix free which just means

11:46 no string is a prefix of another string you can either get this if all the strings happen to have the same length then no string can be a prefix of the other if they're all the same length they they they just can't be the other option is you make it a convention and say there's an end of string marker and um depending on on how much experience you have with low level programming this is actually not too far from what C represents strings like there's a specific character in The ASCII character data in the ASCII character set the zero as a character doesn't map to any real character it maps to the the null character and in in low-level C programs strings are represented as null terminated strings so you have a list of all your characters and then there's a special character saying you that's the end other languages represent strings differently they explicitly store an integer saying that's the length that's the number of characters and then there's the sequence of characters coming both exists now Java uses the version with the length

13:02 what does python do uh not 100 sure I would suspect that a string might just be an array at the end I'm not sure what they do I'm not sure I can look that up either way on the theory side both is fine it's not a real um restriction we can always add such an end of word character and you'll see this dollar many many times in this unit so get used to it that's just a way to write this end of word character it's a character that doesn't occur in strings too often it's common used to use the dollar for this uh and it's much more convenient to have this as some something you can draw as opposed to this null character that doesn't have a printing A visual representation but of course you could just replace this with something else here's an example of such a set of strings where we added the character at the end so they're all prefix free and now what is a try a try is a tree where we have a root and then uh the child edges of each root are labeled with one character so in this case the alphabet for these strings is just a and b so all the edges here are labeled with

14:25 either a b or the dollar we add that to the alphabet I'll just write it as this in this weird way to emphasize there's an alphabet where uh the symbol doesn't occur and then we add it to that it must be a new character right so okay we have nodes and we have edges with labels and what's the deal with the labels if you follow down some path in this in this tree let me Mark it maybe

14:58 then you arrive at some leaf and if you read allow the letters a b b dollar you get the string that's stored at this leaf uh the fact that we assume this prefix freeness means we always end in a leaf if we had one string that was a prefix of some other string then we would stop stop reading and still be in the middle of the try if we add this dollar marker we always end the leaf so that's a bit more convenient then we can always say the internal nodes are never the end of the string and the the leaves are representing the actual strings in the set so far so good that's also all uh that's that's a try or a standard try as you can see there are some notes that only have a single child and there sometimes is a long chain of such that just goes down to one leaf so um maybe already smell that there's room for improvement but that's that's one way to do it now if we wanted to find a string in this remember it's a dictionary we're supposed to be able to find a string what we would do is just take the new string we're looking for start at the root and Traverse pattern well character

16:16 by character following the edge that's labeled with that character if we ever get stuck that way it means there the key is not contained in the dictionary so one example um so we're we're checking is b b

16:46 I would start at the root I guess I have to add the dollar for for that to make sense so I would start at the root and follow down this path reading the first B I would follow another B reading the second B and now I want to read a dollar sign but there's no edge with the dollar so at this point I'm falling out of the tree and so the answer must be no because I couldn't complete my search had we been able to continue all the way down to a leaf we would have found the string and then again as for dictionaries for binary search trees the leaves will have another pointer storing the value that's associated with this the inverted index the list of all occurrences but that's just baggage we carry around so I won't usually draw it

17:40 so far so good that's tries let's see unlike some of these questions I had in the past um all you need to answer this question was on the previous slide and you could see the question Etc on the on the thing so um going back there

18:07 so this just requires uh thinking and understanding of the structures um I'm trying to test you on this I have 25 loads but how many people voted earlier 50. foreign

19:47 but I want to show the results already a bit so it shows you that there is uh there's some favorite questions uh some favorite answers but a lot of questions have got some votes

20:23 I know it's a lot of fun lots of answers if I keep this open for too long will you all gravitate towards whatever is the current majority I'm not saying that that's the right answer guys

20:36 in fact right answer is there so the um yeah you know you know it's not useful to change your answer now um the right the right answer is uh linear in the length of the pattern that we're looking for and let's let's briefly

21:07 examine that again on the example that we've just done we can just reuse the blue part so Q in this case would be three and by and large you look at three nodes and then you know you start at the root and then you read one character from the pattern that decides which child you go to or if you're already falling out of the tree um

21:36 query string occurs I didn't say that I might I might have to make this into a an O right but we could say worst case the worst case is uh it it has to go all the way to the length of the pattern you don't fall out of the tree early so you consume one character at a time and visit one more note that's why it's it's roughly the length of the pattern that you need you might get lucky and fall out of the tree early that can happen in the worst case you have to follow down and then you're either you can either stop in the middle of the tree but if you append the dollar sign you will always either find a leaf or you fall out okay so that's the cool thing about tries let me emphasize that like um outside of the concrete question search and tries is linear in the length of the pattern you're looking up it's independent of the size of the try even if the try is the entire web you can search for a tree with just fours four steps down this huge try it's completely irrelevant how big the try is I think that needs a bit emphasis because it's really amazing and it's completely impossible to do that with a

22:54 binary search tree it's only possible because we have strings here and we're we're doing a lot of pre-computation right okay so um if we're trying to find a pattern what determines the search time is the length of the pattern and only the length of the pattern maybe the size of the alphabet um I'm assuming that's fixed here

23:23 that sounds great now I have another question for you yeah we're making a lot of progress today I know just clicking on buttons it's the same setup but this time we're focusing on the space usage

23:46 again you have the answer on the slides on the phones maybe it's more useful to show the slide instead this one seems more clear to you so maybe I can can start showing

25:06 at the danger of influencing the rest of you we have a peek for this answer and that's the correct one so uh Theta of n times M for the worst case

25:25 what's more important for me is is to point out uh a how comes and B what does it mean so if I'm I'm going back to the picture the the worst case would be that essentially all strings look like look like this one long chain of unary notes single child notes all the way down to a leaf you can get essentially that if you have a lot of differences in the early few characters of the strings and then long chains of whatever strings that just have to go all the way down so by and large you have for each string roughly its length in unary notes and that brings the the total space to n times m the absolute worst case probably is if every string has a unique first character that only occurs in this string and then the rest can be arbitrary it would just be appended it would look like one one big jellyfish or I don't know a star uh dandelion okay enough weird Botanical

26:35 metaphors so is this good or is this fat uh it's a bit um depends on the point of view that's the total number of characters together in all strings and we need to store the strings somehow so in a way it's probably not easy to avoid spending n times m space times times the size of the alphabet in a way where log of the size of the alphabet will come to the compression encoding bits next time next unit the number of nodes is n times M now if you assume that we store the strings separately and then build this try on top just for searching then it's suddenly not so great then we have this additional so we just double the space or likely is that the constant Factor hidden in this is is actually a good deal bigger because these pointers these nodes have to be represented with pointers and they need to store the The Edge labels there's a lot of overhead going into this so probably this this constant factor is is much bigger than one so we're storing our our strings and then we're storing a lot more on top just to facilitate these searches that's not going to work if the size of the thing you have is is really big if

26:38 Clicker Question

28:01 you're trying to index the web you can't afford to uh store something that's a multiple times that size and luckily it's not not necessary for this so that's the the next jump in the evolution of these data structures from standard tries to compact tries and the trick is really not not that complicated uh if you if you look at the situation from before this worst case was all these long chains of unary notes hanging down uh and if there's a few in this example let's just get rid of only those and there in a way we we do that by just Contracting them so it's these two that's squished into one Edge that's this Edge uh and this this long thing here is is squished into just this Edge so the the trees you can basically lay them on top of each other you would still find how uh each node corresponds to one node in the in the standard try but of course now uh we're we're losing some information we just replace the long Edge that contains the whole string by A Single Character edge here so what how do we know that the second B is is there or how do we even know how long this chain of of things we now push together into a

28:13 Compact tries

29:25 single edge how long that was to recover that information the notes the internal nodes in the compact try store a number and that's the index in the string that the children compare so the root always has zero which says the first well index 0 character is what determines the child of the root but from then on it could either go one with one further up like in this case or it could jump to two where we say all the strings in our dictionary actually agreed on if they have a B in the first place they all agreed on the second place on index one okay

30:12 so if you have this compact try first of all if you start with the standard try I think it's relatively clear how to get to this compact one you identify all the chains of unary nodes and you replace them with a single edge and the the numbers in these nodes is just the original depth this node was a depth 2 1 2 so it gets a number two

30:36 uh maybe this is another example that's one two three and so it gets a three how do you search in the compact try if if you don't have this anymore if that's gone how do you do the same search as before suppose we search for uh b a b so we would start at the root that tells us compare the zero index character so that's a b we follow the edge that matches now we're comparing the second carry the character at position two index two another B brilliant so we go down here and we have found our pattern except that that's not the string that's stored because we didn't compare this index one character so in a way we can do the search as before but when we reach the leaf we still have to check the missing characters because we have skipped some we may have skipped some so we still have to check if these do also match otherwise it's a spurious hit

31:45 but that's the only that's the only caveat otherwise the search works the same as before it even got cheaper or it at least didn't get more expensive we don't visit more nodes we just got rid of some nodes so the same same statement as before holds you can search in a compact Tri independent of the size of the thing the only thing that matters is the length of the search pattern

32:12 and now uh as a computer scientist this is this is something that it pops up so often but I want to spell this out in detail if you have a tree and all the nodes are at least binary have at least two children then the number of nodes is never more than the number of leaves in that tree that's a it's a simple counting argument if if every node has has slots for children and consumes one slot because it has a parent pointer you can set up an equation how many internal nodes do you have how many leaves do you have by matching up the number of slots taking into account that there's the root that doesn't consume one so in a binary tree it's always exactly one more Leaf than internal nodes and in the general case if you can have even more than two children uh it's just an inequality the number of internal nodes is at most the number of leaves minus one and the number of leaves was the number of strings that's the number of strings our try stores so now we have a really useful bound the number of internal nodes these additional things we have to store to search quickly that's now linear in the number of strings not in the total length of all

33:27 strings so that's a bit more manageable so in in I should probably have put this properly so it's speed of n space independent of M which was the length of the strings

33:51 so tries are good because they can search fast but they might may use a lot of space compact tries make this the structure a little more intricate with these contracted edges other than that the rest works the same and they get the space down to at least linear in the number of strings so that's the two key bits and so let's wrap up with how well this works we can use such a try as an inverted index It's relatively simple to code that up uh if you want to be really really efficient maybe you have to spend some thought but it's it's relatively straightforward still and it's quite fast to look up well our original problem there may be some things left open if we if we just have a list of words and we're storing a fancy dictionary this is okay uh if we're trying to search for just a part a segment of a string just a substring what we want to find the occurrences of several strings uh after each other then the tries don't don't really help as much and even worse if we have biological sequences or other others more General binary data without a specific separation into words then the try doesn't help us because we don't know what to put into it

34:15 Tries as inverted index

35:20 is not so clear