Video 4-1: §4.1 Introduction

0:00 <Untitled Chapter 1>

0:01 so ah welcome back to com5 to six and welcome to a new exciting unit unit four where we'll talk about string matching and because string matching sounds very academic and not very useful i put the subtitle here because unless you're on mac and i don't know what the command is called there pretty much throughout all programs you can press ctrl f and it gives you some ability to search and that's really what we're doing here we're explaining what's happening there especially if this is a text editor or a browser where this is essentially text-based and we'll come back later to the scenario that's closer to search engines or indices

0:45 Learning Outcomes

0:50 so learning outcomes for this unit uh i want you to be familiar with the theoretical notions and notations for strings this is just something again i think computer science tend to communicate in these terms so it's important to know those and pretty much anything is a string so there are ubiquitous in in various ways in programming but we'll take the mathematical notations into this game as well i want to introduce three main algorithms nicely abbreviated so that they don't make much sense if you don't know them but that's knuth morris brett boyamore and ravencarp all named by their inventors

1:32 apart from just knowing how they work i wanted to know what the differences in their performance are it's a little bit like in sorting none of them is completely dominating the others in all possible metrics um and instead you'll have to sometimes mix and match a bit depending on what you need and lastly it turns out that a component of kmp can be used for other for solving more sophisticated problems than just finding occurrences in a text that's what string matching is by the way we'll come to the proper definition in a second there's a something more versatile going on and so i want to teach you a little bit how this works but nothing too crazy

2:14 i broke it up in nice little chunks but some of them will be quite quick particularly the first few and we'll talk about another method that leads up to kmp first that's string matching with finite automata

2:35 with that uh let me start with the introduction and in particular all this notation around strings i'll jump through thumbs some of these slides a bit quickly uh they're both mostly for your reference

2:47 Ubiquitous strings

2:50 so first of all what is a string um and we're not talking about underwear uh it's a sequence of characters for us and the characters can be uh something we'll talk about in a second um i want to first stress how ubiquitous they are we use them for natural language texts in one form or another all all languages i know of are based on on something like sequences we use them for programs they're used for websites and xml documents which arguably websites should be right they're also in our body in a way even though maybe encoded in a slightly more wet and yucky form but dna sequences that make up your your genome are also strings in essence and of course bit strings so when we get closer to computers everything is ultimately somehow bits and main memory is one we can we think of it as one long sequence of bits and so everything you do in a computer ultimately is a string if you want to look at it that way because it's a sequence of bits although sometimes a bit more structure is imposed on these but this also means there's many different applications also many different tasks and questions we want to ask about strings so there's a lot of different things

4:11 we can do with strings and so this will keep us busy for a few more weeks in this first unit we'll look at finding in one long string which we will call the text we'll try to find a pattern and the pattern is really just another string so think of finding all occurrences of whatever love in the works of shakespeare might be might be one example another more esoteric one is finding a certain gene that's encoded in your dna you want to find if that gene is present in your dna that used to be science fiction but it no longer is you can ask a company to sequence your dna and they will get back to you with a two gigabyte text file um and then you can do all these analyses if you can make sense of them yeah virus scanners are usually based on something like finding specific patterns they're often the at least the basic form is quite dumb it's trying to find specific uh pieces in code that it knows are part of viruses they can do more sophisticated things as well

5:28 finding patterns like this is often a building block for other applications for example in in bioinformatics if you're talking about genomes you often need slightly more sophisticated notions of finding strengths usually things are not exact but there's slight variations that are essentially irrelevant for how your body works

5:49 Notations

5:53 and now the promised notation so bear with me for a second strings have an alphabet we always when we talk about strings we always need to assume we know what are the possible characters that can occur we assume that this is a fixed and finite set so it's not like uh all positive integers it has to be fixed and so we can speak of little sigma the size of big sigma uh the size of the alphabet the number of different characters now if you think about english you might think okay we have 26 letters but then we have them in lowercase capital and uppercase and we have all the punctuations and spaces etc so we probably have a few more characters to take care of uh traditionally um i think we'll we'll talk about this in a second so you know ascii this character encoding that has 128 characters that use uses is is usually enough for most western european languages and english for example but already struggles with some like german because we have a few other characters that are not represented uh so even even there uh you have not just the 26 but something like 100 characters and uh this has recently been more or less recently been extended massively so you

7:13 know unicode with all the emoji they all count as a separate character so we have many many more uh i lost i think unicode has around 150 000 characters that's just something to bear in mind so this sigma can be really small it's four for dna four different nucleotide bases but it can also be uh hundreds of thousands depending on what the application is

7:47 all right here are the nucleotides for your dna now an alphabet tells you what a single letter is a string is several letters and we can write this as the cartesian product of the alphabet so it's just uh a string of two characters is a pair of two characters or in general and a string of length n is an n-tuple of characters and that's the way to write that in mathematical notation

8:19 so you can write sigma to the end if you know that the length is fixed then in this context two other notations are often handy the star means any length we don't know including zero so the empty string which is uh this greek epsilon that's just the string of no characters of length zero it's sometimes useful to be able to write that down without writing nothing and sigma plus is well similar but starts at 1.

8:57 we will massively make use of the fact that a string is a sequence and we can access characters by index and so we'll just write this like this so other other books or other lecture notes will vary the the notation there but i think it's it's convenient to not hide the relevant thing in the index the subscript so we use this array notation to access strings and many programming languages represent strings as arrays of characters so this is close to their implementation as well and again we started with zero like all arrays in this class so if a string has length n it has indices zero up to n minus one

9:44 uh we'll just write two strings after each other or their concatenation such as putting one string behind the other and if you want to spell it out you can use this multiplication symbol and the last thing is this notation that we've used for sorting for recursive calls of sorting algorithms already so it's not not really new this is a slice of a string from positions i to j so in this notation including the endpoint this notation will often be convenient as before for sorting you know this already so i is inclusive j is exclusive um so any such thing is just called a substring of a string um be careful i will i will try to be consistent that a sub sequence is something different a subsequence is where i can take any positions as long as there are left to right but i can leave out things in the middle whereas the sub string is a contiguous subsequence where there's everything included from an endpoint beginning point to an endpoint

10:59 and two more two more vocabularies is prefix and suffix prefix is something that a substring that starts at the beginning suffix is a subsequent ends at the end i think that's it so time to wake you up as always

11:24 this can be a quick one it's just testing if you paid attention even though it looks like a fairly clear result okay three two one all right we have a clear majority for true

12:31 Clicker Question

12:35 so remember sigma star is a string of any length including the empty strings including length zero sigma plus is this is all strings of any length but starting with length one so if you want to get sigma star from sigma plus you just have to add the empty string again note that the empty string is kind of the only string where we don't have to obsess about its alphabet it fits for anything because it has no no characters anyways all other strings should have a properly defined alphabet

13:08 String matching - Definition

13:12 the last part for this introduction and this massive list of notation is the formal definition of what the problem is like that we're looking at so string matching as i said before the problem consists of two inputs we have a text t and now the text will always be of length n or n will always be the length of the text and p is the pattern that we're trying to find which is some other string over the same alphabet note that they have the same sigma and the pattern has length m now we usually think of the pattern being relatively short and the text being relatively long formally that's not uh not part of the problem it's just usually the case now if the pattern is longer than the text we don't have to search but the pattern could be half the text something that's not unthinkable but usually you can think of the pattern being small

14:17 um and so for the output it's a little um there's there's different variations and i want to stress here that we find the first occurrence only for so for this point so we try to find the smallest position i so that if i take the substring of t starting at position i i find the pattern

14:43 and i take the smallest such i so it's the left most occurrence the first occurrence of this pattern in the string in the text if you want to find all occurrences you can always find the first and then remove that occurrence from the string and then start the search again on the remainder um

15:11 there's another option if the pattern does not occur at all we return some some special return value um i'll just write return no match with the pseudocode different programming languages of different conventions but it's convenient there so we'll keep it abstract

15:31 a variant of the problem as i hinted at is to find all occurrences we'll talk about this at some point because for some of the algorithms you can find all occurrences in essentially slightly faster than searching for the first and then continuing from there is to kind of give up some information you learned already but we'll now focus on always finding the first occurrence okay let's do a small example here's a string uh where is he if i say the pattern is he i want to find where is the first occurrence don't be tricked the first occurrence is here there's a second occurrence which is a bit more springs to the eye but so the return value here would be one remember we start at zero uh and if i search for who i get no match because it doesn't occur

16:31 uh i wanted to stress that uh programming languages tend to implement this because it's a primitive they don't always implemented it implement it in a very smart way and we will come back to this so in java there's a class string and it has a bind index or it has an index off method that finds in the first occurrence and in python it's called find okay and i'm confident that any other programming language you come up with will have an implementation of string matching too

17:17 he's not even strictly speaking about string matching it's just practicing uh the notation again i mean pay close attention to the types of parentheses other than that there's no tricks is this

17:44 i know counting is hard and then it's monday okay i see reasonable things coming in three two one and locked so i guess it's kind of clear although some people sent no idea

18:31 so let's go through this very briefly again uh if i if i had shown you this it might have been a little more convenient so here are the indices on top of the characters and now we just start at the third position but starting counting with zero and then up to seven but excluding seven so it's up to six so p five two six okay easy enough should we do some real algorithms