Video 4-2: §4.2 Brute force string matching

0:00 Intro

0:03 in the next sub section after introducing the notation for string matching i want to look at the very first and simplest string matching algorithm and that's just the the brute force method

0:15 Guesses and checks

0:18 normally um brute force sounds really slow but in this case you will see brute force is not as bad as it may sound a general thing that is true for almost all of our algorithms for string matching is that they they can be described in terms of guesses and checks and here a guess is a position in the pattern in the text at which the pattern might start so it's a guess because we don't know yet but whenever you have a text t a long text you can always try and guess that the pattern might be found at this position starting at this position that guess may or may not be justified and initially if you know nothing about the text any guess might be might be justified but as you learn more about the text through comparisons some guesses are becoming impossible the way to find out is a check and a single check is a single comparison of two characters we sometimes write this as this shorthand so if if you start at position i and you check the jf character in the pattern then this is really doing this comparison there's one character here and you compare if that one matches the corresponding position in the text that's all that there's that is written

1:45 here with the appropriate um computation on the indices okay so algorithms will differ in how in what guesses they make and in what order and what type of checks they do and uh that's that's the process but these two things will reappear in in the algorithms

2:08 Observations

2:09 some simple observations are that if you want to verify um a correct guess so an actual occurrence of the pattern there's no way around doing m checks remember um m is the length of the pattern that was something in the notation but i didn't stress it today so maybe um just to to recap you need m checks to verify that the pattern is really found at a certain position so there's no way to really save on that but if you want to debunk a guess if you have a guess that is not correct then it might take much fewer checks to recognize that this is incorrect a single mismatch is actually enough so it will be interesting to see how we can get the mismatches the incorrect guesses sorted out quickly whereas for the correct guesses there's not so much you can really do

3:10 the cost measure that we will mostly focus in this unit is the number of character comparisons so that's individual characters from the alphabet one in the text one in the pattern or maybe also between text and between pattern and we compare whether those are equal or not

3:31 the only thing we can do is really check t i equals p j that is uh what we can do i'm stressing this because for example we cannot ask if one character is smaller than the other lexicographically or something like this we will not need that in in the algorithms in this section an obvious bound on the cost that we can always get by with unless we're doing redundant comparisons is n times m there are at most n guesses actually n minus m are enough uh but that's roughly n and uh to check whether each guess is correct uh the the worst number we can need is m so that's that's really an upper bound on the string matching problem and if m is very very small if you're just looking for a pattern of two or three or five characters maybe m times n is really not that bad it's essentially scanning the text once

4:35 Brute force

4:37 now let's look at our first algorithm for string matching and it's a very simple one it's brute force so it says try all guesses and do the checks just as they come the only uh slide optimization that's built into this is that we stop if we have a mismatch we don't stupidly keep going if we already know that the current guess must be incorrect that's the only thing so in code that means we iterate through all the guesses these are exactly the guesses that you've seen on the previous slide then we iterate j from 0 up to m minus 1 that's all the positions in the pattern left to right and if we ever find a mismatch that means we stop this inner loop if we keep running the inner loop till the end that means if j is m after the loop then we found a match and we return that position remember we just returned the first match so all we have to do is return this position i at this point let's do an example just to make this clear um let's see well maybe black is is best to read so uh what what these colored boxes symbolizes so here's the text right and we try to fit the pattern in here

6:02 and the pattern here is abba so we do the comparison with a and that actually matches the second character b matches two the third character matches as well but then the last one is a mismatch but we had to look at all the characters here now okay that was not a match maybe we tried the next guess so we start with b but that's immediately a mismatch the pattern starts with a so we don't have to compare all the other ones in this in this position same thing happens here and here then again a is a match b is a match but here we have a mismatch so we don't have to compare this one and this goes on here we have a match a match match and then actually here we find the pattern so uh well had i remembered what number was the the guess here so that's zero one two three four five six

7:01 so we would return a match at position 6 at this point that's all that happens here is that written in nicer font and if you count then you see you need 15 character comparisons in this example whereas this product the upper bound n times m is 44 so that's uh i don't know a third of the cost that's not that bad um but it was a small and specific example what's interesting is that this algorithm essentially in the way i wrote it there even though

7:39 hidden deep in a in a you know in a hidden function a private function the java library has um a method called string index off and this one um is essentially implementing this brute force method so it can't actually be such a bad method right

8:04 now this is also my my take on the brute force method it often is actually good enough but sometimes often is not not good enough we'll see and we're natural language texts where we have

8:21 specific words and not all possible combinations of characters really occur only the specific small subset of our dictionaries really occur so it works fairly well for natural language text because of that and for completely random strings it also works works well because you often get early on mismatches if everything's completely random but it it does come become pretty bad in examples like this if the text is all a so the pattern is all a's except for a b at the end you always keep comparing from the beginning you already know uh there's this b at the end but you you keep and what's what's worse you know that there's all a's up here but you forget this uh you don't use that knowledge for the next guess and so in this case you do get essentially the worst case bound of n times m or the brute force method so if there's a if there's a chance that this is this is what happens in your application the brute force method is not good enough and if you need strong guarantees about what can possibly go wrong because maybe the user supplies the text and pattern that you're searching then the brute force method just doesn't cut it

9:44 um one observation for that leads into the next section is uh this is a particular a particularly bad input which has a lot of self-similarity uh what makes this redundant here is we already knew there are a's in the text so why check the same a's again here and this kind of of redundancy or um superfluous comparisons

10:12 should be able to be avoided um and that's that's something we'll we'll look into and uh yeah so uh we should be able to exploit these redundancies both in the text and then the pattern now that's what we'll look at next

10:32 uh if you have any questions then please let me know at this point it's always a good time okay then um let's move on i have a a little

10:58 i have a little road map here because basically this week and the unit um six that we'll talk about in in a week or two or maybe starting before easter and then finishing after easter depending how it works out uh they belong a bit together they both um discuss the problem of finding patterns in text this um there's two approaches really one is uh that we spent some time on looking at the pad looking at the pattern closely to avoid redundant work when we find it in a in a new text this is what we'll look at today there's also the opposite idea if if your text is static and doesn't change like it's an actual dictionary for for english but much more importantly in in bioinformatics the human genome of a certain person doesn't change all the time if if if it does that's actually very bad news for that person so usually it stays the same in most cells and then it makes sense to pre-process the text whereas the pattern might depend on on the application depending on what the doctors need to know about that person's genome so we're looking in unit six um add methods how you can pre-process the text and make use of that to to speed up

12:17 pattern matching but for for this week and for today we'll start with the opposite version the pattern is fixed and we work on the pattern first and then we do the matching