Video 6-1: §6.1 Motivation, inverted indices

0:00 Introduction to unit 6

0:04 in unit 6 i now want to talk about text indexing that is the string matching problem in reverse where we do pre-processing on the text and assume that the text is given as opposed to pre-process the pattern and this will turn the problem on its head it will make very different solutions and trade-offs possible and it's definitely one of the areas that has had a huge influence on on practical applications in particular in bioinformatics where this is applied to whole genomes to search very quickly and efficiently for certain strings or certain patterns and last not least to find matches of small fragments in a larger genome this is effectively what also many pcr tests build on partly so you're probably all profiting from from [Music] algorithms in this unit with that advertisement let's start into it it's it's also one of my my favorite topics in this class it's beautiful it's impactful it's deep and somewhat mind-boggling a little bit as well but it's very approachable if you do it step by step and then if you take a step back at the end you see wow we built this amazing machinery that can do this these magic tricks that seemed impossible at first but you can do it step by step and it falls into place at the end

1:43 all right it's uh just very enjoyable i hope you agree at the end of this unit 6. the overview of this unit is um i'll talk a little bit about the the underlying uh problems that we address here and then we'll talk about our main star in this unit the suffix tree that solves many of the problems at least conceptually we'll look at some of these in the applications and then probably after easter we'll continue with how to construct suffix trees and that will lead us through longest common extensions which are used for some more applications lead us through suffix arrays and lcp arrays

1:52 Text indexing overview

2:33 and then the combination of these understandable linear time algorithms to construct suffix arrays will then lead to the final solution um if that sounds a little abstract don't worry too much we'll go there step by step and as a first step let's look at what this problem is all about so what is text indexing it's also sometimes called offline text search we're still in the realm of the by now very familiar string matching so we're trying to find a pattern in a text and again the pattern has length m the text has length n this is all exactly as it was in the previous two units what has changed now is a bit the perspective we think of the text to be fixed and the pattern to come well we think of the same text to be queried after many different patterns and this is now moving the problem closer to a data structuring task instead of thinking about algorithms how to do one shot queries you're given here's a text here's a pattern now find the pattern in this text or show that it doesn't occur uh we think about here's a text you're given this up front you can do you you can do your magic with it and then afterwards i'll fire

2:54 Concept of inverted indices

4:00 queries at you one pattern at a time and you have to tell me where it occurs in this text okay you might you might know that this word index is used in many different places it's really the the index finger right is also where this comes from it's it's just pointing traditionally in books you have an index at the end a list of all the words or concepts and they point back to positions in the long text in the book so this is this is not different from that but we will approach the problem in slightly in a slightly more general setting as you will see there's tons of applications that under the hood use use string match use text indexing in one way or another web search can be seen as as exactly that though they usually don't have one contiguous text but documents of of smaller texts you will see that this is essentially the same though dictionaries in the traditional sense well an english dictionary you want to find a word quickly you don't want to flip the book these days anymore same for other bigger databases and as i mentioned the bioinformatics applications

4:09 Dictionary data structures

5:29 the traditional way to do this in books is an inverted index in the terminology of computer science and this is simply instead of um instead of having the text where all the words are listed in the order they appear in the text which by the way is how we want it if we want to read the book an inverted index takes all the words that occur and maps that to the page in the book where they where they occur and that could be several pages usually okay there's an assumption behind this and this is also a limitation of the traditional indices in books you only find in this index what someone care to put into this index and especially in printed books you can't make the index arbitrarily big and the underlying assumption here is that we only search for entire words um sometimes this makes sense for natural language text this is often what you want

6:34 if you search for a word it's often not so helpful if you report matches that are just um within another word uh and then um this this works fine

6:48 uh what we do for this is you're given the text then you split it into words for natural language that's often clear how to do you just take split the text at white space in practice you want to go a little further using the fact that this is say an english text you want to reduce words to their stem so that if someone searches for cats if someone searches for a cat it also he or she also finds occurrences of cats or other related forms this is what users expect but we will not dive into this part

7:31 usually these are heuristics um based on the language and it's it's fairly well understood how to do this for english it might depend on on the language how well it works what we still have to do is store a mapping from words to the list of occurrences and this is this is a now an algorithmic or data structure question that um you can make sense of already and uh in a sense this is this is just like a dictionary

8:17 so you have keys and you have values right the keys are your words and the values are list of occurrences which you cannot see uh the values are is a list of occurrences of that string in the text that is totally doable but if you if you implement such a dictionary with a binary search tree search would still take logarithmic time in the number of words that you store now i just give this a rough back of the envelope calculation if you were running a web service like google search the entire web and you had a dependency on the size of the web in your search uh guess how well that would work that's definitely too slow in that scale of data it might just be acceptable for some other applications but it's it's definitely not the way to go um in in the general case and the reason why this dictionary approach if you use a binary search tree so maybe this is

9:45 worth noting a binary search tree would work and that can be too much okay and how can we possibly improve on upon this we can make use of the fact that the keys are not arbitrary objects but strings and we can do more with strings than with arbitrary objects and now i want to see if you know this term tries spelled t-r-i-e

10:14 Tries explained

10:30 just so that i know if i have to explain this or not again yeah i'm trying to make the answers a bit um more energetic and not too dry but yeah it's totally fine if you haven't heard it it's something that sometimes is taught in undergraduate algorithms or data structures classes in computer science but then a third of you haven't ever gone through an undergrad in cs and even those who have um might not have seen tries in great detail they're not in the in the total must-have of data structures which is a shame but that's what it is okay we have our usual 25 almost uh okay now we got it so you see the results it looks like we we should definitely spend a little time on looking at what tries are so what are tries

11:44 at the at the basic level a try is an efficient dictionary where the keys are strings this is exactly what we need right we need we need a dictionary um where our keys are the words in the text and we can associate some some value with that the weird name someone found it nifty to use retrieval to retrieve the keys and take this this infix this this substring as the name but then because tree from retrieval that sounds like tree like the tree

12:22 and uh well i mean it's not at the end a try is a tree but um it's they don't want they didn't want it to sound like tree otherwise people would be confused so it's pronounced try uh well that's what it is um it kind of cuts it it's stuck like this and it's a good it's a short name it's maybe not very logical but uh that's that's maybe not too bad it is a tree though um uh this is what i what i said here it is a tree um but it's not a binary tree and it's it's used in a slightly uh different form maybe i'll show you the example first this is an example try there's a root note this is like in binary trees now this one is binary but that's because the alphabet is binary and it's not entirely true because there's also this dollar but i don't have a ternary note i do have notes with only a single child in general a try node can have as many children as there are letters in the alphabet

13:36 in the basic version a try simply says if you want to store a string bba you have to make sure that if you traverse the path from the root to this node to this key the labels of the edges spell b be a dollar exactly the string that you store that's in essence what a try is you make sure that every edge is labeled with a symbol and if you read the edge labels as you walk down to a leaf that gives you exactly the string that is written in the leaf now uh there are a few catches in caveats

14:17 to make this work we assume that the strings are prefix free so that means no string is a prefix of some other string if you had this if a prefix if there was a string that's a prefix of another one it would end in the middle of the try and uh that's inconvenient for various reasons um you can handle this in different ways uh the easiest is to say uh we assume that the strings are prefix free and that's for example true if they all have the same length then no no string of the same length can be a prefix of another string or if we append a special symbol and the convention here is to use this dollar sign so again you see things are dominated by americans we use this dollar sign always in this in this unit to mark an artificial end of file character

15:15 it's important that this character does not occur as a usual character in the alphabet so if that ever happens you have to find a different make it a green dollar or whatever the assumption is you start with strings over some alphabet sigma and then you add the dollar sign as a new one and by making this the last character in every string appending it to every string you make sure that there's never a prefix never one of these is a prefix of another one because that would mean the dollar occurs in the middle of some other string and we we didn't allow that

15:56 so here's some more uh more systematically what this example shows is here's a set of strings over the alphabet just a b so um don't have this on the slide but it's um worth noting that the alphabet is just a and b we append it to all the strings the dollar sign and then we constructed this try exactly by well every node every node here can have a child labeled a label b and label dollar and say if we added another string here that's just dollar we would indeed have this

16:39 as a new leaf and a new node and then you would have a ternary node where you have three children okay because the the edges are labeled it doesn't really matter in what order you draw them but it's often convenient to be consistent but that's uh that's not a must

17:04 okay um i hope you have a somewhat better idea now what a try is i didn't talk about how to construct them or how to use them for searching much but maybe you can imagine if if you were to search for a string you would just walk down the tree and follow the edge with the appropriate letter if you ever reach a point where there is no note where there is no um such outgoing edge say you look for b a you traverse b but then there is no a then you already know there's no this string is not part of the dictionary

17:39 and to insert something you do the same thing you walk down the tree as long as you can and as soon as there's no no further edge to follow you simply add a new child to this note and give it this this label okay

17:53 Complexity of tries

17:53 um so much for that now let's see how much you were able to follow this here's a fairly long question so i'll have to give you a little time to read this all

18:13 basically it's it's asking about the query time of a try you have a try that stores n strings over the alphabet of just the latin capital letters doesn't make a very big difference so 26 letters each stored string has exactly m characters to make things a little easier and we now search for a query string now the query string can have a different length doesn't have to be n how many notes in the try are visited while you're answering this query and answering this query means is there a string that has uh this query as a prefix or is there um a prefix of the query that occurs in the dictionary it's essentially finding finding all nodes that could be reached through that and um

19:11 yeah if if q was equal to m it would also mean you find exactly one string or you find there's no such string but it's um it's often think about q being smaller than m so you're i think this is uh the interesting case

19:31 then um you're basically stopping the search early and there might be many different strings stored in the try that start with the string q okay so how many notes of the try are visited in this single query that's that's the question and remember um maybe go back to this one how do you search for a query string let's do um i don't know maybe the example is is bb you walk down the tree uh following these um edges with the appropriate letter and um i assume that you just stop where you where you get to once you're done with this

20:25 i'd like to see a few more votes if possible we're running a little out of time so i won't i won't be able to leave this open for much longer [Music] but it probably just means we have to delay the exciting news what suffix trees are for tomorrow

20:50 let me show you the results for now um so here they are uh i added lots of possible answers just to make it a little more uh confusing maybe uh to offer you any any possible thing you might have come up with you see your peak for theta q and also m times log n so let's try to avoid from people shifting around but the correct answer is is down there uh the theta of q and the reason for that is if you're if you're asking about the number of visited nodes um you're basically asking about the length of the pattern that you're querying for if i was to query for bb what are all the strings in the set that start with bb i would just walk down b and b and then basically here i can stop now this is this doesn't exactly tell you which of these strings there are but um you can there's additional steps that would be needed for for finding all these leaves you could walk around all this tree that's separate maybe the question is a little ill-posed because it it doesn't really say what you're doing with the query string if the question is is there any string in the dictionary that starts with this query i can do it in

22:18 feed a queue time so the precise query here should be for that here's another one because it was so much fun um same setup we have a try with n strings uh same alphabet and same length now i'm asking how long how how big is this try how many notes does this try have in the worst case and this means it will depend on the strings that you store all right and again it's probably insightful if i show you the example here so how many nodes can you have in in this try if you have

23:41 now if we were in a in a room together these type of questions would be much more fun because you could do something called think pair share you would discuss this uh you would you would first vote and then discuss with your neighbor and then see if that changed your mind and then we could take it to the to the discussion with the entire group um i think the best i can offer with slido is just the thirst the first the think part but that's at least something so we have um

24:15 our almost 25 answers yep okay so let me lock in the vote now and most of you got this right the the answer is n times m and i'll show you on the example why that's the case uh in the worst case um

24:34 the strings differ very early so basically what happens is most of the time you have some prefix where it's it's it's branching out as a tree but then the remainder of the strings all look like these linear chains where you just have one note per character and you need roughly uh as many notes as there are letters in all the strings together because all of these notes just caters for one letter in one string okay and this is also the main weakness of tries this is why uh the try in the form that we've just seen it is not really useful it's not really feasible to use uh if your words are very very short maybe it's not a big deal but again think of the scale of google you can't afford to store five times even if strings were short like five you can't really afford to store five or ten times the size of the internet that's too big for an index you really want and this doesn't even store any additional the positions that's just the number of nodes so that's just out of the question this is too much and we can we can improve upon this using compact tries so what are these beasts the idea is if you look at the worst

25:55 Compact tries and beyond

26:06 case for these tries for the space you find that these long chains of unary nodes are really the pain are really the part that that hurts the space that require many nodes what we instead do is we compress all paths of unary nodes so whenever we have two such edges we just make that a single edge as you can see here and we do that also here and you see this this just became this edge now uh we do have a little problem here because previously this these two edges were labeled bb but now we only have space for a single character always take the first that's the rule but that means we somehow lose information in this process and we have to fix that so what we do is we store in the internal nodes the position that we compared okay so uh in the root we start comparing with the the zeroth position of the pattern or off the of the strings in the dictionary and if we if we jump down here it means that the next character we look at is is not a position two okay so this a here is really at position two not at position 1. again this a is at position 2 not at position 1.

27:37 that's why we have the 2 here okay what that means is um that all nodes have at least two children if if they had only one we would have removed them and that means every internal node makes the the number of leaves uh go up by one and so this is the same same bound we've used before the number of nodes is at most the number of leaves and that's the number of strings so the number of nodes is now order n

28:36 that was the space of the standard try and now the compact try gets this down to order n so again starting with the standard try you find all the paths of unity edges you only keep the first label but you have to store in the notes now a number that tells you how many characters you have to skip basically okay but formally it's the next position that you compare so that you know what these two letters what they correspond to

29:10 if you search in this compact try you have to make sure that once you're at the leaves you also check for the skipped characters so um if you if you were to search for b a b you would go position 0 i find a b position 2 i find a b yeah i found b a b b but hold on this is b b b so once you completed the search in a compact try you have to compare the characters you skipped over because you never compared the character position one in this in this search here

29:52 okay um if we use the compact tries we can build an inverted index that is very simple supports fast lookup and has uh not not an insane space requirement it's essentially as as big as the number of words not the total size of the words

30:12 the downside is and this is intrinsic to all the versions of tries it's it's restricted it cannot handle other queries it cannot possibly search for a substring a part of a word is also not easily doable to search for a sequence of words that have to occur in a certain order and the main big question is how do you do inverted indices in situations where there is no notion of words if you have biological sequences a dna strand there are no words these are just nucleotides all over billions of them how do you search how do you build an inverted index in that or binary streams if it's just a file and you'd like to support searching on a lower level this doesn't work with inverted indices and you need new ideas for this