Video 4-1: §4.1 Introduction

0:00 <Untitled Chapter 1>

0:03 so welcome back everyone uh welcome back to com526 efficient algorithms um we're starting a fresh new topic we'll talk about strings for for a while uh not just this unit but we'll start um nice and simple so I'll I'll talk more about what's what strings are for us and then specifically this unit will be about string matching finding subsets in in a large text again something uh some of you will have seen will then build on that and go a little deeper than you would usually go

0:39 Learning Outcomes

0:41 the learning outcomes for for this unit are know some Basics about strings if you haven't seen this before it's just uh something ubiquitous in in all of programming computer science there's a few concrete algorithms we'll look at the knuth moist spread for you more and Raven carb algorithms let's put these abbreviations stand for and as always like for the Sorting unit I want you to not just be able to execute the algorithms but understand when they are good and when they're not so good and we'll look a little bit at building blocks that you can use to solve other problems because it turns out people don't always just want to find substrings a big surprise I subtitled the unit as what's behind control F I mean for all Mac users whatever the shortcut is there uh today you could even say what's behind search that would just be slightly bit lying um think of this as finding the text in a text editor uh it's a little different if you have a search engine that can pre-process the text but we'll come to that as well

1:51 Outline

1:57 I want to start with um some Basics about text and string and uh although this is quite um quite Elementary uh the formal way to define strings and work with them in a mathematical setting is it could be new for a few so I want to briefly recap that but as a string is just a sequence of characters so you hopefully know what a sequence should be now a character can be pretty much anything uh we'll we'll come back to more restrictions on that some examples of where strings arise any kind of English text or other language text source code and websites and pretty much everything essentially is converted to a text because it is a very natural format for us and computers despite some exceptions much of computers is one-dimensional in a way we organize memory one-dimensional and so it's it's quite natural to also do this for the data that we work with and some things like XML documents they're effectively a tree right it's a tree structure but you can encode it as a text and so many things we do for text are a little more General than they first appear because you can map so many things back to text okay when I say text uh that's the same as string it's just

2:02 Ubiquitous strings

3:25 I don't know a string sounds short and text sounds long but there's no formal formal difference okay because it is applied in so many different contexts it's not surprising that there's different requirements and different algorithms depending on what you want to do the task we will focus on for this unit is to find a short pattern in some long text so we find exact occurrences of some pattern string and so that's what usually control F at least in the text editor does many searches are slightly smarter these days they try to also find things if you mistype them at least if you mistype them in the typical ways that other people have mistyped them uh but we'll we'll focus on the exact one first there's a classic Unix tool grab that basically does this and and more F grab if you want to be specific and at least the core of virus scanner still works like this they also have additional heuristics but um they still have signature databases they have little Snippets of machine code that they are looking for because these are known to occur in known viruses so they're they're really looking for for substrings exact matches as their core principle and the reason why they still do this is that it's so fast

4:47 many of these other heuristics are smarter and better at finding threats that are slightly changed from what has been seen before and so on and so forth but their basic text searches so fast it's still it's still useful as a Baseline

5:07 as for sorting it's it's often a building block for for further things so what are what are strings for us um I already said it's a sequence of characters so we should know what a character is and uh we'll just talk about alphabets so uh here's the first first Greek letter of this it's a capital Sigma same as the sum sign but not the same symbol right it's a Greek letter capital sigma and we use that to denote the alphabet the only thing we really restrict here is that it should be a finite set so you you can write down the alphabet once and for all uh it's convenient to have annotation for the size of the alphabet so that's the little Sigma or at least one version of it and so we use these two keep that in mind standard types of alphabets are just the letters we use in English and other languages but it could be a bit bigger could include all the Emojis uh I forgot to look at the the latest stats I think it was around 100 200 000 characters in the Unicode standard maybe I'm exaggerating a bit they keep adding more emoji and more more other super valuable things all the klingonic scripts and whatever uh but even if you if you're a very liberal

5:09 Notations

6:24 and include anything and everything that some some group of people says yeah this is a thing you end up with something like 200 000. it's a lot of characters if you wanted to write them down but it's also just two hundred thousand if you think about it in terms of computer memory it's not such a big deal there's much smaller alphabets as well uh this is from from bioinformatics your your genetic code is basically a four letter alphabet

6:54 all right many different alphabets and we'll usually keep that generic we'll just say there's an alphabet Sigma um that's a single character now to form sequences of of these characters we have different notations that are handy if you just say Sigma with a superscript n you can say that's just the the N Fold Cartesian product of this in this in set notation so that's all end tables so it's all strings of length n n characters so you can write that very briefly as Sigma to the n and people have these these two abbreviations that are that are handy star means any n and you take the union that's what's spelled out formally here and that includes the string of zero characters which is called The Empty string so we'll we'll have a second a separate symbol always use this this Epsilon here to denote the empty string It's just sometimes useful to write that all programming languages would use quotes for Strings oh well all that I'm I can think of use quotes for Strings and so the empty string would just be quote quote um to not write quotes all over the place and you know all the hassle with escaping if you need the quote symbol inside the string and all that uh in in

8:14 the mathematical notation we don't do that we don't normally write quotes uh so that's more concise but it means you can only write the empty string if you have a special symbol uh the plus as a superscript is the same as the star but starting at one so all strings that are not empty

8:39 um and then because a string is a sequence we will model this as an array in a computer and so the rest of the notation is derived from that I'll write this bracket notation to say that's the ith character but we start with zero which is exactly what python does right a string in Python is is an array of characters and so uh in in square bracket zero gives you the the first character in the string all right uh just a few more so if you have two strings you can just write them behind each other and that means concatenation now uh it's a little unfortunate that in math terminology the the dots as multiplication is for people predominantly write for concatenation this comes from group Theory and uh that that people thought about strings as the free group over the alphabet and so on and so the natural symbol for groups there is is multiplication not Plus I mean this is a very weak justification but uh it's very firmly established so if I write two strings and put a multiplication between them that's concatenation python would use a plus and um most most programming languages would use a plus uh so that's just um I don't know if it makes a lot of sense

10:03 to to add this to the slide as well I don't think I'm telling you new things at this point in the term uh last pieces if we have a string we will often want to speak about substrings which is a contiguous range so a sub-range of the array same as we used for recursive calls of sorting algorithms and so uh s i j is the substring where we include the endpoints and we'll use this notation often as for arrays so same same just different names for it we call it a substring here and two specific types of sub swings of prefixes and suffixes a prefix is a substring that starts with the first character or at position zero the suffix is someone that goes all the way to the end

11:08 all right any questions on the notation so far my suspicion is that much of that is repetition but just have a little check let's do this little one just to answer so I realize you can just guess but maybe

11:30 avoid the guessing foreign we've had a record-breaking 81 votes on the attendance code let's see so you should definitely get 60 right or more I think um I'll leave it with 46. most of you seem to know uh that that's the same and

13:15 that's true uh just to recap so this is the set of all strings including the empty one so you can write this as non-empty strings and the empty string all right

13:24 String matching-Definition

13:27 so what do we want to do with our strings let's formalize this finding patterns as well and there's this one one caveat here where it did you have some choice so I'll point that out uh the first is just the names so we have two types of two two strings involved in this problem the input is a text and a pattern so T will always have length n so with our new fancy notation we can write it like that and the pattern has length M so uh that's the where the two letters come from and I'll use that same same names for for Min for on many slides so just uh hope that sticks and we usually think of the pattern being relatively short and the text relatively long but that's not something that's part part of the definition it's just if you if you think about what are typically good algorithms uh that's something to keep in mind but it's not to say that you always have this now for the outputs uh this is a little ambiguous so what we Define here is we want to find the first occurrence or the first match of the pattern in the string so that's formerly the smallest index I so that the pattern occurs starting at

14:45 this position I in the text all right now what would be the other option it could occur several times so you could just report all the indices then you can get into a question what about overlapping occurrences if the pattern allows that do you count all or both so for here we'll just break ties to say the first is all we want and if you want more you have to continue searching again that's something in line with most programming languages python has this find function on strings that does by and large the same thing of course it can happen that there's no occurrence of p in the text then there's some special return value we'll just call that no match

15:33 you can also find all will will touch on that briefly later but um for now you can just do this iteratively by asking for the first occurrence and then starting or taking the the suffix of the original text and continuing from there a quick example here's a text and here's a pattern now our problem says find the first occurrence and so he occurs here now remember we start counting at zero so that's return value one because that's at index one and for another pattern which does not occur you should return no match okay good um so far so good let's Hammer this point home but I want this really quick so uh currently the connection will work let's try to do this real quick because it's a simple question

16:54 should have probably hidden the the results uh either way no one no one disagrees so um to not bore you to death if you write the indices above each of the characters then you see that position three is the p and then you go up to position seven but excluding position seven that's the round parenthesis so you take positions three to six inclusive so that gives you P five to six okay not too hard okay that's that's just uh there's so much confusion in the literature so maybe this is let's flip that over into a warning if you read up Elsewhere on strings uh always watch out for start day do they start at one they start at zero are inclusive X the substrings inclusive or exclusive of the endpoints um there's just no consistency so you always have to be a bit careful of course it doesn't change the the fundamental principles at all but well

17:02 Clicker Question

18:10 maybe at this point before we continue let me ask what kind of string matching algorithms you've seen so I can get a feeling a bit for how fast we should go over this unit

18:34 however there's always a few people who have not seen any of any of this at all uh in a way my justification at MSC level is that it's fairly is fundamental things so even if you haven't seen them uh by now you've learned to digest this content faster than undergrads and for those who have seen it uh

18:59 yeah I love that I love this uh specific string matching algorithm uh well I mean algorithm uh what I mean by algorithm is the way it works not necessarily boasting with all the languages you've learned and how the string search method is called there okay

19:36 okay against um it's tough to see from from there so Brute Force nine people voted five people noted none uh we're still just at 33 34.