Video 4-2: §4.2 Brute force string matching

0:00 <Untitled Chapter 1>

0:04 in the next section let's see our first actual algorithm for solving the string matching problem uh and i call it the brute force method because it's essentially just drawing all possible options in a simple problem like this this might be good enough indeed um but yeah we'll see that it is not always that great

0:08 The Brute Force Method

0:28 but it's a good way to start um it's also a good opportunity to think about the problem more generically well what can you do to solve this string matching problem um and so i will assume that what we can do really at this uh for all the unit except maybe for the last section the last subsection uh we can take two characters from the string or from the pattern or from one from the text text one from the pattern and compare them are they the same or not that's pretty much what we can do and so we call this a check if we do this between the text and the pattern

1:12 i think the notation is is not so important it will always be spelled out if i remember correctly so we can check two characters one in the text and one in the in the pattern

1:25 um and we can try to confirm or exclude guesses so positions in the text where the pattern might be found so you can guess maybe the pattern starts in the text at position i so that would be a guess and there's only so many possible guesses because the pattern can only start at every position and of course you can take a guess and then do a few checks and they might either confirm that there is a match or they might show a mismatch between some characters and then you know this is not a correct guess

2:09 a key feature is we need m checks or a correct guess because we have to check all the positions but we might we may be much much faster with excluding a guess because one mismatches enough if we know where to compare to find that mismatch we can be much quicker

2:28 what will count in terms of the costs remember ultimately it's word ram but we want to make our life a little more convenient so we'll count something more abstract than web drum instructions so here i'll i'll usually count the number of character comparisons with the number of checks

2:48 we'll later allow some pre-processing so we'll also compare characters in the pattern with each other which strictly speaking is not a check according to that definition but i will still want to count them as character comparisons so this this equality is for the is fine for the first section but maybe it should be taken with a grain of salt for later uh but an immediate observation from this uh from this one is the number of checks can only be at most n times m because then we have for every guess done all the checks after most n times m comparisons we have compared all possible combinations of text and pattern positions so if we haven't figured it out till then we will never figure it out

3:38 Brute Force Method

3:39 and so guess what the brute force method does it tries all the guesses and does all the checks so you iterate with i through the positions where the pattern could start and j iterates through the positions of the pattern and you compare the appropriate characters in the text and the pattern now if you ever find a mismatch you don't really have to continue that loop so the brute force method is already not completely done it breaks out of the inner loop if it finds the first mismatch and then returns no match um well it it skips out of this inner loop and then goes with the next i and if it has not found a match for any i it returns no match and if you ever reach the end of the pattern in the checks then you have found a match right then you return this position where the match started is the algorithm clear that's as easy as it gets it it's just two for loops now interestingly this is essentially what java does in the index off method and there's a reason for that that it isn't often as bad um for example in in this let's let's maybe play this through quickly so we would um try to find this pattern abba in this

5:04 text so a matches and b matches and b matches but then this is a mismatch so it doesn't occur in the first position so you try again here but there's immediately a mismatch so you don't even have to compare these other two these other three same here and here then we have to start comparing again and here's a mismatch but then we again immediately stop here whereas here we have to continue longer and indeed this is a match that we have found our match here and here's the same thing in nicer um so red is is a mismatch uh if you compare how many comparisons in this concrete instance where needed uh it's 15 whereas this worst case n times m is is quite a bit more so it's actually not that bad uh often if the inputs are not adversarially chosen or you're very unlucky the brute force method is not unreasonable to take as a start but for a good library implementation it maybe isn't robust enough and and the reason is is this example so i i said the good thing already about it it's easy and it's not always bad but it can be quite bad in this example the text is quite boring and also the pattern is fairly boring

6:33 but nobody stops your users from checking patterns string matching with these inputs in this case you need exactly all the all the comparisons that you could possibly need okay

6:48 so nice and easy not always crappy but not quite not quite good enough for a robust implementation we can learn something from this worst case example here in particular it seems like at least this worst case has a lot of self-similarity the text is the same character repeated all over and the pattern is not too far from that either so maybe instead of treating this as a bad case maybe we can take advantage of this fact

7:26 and also and some in some cases here like you compared a's up to this point and then okay there was a mismatch and it was kind of stupid to start again but for these next three a's these two a's you already checked and you already know that the text has a's there so if you were a bit smarter about looking about your pattern first you would have been able to figure out that you don't have to compare those two it's clear that they're they're implied matches but of course the brute force method wouldn't be able to figure this out

8:04 so what can we do to improve this um there's really two big approaches and the second we'll look at in the next subsection both approaches essentially mean don't just start comparing and make uneducated guesses but instead first spend a little bit of time on analyzing the situation and that can either be the pattern or the text depending on the situation in this unit we'll we'll treat the situation as dynamic the text can change all the time and the pattern is given to us when we create before it but we assume the pattern is small so taking some time to analyze the pattern is justified and so we'll have four different ways that take a look at the pattern and try to do something smarter with it than the brute force method the other option is also interesting though if the text can be expected not to change all the time then you can instead pre-process the text and that can mean you might be able to find matches much much faster and we'll do that in in unit 6. uh you may have heard of inverted indices or even sub-extreme suffix arrays that's what we'll look at there this is what's what's behind search engines or at least the the simpler versions of those um

9:13 Inverted Indices

9:27 the texts are websites now they do change once in a while but not so often that you can recompute this index but for now let's uh stay in the first approach where the text can change all the time we have no control and instead we're only looking at the pattern before we start matching