Video 4-1: §4.1 Introduction

0:00 Introduction to unit 4

0:03 welcome to unit 4 of comp526 in this unit we will talk about string matching that's the fundamental problem of finding a certain piece of text in a certain larger piece of text in that generality i put it with a subtitle what's behind ctrl f because the ubiquitous search functionality in all programs and especially in browsers and text editors is is very helpful to boost productivity and people are very used to doing control f all the time and find strings all the time and in essence what's behind this are exactly these algorithms that i will show you and one of them that we'll discuss in in more detail is is what many of these tools use to implement this

0:56 to get started um i want to introduce some notation and some formalization of what strings and text is in in our context so that we're all on the same page about this then i'll discuss the the easy methods how to do string matching and which is often good enough but not always depending on your applications and then we'll discuss a couple of string matching methods

1:25 string edging with automata and knuthmore spread is something you might have seen but maybe not with that angle of explaining it i think you will you will like it if you have seen it explained differently boy or more is interestingly often beating the optimal algorithm here so we'll discuss that uh that um that riddle a bit and uh finally we'll we'll look at ravencarp how hashing can help with string matching

1:54 start with the uh notation and introduction so uh what is this about it's about strings which are essentially just a sequence of characters and um it's in a sense the universal type for all sorts of data that is often the least common denominator used especially on the web of course we have natural language texts uh just english text or text in any other natural language but we also have programming languages and well the the text in programming languages are source code we have websites html at the end is all just text we have xml documents related to that usual websites should be valid xml documents but let's not get into this discussion an entirely different type of text are dna sequences encoding your genetic information we have bit strings it's not usually seen as a text but the same techniques and algorithms can be used so ultimately also any computer's memory is just a long string of of bits so whatever you whenever you want to find a pattern in this um this might be all applied as a as a string matching algorithm then there's many many different applications and that also means the tasks what you want to do with strings and the algorithms to solve this these problems are are very different what we will look

1:57 Applications and context

3:28 at is a very simple and fundamental problem but one that already has quite interesting algorithmic solutions and we'll build on these for more advanced applications so control f is what i mentioned grab the unix command or f grep if you want will not get much into regular expressions but the extension is often not too hard so these are classic tools that find occurrences of some pattern text in a bigger text file you can also generalize this to computer forensics where you scan large amounts of data for certain signatures of of malicious files that's what wire scanners do etc and many other applications essentially build on string matching as a as a stepping stone

4:20 Formal notation

4:23 so here's my notation for strings we have an alphabet and that's conventionally called sigma the capital sigma looks like the sum sign but it's the letter sigma in the greek alphabet uh is any finite set of characters and a character can be really a lot usually we think of them as letters in some alphabet maybe the latin alphabet that we are used to use but it could be any other natural language alphabet it's often also generalized to whatever you can type on a keyboard or well whatever you have in the unicode standard including all the emoji and whatever

5:03 and it could also be very more very much restricted to just zero one or the nucleotides in a dna sequence that depends on the application an important parameter will be the size of the alphabet that sometimes plays an important role

5:23 i will write sigma to the n with the superscript m to be the n-wise cartesian product so these are just all the strings of length exactly n and we also call these n-tuples in general if this sigma is any set though that's just generalizing standard notation from mathematics

5:43 sigma to the star is all the strings of any finite length so the union of all these for any n greater equals zero and it includes the empty string this guy which is written as this little epsilon that's the empty string and we sometimes want to write it even though it's actually just nothing empty right and something that's also useful as a shorthand the sigma plus is all the strings that have finite size but not zero that's uh that's not and uh now i'm in the way uh if we are given a string s of length n then we just write accesses to these characters as if it was an array of characters so we write s i as if i for the ith character and uh again we i try to be consistent and make it zero based for all of this class so we start with the zeroth character and we end with the n minus first some other texts are books used as subscript i but um i tend to find this closer to code and it's just as readable so we might we will just stick to that if we have two strings we just write st to mean the concatenation putting the strings next to each other one after the

7:06 other and sometimes spelled out by putting a multiplication sign in between and finally if we have a string of size n we write this notation which is similar to arrays for a substring that's formed from just these characters from position i up to j both inclusive if i is 0 we call this a prefix of s and if j is n minus 1 we call it a suffix of s so this is just something at the very beginning or very end of the string again nothing nothing magic about this and uh again something i introduced for arrays already is this notation with a round parenthesis because we will often want to write positions i up to j but excluding the end point and so that would be with the round parenthesis

8:08 i hope this set of notations is somewhat close to what you've seen in other classes and it won't be too confusing but well just bookmark this slide in case you ever get lost or ever don't remember what something means here's a little question to test your understanding or check if you paid attention on this rather boring slide maybe is it true or false that the sigma star is essentially sigma plus and the empty string for any for any alphabet

8:49 okay i'll give you a little bit of time i went over this quite quickly but it's a very simple question it's essentially just making sure you're still awake we have some more you can be honest and take no clue if you fell asleep during the last slide that's fine um it's it's all written there so you can just go back and watch it again later

9:29 okay let me show the results because it's uh it's interesting we have a roughly equal equal split between true and false so i guess i did go over this slide a bit too fast maybe it could also be that you're still not not very familiar with these notations so it was a bit confusing the correct answer is yes this is the same and let me briefly go back and show why

10:04 if you have the set of strings here um the sigma star is the union of sigma to the n for all n greater equals zero the sigma plus is the same union but starting at one and the only single string of length zero that has no characters at all that is the empty string so really the only thing missing in this set compared to this set is that single string so that's why we get uh get this equation okay um fine um that's uh again as i said it's just a a lot of information and notations thrown at you but it's not really anything particularly deep i do want to define the problem at least today that we will look at in detail next week and that's the string matching problem so suppose we're given a small pattern string relatively small it's not necessarily very small and a fairly large text that we want to search so we'll usually denote by t the text t like text and p like pattern i hope that is intuitive enough people sometimes also call it finding a needle in a haystack but i don't like that metaphor too much because that sounds like it's very hard to do whereas uh string matching is a problem that is is very efficient to solve in practice

10:49 Problem definition

11:36 there's no no problem really so uh finding a needle sounds in a haystack sounds really tough and as i said you know as a wake statement usually we think of the text the text has length n the pattern has length m we typically think of the text being much bigger than the pattern okay

12:00 um well i mean the obvious application is you open a text file and it contains i don't know the text of moby dick and you're trying to find all occurrences of whale in moby dick then the text is well i don't know how long that will be a couple of million characters maybe and the pattern is just well five five characters or maybe you want to find a little more specific whales but uh it's it's fairly small in this example what is the output and this is again um this is a important to get uh the exact details of the pseudocode right at the end i will always formulate the problem so that we find the first occurrence of the pattern in the text so the the smallest index at which we find the pattern in the text if we take the substring of length m of the text starting at that position okay that's the formal definition of the problem if there is no match which could just as well happen then we just return this this dummy result no match

13:16 i should say that there are variations of the problem which could be find all occurrences um or some well some variations where you start at a certain position in the text starting at a certain position can formally be just treated as giving in a different text finding all occurrences is usually the same as this one you could essentially just start find the first match and then start find the next the first match after this one so you can iterate through all the currencies there's a slight catch to this that i will comment on at the appropriate time but you will find in textbooks sometimes uh this variant is the one they study i think this one is just as general maybe even more general so i'm uh we'll always find the first occurrence okay here's this variant as i just mentioned a small example if you have this text and this pattern then you actually find the first occurrence here um maybe in red instead and you don't find the pattern who of course he occurs a second time at this end here but we just record return the first match

14:44 an algorithm for this problem is implemented in in java in the standard library uh in the method um index off and it's actually the the brute force method at least when i last checked but we'll we'll come to that