Video 6-1: §6.1 Motivation, inverted indices

0:00 Introduction

0:04 welcome back to com 526 and a new unit again um this time on text indexing so we stay in the realm of strings and we stay in the realm of finding strings in longer strings but this will be a slightly different approach

0:22 i subtitle it with searching whole genomes because that will be one of the main applications where this is this is in in big use and since we just come out of this pandemic or hopefully come out of this pandemic you will all have done your pcr test at one or the other occasion and very much oversimplifying what's happening there is you take a sample of some rna from your body rna is this short-lived cousin of dna that coronaviruses are also made out of

0:57 it's amplified so that you can see them and then it's sequenced so all of the occurrence all of the occurring rna is is read off as a string and then you try to find these strings in a database of known strings and that's although the pcr tests use very specific snippets that are highly indicative of the specific corona virus for covid19 but the method is is fairly general you can use this for many other diagnosis and what's behind it in many cases is trying to find a specific string snippet in a huge library of known strings of known rna molecules or known genes from genomes or finding a certain part in the human genome to know what it's doing and this is this is very much uh the basic level of what's behind this is what we'll cover in this unit i hope this makes it a little more relatable to you when i did this last time this was even more acute but

2:05 we'll still see the one one odd pcr test done at the time once one of the one word device what do we want to achieve in this unit i'd like you to take away from it a few notions that can be used to pre-process a large collection of text that doesn't change all the time so we treat the text as static so that we can work with the text and specifically our inverted indices and suffix trees and the modern versions of that i wanted to know what this generalized suffix tree is well we'll cover that um on thursday probably

2:19 Motivation

2:57 again as usual it's not just about what is in principle doable but how fast can we do it that will make a major difference if you're working with gigabytes and more of data

3:09 and i'd like you to be able to design simple algorithms based on a suffix tree where there where you use what the suffix tree can give you this will not make much sense at this stage where you don't know what these are but we'll come to that and same for the construction algorithms of these

3:30 there's a whole bunch of sections because i tried to break this up into many small parts as opposed to having two big sections uh i would say this is my favorite unit because it shows some really elegant and nice results where some really famous people thought they're impossible and i'll show you towards the end of the module all the details of how to do it so it brings you quite close to the cutting edge of research but every individual step is really quite fundamental and elementary to understand it's just just in quotes that putting all those steps together builds something really fancy and complicated i think it's a really beautiful topic so i hope you can enjoy it a bit

4:19 it is a bit longer a unit than the other ones so it will probably keep us keep us busy for this next week okay let's have a look at what we're doing here more formally than in the introduction we look at what's called the text indexing problem where we again try to find occurrences of a pattern in a text but the game is is different the text is fixed this time around so we get the text ahead of time and well i'll i'll show walk you through the examples down here in a second what the text can can be but it's um an abstract problem that's quite versatile and we can pre-process this text so we can spend some time on the text and make subsequent searches fast and the idea is that we expect many queries for different patterns so this should be offset by the the time we spend on looking at the text should be offset by those many searches and if you want string matching as we've looked at it in in the previous two units is more of an algorithm where you're given the input you do it and then you forget everything and in this unit we take more the data structures classes the data structures lens where you build the index of the text and you

4:27 Text Indexing

5:41 keep that around and then you do queries on the data structure where would you find something that is text indexing at the bottom of it web search engines in the simplest way are like that they do lots of other things these days but when google started one of the basic functionalities was i type in a certain string and it finds all the websites where that occurs and other sorts of search engines or inverted indices well we'll come to that in more detail they still work pretty much like this dictionaries in the classical sense of looking up words in a different language they're pretty much static but often you don't want to just find the the keywords but maybe also where this is used and then you easily get to something like text indexing wikipedia is the same i think the the search function of wikipedia is notoriously bad i don't know everybody who you feel but it could sometimes could sometimes work better it often doesn't find occurrences in the text really well it's basically looking at the titles mostly then slightly more esoteric but i hinted on this if if you're working in bioinformatics then you have these huge collections of known biological sequences and the standard application there would be you take a sample somewhere from

7:11 some [Music] deep sea area you bring this up and then you try to find what has lift there and a way to do it is sequence these little remainders of life that you have in your test tube and then search these little snippets in a big database of known dna and that way you can often with high accuracy identify what kind of creatures live there and you can do all sorts of analysis based of that and lastly whenever you have text documents any collection that doesn't grow too fast can be seen as a text indexing task

7:57 Inverted Indexing

8:02 i want to look first at a very a conceptually very simple solution that is highly effective in some applications and is often the end of the story if you see text indexing and undergrad classes

8:15 so first of all where does the word actually come from it's is something you find in books so an inverted index is like the index in a book where you have a list of keywords and it shows you where they occur in a book and the same can be done in a sense for a whole text so this often works well for natural language text the big assumption that's behind this is that we only ever search for given keywords so if you try to search for some word that occurs in a given book that you have but it's not included in the index because the other thought it's not really relevant you won't find it or a book won't list all the occurrences of and in the book just because people assume this is not interesting

9:05 so an inverted index in in computer science is slightly extended from that restricted list because we have we can afford to have a little more space you just take all the words that occur in the text so can be just take the text and split it at white space but often it involves some knowledge of the natural language that's used so you often reduce words to their stem but then at the end of the day what it is is a big map or a dictionary from that maps from words to where they occur

9:47 and so i wanted to point out so this is just a dictionary or one one way to implement it would be a dictionary that maps from from strings to lists of integers

10:06 so the keys are the words that occur in the text and the values is the list of of starting indices say of occurrences and you've seen data structure is how to do this any suggestions

10:43 how would you do it if i give you a text file and you want to store an inverted index well you could download apache lucien it's a library to properly do it a simple way would be just a binary search tree right it's a dictionary the keys can be compared so you could just have a binary search tree

11:09 the problem here is that it needs at least let me write omega login it needs at least log n time to find something in this dictionary and n is now the number of words which could go we could could grow quite large and this is even disregarding the fact that the comparison takes time we're comparing strings and not just single characters so it's just um not quite as fast as we would like it it would work but remember n could be something like all of the internet or a web search engine or all of wikipedia it wouldn't be great if whenever you type something you have to wait some time that depends on the size of the data set it's just not good enough in this application

12:03 what we really want is something that depends on the pattern that you search because that's inevitable but nothing else all right because we're running a little short um let me maybe finish after this one

12:54 okay i can wait a few more seconds but it seems like we should spend some time on tries right i in this case let me not rush this last part but i don't want to leave you with the cliffhanger so i'll just tell you what a try is and we'll look at it properly next time

12:59 Try

13:14 a try is a tree data structure that stores strings as keys so it can be used for a dictionary but specifically for the case that the keys are strings and it has some some very useful features for this specific case

13:32 the term is a little is a terrible name uh it sounds like try so if well if you put it the plural then tries as the pronunciation makes a little more sense the rumor has it that it comes from retrieval and so you should say tree but trees is already taken so we say try i never really got this one but it's um common use so i i guess we'll just stick with it

14:03 um let's just look at the example here uh the what a try does is it stores the keys the strings that are stored as the labels on the root to leaf paths so if you take this path leading to this string then you see if you read from the root a b a a b and then this weird dollar sign that's exactly what's in the leaf so if a try stores a certain string it will make sure that the path from the root to where the string is stored reads exactly as the string itself and why is that a good idea it means that for example all the strings that start with a b can be found as the sub in the subtree of this note they're all grouped by prefixes and so this can be used for searching if i wanted to know does this try contain a string i just start traversing at the root and follow down and if i get stuck it doesn't contain it and if i find it i found it okay so search becomes quite simple um and well we'll we'll discuss the uh the nitpicks here next time you can also think about whether this already is good or not and spoiler the answer is not quite yet

15:21 but yeah let's let's not rush this one because most of you haven't seen this before