Video 4-2: §4.2 Brute force string matching

0:00 Brute force overview

0:01 the first string matching algorithm I want to show you is called The Brute Force algorithm and normally this means it's a terrible solution in this case it's not so terrible it's still useful and so it's it's a fine algorithm but it it's worth knowing it's blind spots

0:23 before we get to that um it turns out that a lot of different string matching algorithms can be cast in in one uh in one framework so let's introduce that a bit um most most of these algorithms will work by making a guess and a guess is just a position in the text where the pattern could occur and then you might check individual characters one character from the text and one from the pattern do they match or not I think it's conceivable that this is what you will do in string matching in one way or another you have to start making some comparisons somewhere and then you do several checks to potentially verify your guess uh the number of guesses is not absurdly big so that's why Brute Force has some hope

1:15 a little thing to keep in mind if you want to verify your specific guess at one point or another you will have had to check all the characters of the pattern so it needs M checks but it might be enough to do a single check to dismiss a guess if for example the text contains some symbol that does not occur in the pattern if you find that symbol there you know there's no there's no occurrence you don't need to check any of the other characters foreign leads us to a useful cost measure so remember this will come haunt us many many times the the word Ram model says we should just count all these primitive instructions but we don't often feel like coding at that low level so instead we count something that's the same for all these possible conceivable implementations some abstract cost measure and that's the number of character comparisons in this case so the number of checks and if we're not doing redundant checks now okay a really stupid algorithm could well do more than than these checks but non-redundant checks if you if you manage to keep note of the results you should not do more than n times M because that's every possible position it detects against every possible position in the pattern

1:44 Measuring algorithm cost

2:34 you've learned everything after that after that many checks nothing new Under the Sun after that so how would you how would the brute force method work it checks all guesses and the only slight bit that's uh smarter in this is uh to to break out of the loop a bit early but let's just uh first do the example so the text is written up here and the pattern is a b b a so I already filled out these diagonals to show to help me not to lose track of the lines but also to show you that's that's the worst that can happen for every possible starting position so in a way this is the starting position here is I that's the zero one two and so on you have to do at most four checks because that's the length of the pattern so if we start comparing here a matches B matches B matches but then we have another a so we have a mismatch here so that was not a correct guess too bad let's start from the beginning so do another oh okay it doesn't match another it doesn't match doesn't match so in the all of these cases after the first check we could already dismiss the guess and if you look at the code above this

2:42 Example of brute force

4:03 is also what it does it goes through all the guesses and then it goes through all the positions in the pattern and compares the appropriate positions in text and pattern and if they don't match then you break out of this Loop so you don't continue comparing if there's no need to if you reach the end of the pattern that way then you return your guess and that was the first hit the first occurrence and if that doesn't happen so if you if you didn't get all the way to the end of the pattern then you would not return a match and continue with the next guess

4:44 let's finish this off in the example uh here we have a match a b but then there's another mismatch mismatch A B B A hooray we found our pattern and let me just Mark the mismatches as well um okay and here's the thing in nice again I did the counting for you so it's uh overall 44 comparisons character comparisons that we needed in this execution uh sorry it's 15 out of 44 character comparisons that we needed 15 we actually did 44 would have been the worst case all the Shaded cells so it doesn't look like uh brute force is doing too too badly here okay I think this is still true in Java is essentially this method is for what they use um it's only mildly embarrassing uh python is has a a much more sophisticated method they used to have something that's fairly close to something I'll show you and now a few years ago they had a specific project where they asked algorithm Engineers to come up with something better and so now they have a a quite customized sophisticated method so definitely not doing Brute Force

5:33 Performance and worst cases

6:19 now this sounded like brute force is not such a bad idea and if Java does it and people are not always complaining maybe it's fine and it turns out for for many types of texts it works surprisingly well especially natural language text or things that behave sufficiently random uh but uh if you look at the worst case then you can construct texts like this so if the text is just all A's and the pattern is all A's but a single B at the end you will always get the mismatch from the B and so you'll have to try every single possible check so the worst case is essentially n times m you do the exact counting that's what you get but in terms of the the asymptotic cost it's the product of the length of the two strings okay

7:22 Improving search efficiency

7:25 okay so many of you have seen this before now what do you do if your application could produce inputs like this if both the text and the pattern are are quite long this is potentially too costly and it's definitely annoying for such a simple task to spend so much time if you look at the worst case here you could say ah this is this is really peculiar and special there's a lot of self-similarity in the text in this case like it's all it's all is repeated all over so that's as repetitive as you could could somehow get maybe we can take advantage of this instead of uh being hurt by it and also if specifically here like um if you do this as a human you don't even it's it's hard to to go through and and even write all the A's because it jumps in your face come on you know there's another a coming you've just seen by this comparison you've just seen that this is an a now you're asking again whether the text has an a at this position really so you uh you do repetitive comparisons in the sense that you already know the outcome the algorithm just wasn't smart enough to realize it

8:49 so to sketch out what we'll do is uh in well that's a tough call this weekend Monday I guess at least uh we'll we'll look at what we can do if we study the pattern a bit up front and it turns out even if the text is repetitive it's enough to study how the pattern behaves to exploit that and we'll see uh well three to four examples depending how you want to count uh for for doing that and there's the second approach which is different type of application if the text is not changing all the time and that's the the realm of search engines in a way uh then it might make sense to pre-process the text because then uh you can at least hope to find matches in time independent of the size of the text and it's quite obvious if search engines for the web would do anything that has to scan the entire web for every search I mean clearly not not possible so we'll touch on that a bit later again