WEBVTT 00:06.070 --> 00:10.280 OK, welcome to another session on Algorithms for Internet 00:10.280 --> 00:10.980 Applications. 00:11.480 --> 00:15.500 Today I record again with the Bluetooth headset. 00:16.080 --> 00:22.280 I didn't do that the last time because there were some disturbing 00:22.280 --> 00:24.680 noises at some places. 00:25.120 --> 00:34.180 But some of you complained that the quality of the last recordings was 00:34.180 --> 00:34.900 not that adequate. 00:34.900 --> 00:37.840 So I try it again with the Bluetooth headset. 00:39.580 --> 00:42.800 So let's look what we did last week. 00:42.880 --> 00:46.380 We looked at the problem of searching for information. 00:46.540 --> 00:53.600 We looked at some final things, at routing algorithms and the TCP 00:53.600 --> 00:54.260 protocol. 00:54.400 --> 00:59.460 I showed you the UDP protocol and also briefly explained the ATM or 00:59.460 --> 01:03.600 some aspects of the ATM protocol. 01:03.600 --> 01:10.920 And then we came to this chapter on searching for information, which 01:10.920 --> 01:19.820 is one of the major applications of the World Wide Web. 01:20.980 --> 01:29.480 OK, we looked at some methods or some ways how information is 01:29.480 --> 01:29.900 presented. 01:31.380 --> 01:34.600 Things that are important there are search engines, directories, 01:34.780 --> 01:35.920 hybrid search engines. 01:36.720 --> 01:42.620 I explained to you briefly what a spider is, how an index is built, 01:42.920 --> 01:45.280 and what the search engine software has to do. 01:45.400 --> 01:51.560 I showed you this diagram where I briefly explained the steps that 01:51.560 --> 01:56.280 have to be taken when information is retrieved from the web and when 01:56.280 --> 02:00.280 queries are sent to a search engine. 02:00.960 --> 02:06.980 We looked at this measure for measuring the quality of information 02:06.980 --> 02:09.300 retrieval, recall and precision. 02:10.540 --> 02:15.540 And looked at a few things about what queries are. 02:16.740 --> 02:20.560 Briefly made a few remarks on regular expressions, showed you examples 02:20.560 --> 02:21.760 of search queries. 02:21.760 --> 02:29.220 We looked at similarity measures, some distances, similarity 02:29.220 --> 02:31.860 distances, like the hemming distance or the editing distance. 02:31.960 --> 02:36.880 For the editing distance is the more adequate measure for similarity. 02:37.820 --> 02:45.220 If we look at what we think looks like similar words. 02:45.880 --> 02:50.640 So this certainly depends on the operations that are allowed here. 02:50.640 --> 02:52.620 Usually we allow deletion and insertion. 02:53.120 --> 02:54.820 Sometimes you might allow more. 02:54.980 --> 02:58.760 And then you see the distance and the number of operations between 02:58.760 --> 02:59.680 different words. 03:00.640 --> 03:09.540 And then we came to the problem of checking for a word in some 03:09.540 --> 03:10.540 document. 03:11.580 --> 03:14.480 And this actually was the last slide. 03:15.660 --> 03:18.920 Let me just briefly come back to that here. 03:18.920 --> 03:24.780 This was the last slide where we just looked at a very naive approach 03:24.780 --> 03:28.860 to checking for the occurrence of a pattern in a document. 03:30.480 --> 03:37.980 And the naive way would be just to sketch this non-deterministic 03:37.980 --> 03:39.040 automaton here. 03:39.040 --> 03:46.760 And then we would just have this very 03:49.850 --> 03:54.890 simple automaton, which translated into a program looks like this 03:54.890 --> 03:55.310 here. 03:56.470 --> 03:57.890 A simple program. 03:58.490 --> 04:03.710 And if we look at the complexity of that or the cost of that program, 04:03.710 --> 04:08.650 what you immediately see is that you have two loops nested into each 04:08.650 --> 04:08.970 other. 04:10.050 --> 04:19.290 And one loop is corresponding to the number of symbols in the document 04:19.290 --> 04:21.530 minus the length of the pattern. 04:22.350 --> 04:27.610 And in there we, as you see here, just go over the pattern. 04:28.250 --> 04:30.430 And so here we have two loops. 04:30.430 --> 04:37.850 So obviously the complexity of this would be order of n times m, which 04:37.850 --> 04:40.470 is quite expensive. 04:41.250 --> 04:45.870 If you have a long pattern in a very large document, this certainly 04:45.870 --> 04:47.050 will take some time. 04:48.130 --> 04:54.630 So down there it's written also that this is time order of n times m. 04:54.630 --> 04:59.950 And now you can immediately see that there might be ways of making 04:59.950 --> 05:00.750 this more efficient. 05:01.470 --> 05:04.230 Some of you may have seen these algorithms. 05:04.310 --> 05:06.430 Who of you knows the algorithm of Knuth-Morris-Pratt? 05:07.210 --> 05:08.030 None of you. 05:08.190 --> 05:10.110 OK, so all those who know it are not here. 05:12.250 --> 05:17.730 And so as you see, this is quite old, almost 30 years old, this 05:17.730 --> 05:18.210 algorithm. 05:18.210 --> 05:25.110 And Knuth-Morris-Pratt looked at the problem of pattern matching. 05:25.910 --> 05:33.850 And the major and very straightforward idea is to just exploit the 05:33.850 --> 05:38.970 knowledge that you have when you notice that there is a mismatch. 05:38.970 --> 05:42.130 So if you notice that there is a mismatch, for example, at this 05:42.130 --> 05:47.710 position here, then certainly all the parts that you just had looked 05:47.710 --> 05:52.450 at here, which I now have indicated here with these lines, with these 05:52.450 --> 05:57.810 shaded lines, then what you would certainly know is that this part 05:57.810 --> 06:00.970 there matched the pattern. 06:01.110 --> 06:06.350 So the prefix of the pattern actually occurred, but just at the 06:06.350 --> 06:09.350 position j of the pattern there was a mismatch. 06:10.010 --> 06:15.910 And now the question is, can we exploit that knowledge? 06:16.110 --> 06:18.230 Can we exploit the information we have? 06:18.590 --> 06:21.370 If we can exploit that knowledge, it might be possible. 06:22.170 --> 06:24.470 Let me just check something very briefly. 06:26.030 --> 06:29.290 Yes, just wanted to check whether the audio is still running. 06:29.290 --> 06:29.970 It is running. 06:31.070 --> 06:40.490 We can exploit this information by, for example, moving this pattern 06:40.490 --> 06:43.470 by more than one position to the right. 06:43.550 --> 06:47.870 In the naive algorithm, we would have just moved the pattern one step 06:47.870 --> 06:53.970 at a time, and for every mismatch would just have tried it at the next 06:53.970 --> 06:54.430 position. 06:55.110 --> 06:58.990 And now we would just exploit the information that we have there. 06:59.270 --> 07:01.610 And if we exploit that, what can we do? 07:02.250 --> 07:06.230 What we can do is indicated in this visualization here. 07:06.450 --> 07:07.530 This is our pattern. 07:08.510 --> 07:12.130 And now we want to, like what we want to do is we want to move the 07:12.130 --> 07:16.230 pattern by some distance to the right. 07:17.230 --> 07:25.190 And now we know that a certain part, the prefix, also occurred in the 07:25.190 --> 07:25.750 document. 07:26.830 --> 07:37.650 And so if we move our pattern to the right, then certainly we should 07:37.650 --> 07:40.890 look at what kind of symbols are there. 07:40.890 --> 07:48.770 So if there is some prefix of our pattern that occurs again as a 07:48.770 --> 07:55.930 suffix just to the left of this mismatch, then certainly we could just 07:55.930 --> 08:02.150 put our pattern that much to the right. 08:05.310 --> 08:12.350 So if you would move it further than that, then you might have 08:12.350 --> 08:15.610 overlooked a possible occurrence of a pattern. 08:17.770 --> 08:24.810 And if you would move it by a smaller distance, by just a smaller 08:24.810 --> 08:29.150 part, then you would rely on a larger prefix. 08:29.150 --> 08:37.130 So what we would look at is we would look for the largest prefix. 08:37.470 --> 08:44.770 So the largest prefix here that occurs also as a suffix of this part. 08:46.910 --> 08:52.010 And if we know that, then we know the maximum distance that we can 08:52.010 --> 08:59.470 move our pattern to the right without missing any pattern matches. 09:00.710 --> 09:05.130 And this is expressed in this function next j. 09:05.710 --> 09:11.350 So next j means we have a mismatch at position j in our pattern. 09:11.930 --> 09:21.250 And we look for the next position of our pattern that should be 09:21.250 --> 09:25.610 compared to the current position at our document. 09:26.250 --> 09:31.050 So di is the current symbol in our document. 09:31.050 --> 09:36.630 And we look for the next symbol, for the next position of the pattern 09:36.630 --> 09:39.950 that should be placed exactly underneath di. 09:41.510 --> 09:42.890 And which is that? 09:43.090 --> 09:47.710 Well, we look for this position here, next j. 09:48.530 --> 09:53.870 This is some w... I think I have an i down there. 09:54.850 --> 09:58.350 But this certainly is a different i from the one up here. 09:58.350 --> 10:06.650 So this symbol w, something certainly should be different from wj. 10:07.930 --> 10:10.050 So it is here, it is wi. 10:10.270 --> 10:12.770 So we look for the maximum index. 10:14.450 --> 10:19.930 The maximum index in this area here. 10:20.470 --> 10:25.010 Certainly, we only have to consider the positions 1 to j-1. 10:25.910 --> 10:33.110 Because we look for some index to the left of this position j in the 10:33.110 --> 10:33.390 pattern. 10:34.290 --> 10:37.590 So i has to be less than j. 10:39.350 --> 10:45.110 And we look for the maximum value, so the next symbol, that is 10:45.110 --> 10:47.770 certainly different from wj. 10:47.770 --> 10:53.870 Otherwise, it wouldn't make sense to position the pattern at this 10:53.870 --> 10:56.110 place, because there would be a mismatch again. 10:57.890 --> 11:04.450 And we must make sure that all the symbols to the left of this symbol 11:04.450 --> 11:17.470 wi here, all these symbols here occur also at this position. 11:18.870 --> 11:28.290 This is expressed in the second part here, that all the indices, I 11:28.290 --> 11:34.670 don't know whether I actually explained this notation, some value in 11:34.670 --> 11:43.210 square brackets, this is the set 1 to i, just an abbreviation for the 11:43.210 --> 11:44.310 numbers from 1 to i. 11:44.850 --> 11:57.390 So here, for all indices from 1 to i-1, the values wk, in this case, 11:58.770 --> 12:02.170 are supposed to occur again at a later position. 12:02.310 --> 12:09.310 This is exactly comparing positions in these two parts of the pattern. 12:10.530 --> 12:17.470 So this is this function, which looks for the next reasonable 12:17.470 --> 12:17.930 position. 12:17.930 --> 12:22.710 We certainly have to look for the maximum index i, because otherwise 12:22.710 --> 12:28.490 we might position the pattern too far to the right. 12:30.010 --> 12:34.250 I hope that this was clear how we do that. 12:35.090 --> 12:36.930 I will show you examples for that. 12:37.830 --> 12:41.910 Certainly, we have to initialize or to look at the extreme values. 12:41.910 --> 12:48.110 If this set here is empty, then the maximum shall be 0. 12:48.290 --> 12:52.390 That means that, for example, next of 1 is 0. 12:53.370 --> 12:59.790 Now, next of 1, if we are at the first position of the pattern, then 12:59.790 --> 13:02.890 certainly the next position will be position 0. 13:03.410 --> 13:08.810 That means we have to proceed to the next value. 13:08.810 --> 13:14.330 So if the mismatch had occurred here, for example, already, 13:17.710 --> 13:24.970 then it certainly doesn't make sense to... 13:24.970 --> 13:28.310 Well, there is no other symbol that we can compare to, so we have to 13:28.310 --> 13:33.390 move the pattern 1 position to the right, and we also have to 13:33.390 --> 13:36.270 increment the index in the document by 1. 13:37.030 --> 13:41.890 So if the index is 0, it means we just move it 1 to the right, or to 13:41.890 --> 13:43.230 the right of the current position. 13:45.550 --> 13:50.810 If we have that next function, we can easily formulate our Knuth 13:50.810 --> 13:53.350 -Morris -Pratt search algorithm. 13:53.670 --> 13:56.490 So it's very similar to the algorithm that we just saw before. 13:56.610 --> 14:01.450 The only difference is that we now look for these shifting distances. 14:02.230 --> 14:08.810 So initially, we start two pointers in our document, and the pattern 14:08.810 --> 14:15.150 just at the initial positions, and now that certainly corresponds to 14:15.150 --> 14:18.510 the situation that is visualized there, corresponds to a later part in 14:18.510 --> 14:19.450 the algorithm. 14:19.910 --> 14:28.690 So we start by setting it to the first positions, and then if j is 0, 14:28.950 --> 14:35.270 well, j equals 0 would mean we have to increment our values, because 14:35.270 --> 14:40.510 the position is to the right of the current position in our text, in 14:40.510 --> 14:41.030 our document. 14:41.970 --> 14:50.050 If j is not equal to 0, but the current symbol in the document and the 14:50.050 --> 14:54.590 symbol in the pattern match, then we just proceed to the next position 14:54.590 --> 14:57.150 and check that again. 14:57.870 --> 15:03.420 If, by incrementing j, we got beyond the index of... 15:04.450 --> 15:10.990 if we got beyond the pattern, it means that we have actually noticed 15:10.990 --> 15:14.730 that all the symbols of the pattern match. 15:14.810 --> 15:18.230 That means we have to report a match at position i minus m. 15:19.050 --> 15:24.950 And now, if we would look for just one matching pattern, then we would 15:24.950 --> 15:29.170 stop, but here I assume that we would like to go on and look for the 15:29.170 --> 15:35.510 next occurrence of a pattern, and so there we would look for the next 15:35.510 --> 15:43.890 reasonable symbol that should be compared to the current symbol that 15:43.890 --> 15:46.770 we have reached in the document. 15:46.770 --> 15:52.950 So there we use the next function to move the pattern the appropriate 15:52.950 --> 15:53.670 distance. 15:54.290 --> 16:01.470 If this was not true, that means if j is not equal to 0 and the 16:01.470 --> 16:07.270 document does not coincide with the pattern at this position, then we 16:07.270 --> 16:12.070 know there is a mismatch and we move the pattern by the appropriate 16:12.070 --> 16:19.890 distance and the next symbol looked at in the pattern is the next j 16:19.890 --> 16:20.410 symbol. 16:20.810 --> 16:26.470 And this is just repeated until we actually have looked at all the 16:26.470 --> 16:27.970 symbols in our document. 16:29.050 --> 16:35.450 And if you look at that algorithm, you immediately see that our value 16:35.450 --> 16:43.390 i is only incremented so whenever we get into this branch of this if 16:43.390 --> 16:45.790 statement, we increment i by 1. 16:47.770 --> 16:53.470 j is also incremented at these times, and sometimes j will be 16:53.470 --> 16:57.730 decremented to smaller values just by these calls of the next 16:57.730 --> 16:58.190 function. 16:59.790 --> 17:06.810 And so, definitely i is incremented exactly n times, and whenever i is 17:06.810 --> 17:12.690 incremented, j is also incremented, and j cannot be decremented more 17:12.690 --> 17:14.690 than i is incremented. 17:15.150 --> 17:22.050 This is also clearly true, and that means we have maximally order of n 17:22.050 --> 17:22.590 operations. 17:23.210 --> 17:30.650 So, this means that we have linear time, so this factor m disappeared 17:30.650 --> 17:33.710 from our pattern matching algorithm. 17:35.030 --> 17:39.510 So, just by exploiting this knowledge about the prefix that we have 17:39.510 --> 17:44.370 already looked at, allows for a reduction of the complexity of that 17:44.370 --> 17:45.470 pattern matching algorithm. 17:46.430 --> 17:48.810 So, it's significantly faster. 17:49.970 --> 17:54.390 The problem is, how do we actually compute that value next? 17:55.930 --> 18:01.930 Certainly, we need some pre-processing for that, and the algorithm 18:01.930 --> 18:04.670 looks very similar to the one that we had just looked at. 18:05.070 --> 18:10.190 So, if we look at this algorithm here, and compare it to the one that 18:10.190 --> 18:13.550 is shown here, they look very similar. 18:14.050 --> 18:20.330 So, essentially what we do here is, we now analyze the structure of 18:20.330 --> 18:26.650 the pattern, and we just match the pattern within the pattern, 18:26.910 --> 18:27.450 essentially. 18:29.090 --> 18:31.370 This works like follows. 18:31.710 --> 18:35.650 Now, we have our value j, 18:39.270 --> 18:47.610 and j is set to 1, so we assume that the index j refers to this copy 18:47.610 --> 18:50.770 of the pattern, and i refers to that copy. 18:53.030 --> 18:53.690 Yes, 18:57.080 --> 18:57.460 it's true. 19:00.060 --> 19:03.260 It refers to that part, I think. 19:04.580 --> 19:06.960 We can easily find out. 19:09.570 --> 19:14.440 Here, we set j to 1, i to 0. 19:15.280 --> 19:18.480 Next j is set to 0. 19:18.480 --> 19:21.400 We know that next of 1 has to be set to 0. 19:21.580 --> 19:25.920 That was the default value for the value 1. 19:27.040 --> 19:32.600 And we also need a value m plus 1. 19:32.960 --> 19:36.920 At position m plus 1, that means we add an additional symbol to the 19:36.920 --> 19:44.340 right of our pattern, in order to make sure that we can detect the end 19:44.340 --> 19:47.680 of this pattern in an appropriate way. 19:47.680 --> 19:51.820 And this value x that we put there has to be different from all the 19:51.820 --> 19:52.740 symbols in the pattern. 19:53.140 --> 20:00.360 You will see in a moment why we actually need that. 20:01.120 --> 20:06.520 Now, we start by checking whether i is 0. 20:06.600 --> 20:15.360 Initially, i is 0, so we increment i and j. 20:16.280 --> 20:26.140 And that means now i is set to 1, and j is set to 2. 20:26.640 --> 20:36.480 And that means we compare w of 1 and w of 2 for the first two symbols. 20:36.720 --> 20:42.760 That means we position, essentially, our pattern at the second 20:42.760 --> 20:48.020 position of the pattern and compare those two elements. 20:49.620 --> 20:55.080 Okay, and then we compute here these, or we can determine the next 20:55.080 --> 20:55.440 values. 20:55.580 --> 20:59.640 I will not explain more looking at this algorithm. 21:00.140 --> 21:01.940 I will give you an example in a moment. 21:02.620 --> 21:04.400 I just wanted to analyze it. 21:04.400 --> 21:09.360 If we just look at the time that this algorithm needs, you immediately 21:09.360 --> 21:13.860 see that it has the same structure as the Knuth-Morris-Pratt algorithm 21:13.860 --> 21:14.620 for searching. 21:15.540 --> 21:22.780 And so the time complexity of that is linear, so we have to spend 21:22.780 --> 21:24.540 linear time in the length of the pattern. 21:25.840 --> 21:33.880 The correctness has to be proved, certainly, and to prove that we need 21:33.880 --> 21:35.440 some prefix condition. 21:36.360 --> 21:41.980 And here we have our loop, and I just state this invariant. 21:43.660 --> 21:45.440 What does it mean? 21:47.360 --> 21:55.200 For all k from 1 to i, next of k is defined correctly. 21:56.480 --> 22:06.020 And for all k of all these symbols, we have that Wk is Wj minus i plus 22:06.020 --> 22:06.220 k. 22:06.300 --> 22:11.440 This was the condition that we had to check whether these two parts 22:11.440 --> 22:12.500 here coincide. 22:14.100 --> 22:23.860 And so this is a prefix condition, an invariant of the loop that we 22:23.860 --> 22:24.700 can prove. 22:24.700 --> 22:29.280 I don't want to go formally through that proof. 22:29.420 --> 22:35.360 I have written it up on this slide here, but I think it's better for 22:35.360 --> 22:41.340 you to just read it through and look at what is stated here, and then 22:41.340 --> 22:44.760 you should be able to verify that the statements here are correct. 22:45.180 --> 22:49.540 I would like to just show you an example how this algorithm works, and 22:49.540 --> 22:53.680 in that way you can understand the major steps of that algorithm. 22:53.680 --> 22:59.080 So let's look at a very, well, certainly artificially constructed 22:59.080 --> 23:00.840 word, Abracadabra. 23:01.520 --> 23:06.440 And you see that here we have situations as the ones that we are 23:06.440 --> 23:10.320 interested in, prefixes that reoccur as suffixes. 23:10.600 --> 23:15.460 So for example, Abra, you see is a prefix and a suffix. 23:16.160 --> 23:22.740 And so we have structures that might be important for our next 23:22.740 --> 23:23.220 function. 23:24.180 --> 23:30.900 Now we have just numbered all these positions in our document, and we 23:30.900 --> 23:33.720 set our indices. 23:34.560 --> 23:44.080 So we set our j value to 1, and i certainly is 0. 23:44.660 --> 23:50.400 And we set next of j to 0, next of 1 is set to 0. 23:51.060 --> 23:59.940 We need our extra element, oh, we have i is set to 0, that means we 23:59.940 --> 24:09.280 now have the situation that, well, we want to compare our document, 24:09.860 --> 24:11.680 our pattern with a pattern. 24:12.320 --> 24:17.060 If this i is 0, it means we have to move everything to the right, as 24:17.060 --> 24:19.300 we will do in this part here. 24:19.900 --> 24:25.700 But now we also have to add this extra element x, which is different 24:25.700 --> 24:28.340 from all the symbols in our pattern. 24:29.460 --> 24:35.320 And then we actually can start, and yeah, here. 24:37.360 --> 24:43.020 We go into the loop, i is 0, that means we have to increment i and j. 24:43.820 --> 24:51.960 And so j is set to 2, and i is set to 1, that means now we compare 24:51.960 --> 24:55.020 those two positions here. 24:56.140 --> 25:04.460 And these are different, so wi is not equal to wj, and therefore we 25:04.460 --> 25:07.700 set next of j equal to i. 25:08.980 --> 25:18.880 Now i has the value 1, and so next of 2 is set to 1. 25:20.280 --> 25:26.180 So if we had looked at position 2, the next reasonable position to 25:26.180 --> 25:28.520 look at would be 1. 25:28.660 --> 25:34.440 And you see this a is different from b, and the part to the left of a 25:35.940 --> 25:40.860 is equal to the part left of b. 25:41.380 --> 25:42.000 It's empty. 25:43.180 --> 25:48.240 So it's a simple occurrence of this situation, just to remind you of 25:48.240 --> 25:50.160 what we looked at. 25:50.600 --> 25:56.640 We looked at something where we have a structure like this, and the 25:56.640 --> 26:00.520 symbols at these two positions here should be different. 26:01.000 --> 26:03.000 This is what we always look for. 26:03.900 --> 26:13.240 Okay, so next j is set to, or next 1 is set to, next of 2 is set to 1, 26:13.880 --> 26:16.400 and we continue. 26:19.780 --> 26:30.980 So we repeat here, i is not equal to 0, wi is not equal to wj, so i is 26:30.980 --> 26:32.560 set to next i. 26:33.120 --> 26:40.820 Now, i in this case was 1, next of 1 is 0, so that means our pattern 26:40.820 --> 26:45.900 has to be moved to the right again. 26:47.180 --> 26:53.140 And because i is 0, we increment i and j, and we have the pattern at 26:53.140 --> 26:53.760 this position. 26:53.760 --> 27:05.440 We compare w1 and w3, and here we again have a mismatch, and so we 27:05.440 --> 27:14.180 have to set next of 3 again to 1, as we did before. 27:15.820 --> 27:28.600 And then again we get into this loop, we get into this i is not equal 27:28.600 --> 27:35.320 to 0, and the things here don't match, we have to move our pattern 27:35.320 --> 27:42.660 again, and now we compare a and a, here so we are at this position 27:42.660 --> 27:50.780 now, wi is equal to wj, that means next of, in this case 4, is set to 27:50.780 --> 27:58.780 next of 1, next of i, because here we have a situation where we have 27:58.780 --> 28:07.020 coinciding symbols, the two symbols that we look at are the same, and 28:07.020 --> 28:13.980 so we have to look for the next occurrence of a symbol where this 28:13.980 --> 28:21.700 condition here is true, that these two small suffixes coincide, but 28:21.700 --> 28:27.020 these symbols wi and wj are different. 28:27.500 --> 28:31.720 So the next position can only be the next position if we look for this 28:31.720 --> 28:37.180 next i, next i has been defined already, since i is smaller than j, 28:38.140 --> 28:44.700 and so we can define next j to be that value. 28:44.700 --> 28:54.680 So next of 1 is 0, and we have the next loop, and we continue. 28:54.860 --> 29:03.060 Now we get into this test here, and we have i not equal to 0, and wi 29:03.060 --> 29:17.240 is equal to wj, so w4 is equal to w1, and so we increment and look at 29:17.240 --> 29:22.480 the next position, and here we have k and b, these are different, and 29:22.480 --> 29:28.360 so in this case we get next of 5 to be the value 2, and in this way it 29:28.360 --> 29:28.900 continues. 29:30.160 --> 29:35.220 I don't have to go through all the details here, but you see that 29:35.220 --> 29:41.700 again we had a mismatch there, again here we had to set the value of 7 29:41.700 --> 29:50.780 to 2, and then here we have a match, so we again get the value of 0, 29:51.300 --> 29:57.540 then we have again a match at position 9, and so we have to set this 29:57.540 --> 30:04.180 value here to the value of next of 2, next of 2 is 1, so this value 30:04.180 --> 30:09.860 has to appear there, then we have again a match, so next of 10 has to 30:09.860 --> 30:20.580 be the value of next of 3, next of 3 is also a 1, and then this 30:20.580 --> 30:26.540 continues to get to next 11, and then here we have 4, because next of 30:26.540 --> 30:32.180 4 was the value 0, and that's it, we are at the end. 30:32.680 --> 30:37.600 This x is different from all the other symbols, that means that we 30:37.600 --> 30:44.600 definitely get into this statement here, and so finally we have next 30:44.600 --> 30:50.020 of 12, in this case, is set to 5. 30:51.960 --> 30:58.080 And now we are done, we have for all the possible values of the index 30:58.080 --> 31:03.760 j, we have a value for the next function, and this always leads us to 31:03.760 --> 31:07.860 the next reasonable position in our pattern. 31:09.160 --> 31:19.360 I hope that this was clear enough, but just try to get through that 31:19.360 --> 31:26.060 example yourself, you have a chance to do that in the assignments, I 31:26.060 --> 31:26.280 guess. 31:27.740 --> 31:32.300 Now, we have an algorithm that runs in linear time, what else can we 31:32.300 --> 31:32.580 get? 31:33.300 --> 31:35.420 Is it possible to improve even on that? 31:37.100 --> 31:42.060 And the interesting thing is that it is possible to improve on it. 31:42.760 --> 31:46.240 Naively, you would say, how can you improve on linear time, because 31:46.240 --> 31:48.840 you have to look at all the positions in the text, and that's linear 31:48.840 --> 31:49.280 time. 31:50.520 --> 31:56.020 But you have a pattern that has a certain length, so the idea of Boyer 31:56.020 --> 32:02.380 and Moore was that I just look at the pattern in a different way, let 32:02.380 --> 32:09.880 me just briefly write it down, so if we position our pattern here, and 32:09.880 --> 32:15.220 we notice that there is a mismatch at the rightmost position of our 32:15.220 --> 32:21.780 pattern, then we might be able to immediately move our pattern to the 32:21.780 --> 32:29.020 right, and if we are lucky, we might be able to move it completely to 32:29.020 --> 32:33.060 the right of that position, because we maybe know that if we have a 32:33.060 --> 32:42.260 mismatch at the rightmost position, there won't be a match at any 32:42.260 --> 32:49.500 other position in there, so we just can move it over there, and then 32:49.500 --> 32:54.580 if we are lucky, we get only very few positions in our text that we 32:54.580 --> 32:55.580 actually have to look at. 32:56.620 --> 33:02.860 And that means, if we are lucky, we would have just order of n over m 33:02.860 --> 33:11.460 comparisons, because we just have to look at these rightmost symbols 33:11.460 --> 33:15.360 of our pattern, if we can always move it by the maximum distance, then 33:15.360 --> 33:17.540 we would have sublinear behavior. 33:18.440 --> 33:22.800 And that would mean, if we have a very long pattern that we look at, 33:22.960 --> 33:27.760 or that we look for, the search for the occurrence of this pattern 33:27.760 --> 33:30.460 would be very efficient, very fast. 33:31.800 --> 33:37.080 And so, one should try to find out how we can actually implement that, 33:37.120 --> 33:41.540 and how we can find out how far we can actually move our pattern to 33:41.540 --> 33:48.340 the right after we have seen a mismatch in our comparison of the text. 33:51.000 --> 33:54.720 I should certainly state also something on the worst case. 33:56.400 --> 34:00.120 It's always necessary to also look at the worst case, and the worst 34:00.120 --> 34:04.240 case certainly would be that you would start at the rightmost 34:04.240 --> 34:05.420 pattern... 34:05.420 --> 34:06.020 Sorry. 34:10.140 --> 34:10.700 Sorry. 34:11.860 --> 34:16.400 At the rightmost symbol, and then you would all the way go to the 34:16.400 --> 34:23.240 left, compare with all the other elements, and have, like you don't 34:23.240 --> 34:27.500 have mismatch, just have matches, and only at the final position you 34:27.500 --> 34:28.140 have a mismatch. 34:28.760 --> 34:33.140 And then, maybe you are unlucky and you can only move the pattern by 34:33.140 --> 34:37.320 one position, and again, you would start at the rightmost position, go 34:37.320 --> 34:40.680 all the way back, and check for matches. 34:42.440 --> 34:47.740 And so, if you are unlucky, you would have n times m comparisons, as 34:47.740 --> 34:49.680 bad as the naive algorithm. 34:50.540 --> 34:56.620 And so, this would be very bad, but if you are lucky, you have an 34:56.620 --> 34:58.960 order of n over m sublinear behavior. 34:59.700 --> 35:04.060 And on the average, which certainly is hard to analyze, because you 35:04.060 --> 35:08.440 have no idea normally what the distribution of your documents is, and 35:08.440 --> 35:12.240 if you don't know anything about the probability of the occurrence of 35:12.240 --> 35:16.140 certain documents, you cannot make any statement on the average case. 35:17.260 --> 35:25.500 But if you just run simulations on collections of documents, it shows 35:25.500 --> 35:28.360 that the average behavior is sublinear. 35:29.020 --> 35:35.840 And so, here, under reasonable assumptions, you get here sublinear 35:35.840 --> 35:39.940 behavior, which certainly is a significant improvement over the 35:39.940 --> 35:42.080 initial naive algorithm that we had. 35:42.740 --> 35:46.600 Now, the question is how we can actually determine the shift distance 35:47.140 --> 35:53.120 that we can use if we have a mismatch. 35:53.120 --> 35:59.980 So, the mismatch occurs, again, at a position in our text, document 35:59.980 --> 36:06.980 .text.di, that's the symbol, and it does not match the current symbol, 36:07.080 --> 36:08.460 wj, in our pattern. 36:09.380 --> 36:15.040 Now, the question is how far to the right might we move our pattern. 36:15.040 --> 36:23.100 What you can see here is, in this drawing, two different aspects. 36:23.620 --> 36:30.900 One is, well, it may be that the symbol di occurs somewhere in our 36:30.900 --> 36:33.900 pattern, at a position as shown here. 36:34.600 --> 36:39.520 Then it would be reasonable, like if that is the rightmost occurrence 36:39.520 --> 36:45.440 of this symbol di in our pattern, then we could immediately move our 36:45.440 --> 36:51.000 pattern such that di is positioned below the di in our document. 36:52.900 --> 36:57.140 And then we would, well, what would we have to do after that? 36:57.260 --> 37:05.560 Certainly, we would know there is a match at this point here, but what 37:05.560 --> 37:07.800 about the symbols up here? 37:07.800 --> 37:16.540 So we certainly would have to restart our comparison at this position 37:16.540 --> 37:21.000 here, like we would have to start again at the rightmost end, but at 37:21.000 --> 37:26.580 least we would know that the symbol di occurs at that position. 37:26.760 --> 37:33.980 So if there is a chance at all that this pattern matches, then the 37:33.980 --> 37:41.260 earliest point where it could match is at this position, where di in 37:41.260 --> 37:45.360 the pattern is positioned under the di in the text. 37:46.220 --> 37:53.940 Another point is, we had already checked all the elements in this area 37:53.940 --> 37:54.380 here. 37:55.380 --> 38:00.880 These elements in this area match the elements in, or the symbols, in 38:00.880 --> 38:02.480 the suffix of our pattern. 38:04.340 --> 38:06.460 And so we should exploit that information. 38:07.420 --> 38:16.500 And if we can exploit that, it means, well, this suffix here should 38:16.500 --> 38:23.440 also occur as a prefix of the part to the right of the symbol di. 38:24.420 --> 38:29.800 Otherwise, it wouldn't make sense to position the pattern like that, 38:30.100 --> 38:36.840 because if it would not occur here, if this would not occur again 38:36.840 --> 38:40.380 there, then there couldn't be a match. 38:40.380 --> 38:46.780 And so we have to look for this in our pattern, and again you see 38:46.780 --> 38:53.680 something as we had seen before, but just shifted or reflected. 38:55.520 --> 39:02.280 Before we had the prefix of the pattern that reoccurred as a suffix, 39:02.660 --> 39:06.100 and here we have a suffix that reoccurs here as a prefix. 39:07.040 --> 39:08.780 So we have to look at that. 39:12.200 --> 39:19.480 So, here are the current, or just the different notations that we 39:19.480 --> 39:28.360 need, and we would, in this time, look for the distance that we can 39:28.360 --> 39:29.280 move our pattern. 39:29.280 --> 39:36.160 Before, in Knuth-Morris-Pratt, the next function gave us the position 39:36.160 --> 39:41.220 in our pattern that should be looked at next. 39:41.680 --> 39:45.360 Here, we look for the distance that we should move our pattern. 39:46.000 --> 39:50.380 After this shifting of the pattern, we always have to restart our 39:50.380 --> 39:55.220 comparisons at the rightmost position, at the right end, because we 39:55.220 --> 39:59.240 always start there with our comparisons. 40:00.320 --> 40:03.480 Now, there are two heuristics that you can use. 40:04.140 --> 40:09.040 The first heuristic is the one that I indicated here by writing here 40:09.040 --> 40:09.980 the Di again. 40:10.540 --> 40:15.980 So the occurrence heuristic means we shift W to the next occurrence of 40:15.980 --> 40:18.340 the symbol Di in W. 40:19.940 --> 40:28.900 And this just leads to a table Delta, where for every character of our 40:28.900 --> 40:37.120 alphabet, we enter the distance to the rightmost occurrence of this 40:37.120 --> 40:38.580 character in the pattern. 40:39.320 --> 40:45.740 So we look at our pattern and look for the rightmost occurrence of a 40:45.740 --> 40:47.260 symbol in that pattern. 40:48.600 --> 40:50.220 Look at that distance. 40:51.780 --> 41:00.340 And that means this Delta of C is M, if M was the length of the 41:00.340 --> 41:10.180 pattern, if C is not in W, and it would be M minus R if C is WR. 41:10.180 --> 41:17.940 So here, that would be our R, then this would be position R, and then 41:17.940 --> 41:20.860 this here would be just M minus R. 41:22.780 --> 41:32.360 So it's M minus R if C is this WR and C does not occur anywhere to the 41:32.360 --> 41:34.160 right of position R. 41:35.440 --> 41:42.060 Okay, and now we can compute the shift distance if we have a mismatch 41:42.060 --> 41:43.720 at a certain position. 41:44.620 --> 41:50.340 Well, now we want to use our distance table Delta. 41:52.360 --> 41:55.800 And now we have to look at what is entered there. 41:55.800 --> 42:04.680 It may be that our symbol occurs at, like the symbol C, that is, or 42:04.680 --> 42:13.320 the information in our distance table may refer to, well, assume this 42:13.320 --> 42:17.260 Di occurs somewhere to the right of the current position. 42:18.400 --> 42:24.460 Like if M minus J... 42:25.580 --> 42:27.120 What is M minus J? 42:27.320 --> 42:31.260 J is the current position here, this here is M minus J. 42:33.700 --> 42:40.760 Now, if M minus J is greater than Delta of C, that means this 42:40.760 --> 42:47.920 character C occurs to the right of the current position, and then we 42:47.920 --> 42:56.360 just shift our pattern by this distance. 42:56.560 --> 42:58.600 Why by this distance? 42:59.260 --> 43:08.820 Well, we know that this symbol here does not occur again at anywhere 43:08.820 --> 43:12.720 to the right of this position here. 43:12.720 --> 43:20.900 And so the next possible match will occur or won't occur at a position 43:20.900 --> 43:23.660 where this symbol is in this area. 43:23.760 --> 43:30.580 So we have to move this position here, or this position of our 43:30.580 --> 43:40.660 pattern, to the right of the first position that we had not looked at 43:40.660 --> 43:41.340 before. 43:41.340 --> 43:44.800 And that is just the distance Delta of C plus 1. 43:47.040 --> 43:55.560 Now, if this symbol occurred to the left of WJ, which is the situation 43:55.560 --> 44:02.940 as indicated here, then we would shift our document by, well, which 44:02.940 --> 44:03.560 distance? 44:04.560 --> 44:12.540 We would move it such that the symbol is located underneath this 44:12.540 --> 44:23.500 position of WJ here, and that means our distance Delta C has to be 44:23.500 --> 44:28.000 reduced by M minus J to get exactly the right value. 44:28.000 --> 44:33.480 So this was the case if M minus J is less than Delta of C. 44:33.600 --> 44:38.760 So if the symbol occurs to the left of our WI. 44:41.120 --> 44:46.920 Okay, I hope this was clear enough. 44:48.180 --> 44:52.380 If you just look at the two different possibilities for the occurrence 44:52.380 --> 44:56.880 of the symbol C, then you see that there is no other way as doing it 44:56.880 --> 44:58.020 like this here. 45:00.140 --> 45:02.380 Okay, that's one heuristic. 45:03.340 --> 45:09.880 Now we know we can use our knowledge of the symbols that occur in our 45:09.880 --> 45:13.160 pattern to determine this shift distance. 45:14.800 --> 45:18.260 So, okay, the rightmost C is to the right of position J. 45:18.260 --> 45:24.000 Okay, these were the two explanations here that I gave already. 45:25.660 --> 45:34.740 And if you just consider looking for symbols in a normal pattern in 45:34.740 --> 45:42.580 our alphabet, then for most of the 26 symbols of our alphabet, you 45:42.580 --> 45:43.760 would have mismatches. 45:43.760 --> 45:47.720 And if you have a mismatch, that would mean you can move by the 45:47.720 --> 45:52.460 maximum distance, which certainly is important. 45:53.500 --> 46:01.500 So since only a few symbols will occur in a word, then you get large 46:01.500 --> 46:10.340 shift distances and sublinear behavior for many patterns. 46:11.020 --> 46:16.420 Certainly the longer the pattern is, the more symbols will be in 46:16.420 --> 46:20.240 there, and then you might have shorter distances. 46:21.940 --> 46:24.280 Now we can try to improve the heuristic. 46:25.180 --> 46:31.480 We just, like what we did here, we just looked at the rightmost 46:31.480 --> 46:36.920 occurrence of C in the pattern, and we did not consider the current 46:36.920 --> 46:39.880 position in the pattern that we are looking at. 46:42.100 --> 46:44.540 So we could also do that. 46:45.120 --> 46:49.120 So we could take into account also the current position in the 46:49.120 --> 46:56.040 pattern, and then we would have a two-dimensional table, and so then 46:56.040 --> 47:01.420 we could appropriately adjust our occurrence heuristic and get 47:01.420 --> 47:03.980 improved values for that. 47:07.420 --> 47:08.700 And if 47:13.330 --> 47:24.030 J is less than M, we shift W with respect to WM, and not with respect 47:24.030 --> 47:26.590 to the position at position J. 47:26.830 --> 47:28.010 Okay, what does this mean? 47:28.990 --> 47:31.010 We look at... 47:34.890 --> 47:41.450 If we are in a situation like this, does it make sense really to look 47:41.450 --> 47:46.210 for a reoccurrence of that symbol we just looked at, like this DI in 47:46.210 --> 47:46.850 our pattern? 47:47.990 --> 47:53.910 Isn't it more reasonable to look where in our... 47:53.910 --> 48:02.130 for example, for a reoccurrence of the last symbol in our pattern, in 48:02.130 --> 48:03.130 this pattern. 48:03.270 --> 48:12.490 So if this last symbol reoccurs somewhere to the left of this pattern, 48:13.050 --> 48:18.050 or if it does not occur, we would know if we shift our pattern, if 48:18.050 --> 48:22.870 this symbol does not occur again in our pattern, but we know it did 48:22.870 --> 48:27.830 occur up here in our document, then we have to move our pattern all 48:27.830 --> 48:30.910 the way to the right of that position in the document. 48:31.530 --> 48:34.490 This would lead to a larger shifting distance. 48:35.210 --> 48:41.350 And so this is the idea that is used in this improvement here. 48:41.670 --> 48:46.010 So you could improve the heuristic, and you could also now try to use 48:46.010 --> 48:52.410 this other information on the suffix of our pattern that we had 48:52.410 --> 48:53.210 already looked at. 48:53.610 --> 48:58.870 So this is our pattern that we had looked at, the position J, and we 48:58.870 --> 49:07.790 know that the suffix of the pattern did already occur in our document. 49:10.430 --> 49:18.650 And so the idea is we shift W to the next occurrence of the matching 49:18.650 --> 49:20.430 suffix of W. 49:20.830 --> 49:23.950 Now what is the matching suffix of W? 49:24.410 --> 49:30.350 That is this part, indicated in red now, and this part should reoccur 49:30.350 --> 49:37.150 at some position to the left, and so it means it should occur at some 49:37.150 --> 49:44.370 position J-S, it should reoccur there, and we just shift W to the next 49:44.370 --> 49:48.850 occurrence of that matching suffix. 49:49.310 --> 49:53.790 If there is no other occurrence of that matching suffix, we know we 49:53.790 --> 49:57.370 have to shift, or we can shift the pattern all the way to the right. 49:58.370 --> 50:07.530 And what I've indicated in this drawing here is expressed formally in 50:07.530 --> 50:14.570 this equation here, or this definition, the shifting distance σH, like 50:14.570 --> 50:23.110 the match heuristic, at position J is defined as the minimum S, the 50:23.110 --> 50:30.470 minimum S is this value here, so it is the rightmost occurrence, the 50:30.470 --> 50:33.730 next occurrence, of a matching suffix. 50:34.190 --> 50:42.510 Now S should be greater or equal 1, otherwise we wouldn't move, and it 50:42.510 --> 50:47.970 may be that S is greater or equal J, if S is greater or equal J, J-S 50:47.970 --> 50:54.310 would mean we would already be to the left of our pattern, so if S is 50:54.310 --> 51:01.930 greater or equal J, this statement here is true, otherwise WJ minus S 51:01.930 --> 51:04.170 should be different from WJ. 51:05.170 --> 51:07.890 So these two symbols here certainly should differ. 51:09.090 --> 51:14.350 That's an important requirement, otherwise it doesn't make sense to 51:14.350 --> 51:15.990 move it to that position. 51:16.730 --> 51:22.750 And now we have to check for these two sections here, these two 51:22.750 --> 51:29.930 sections should coincide, that means WK minus S should be equal to WK, 51:31.150 --> 51:39.510 but we have to consider the possibility that our S is already larger 51:39.510 --> 51:47.830 than S, and that would mean we would only have some initial part here 51:47.830 --> 51:54.770 of our, some prefix of our pattern that matches a prefix of the 51:54.770 --> 51:58.590 suffix, and this is just stated here. 51:58.970 --> 52:07.570 So for all the values to the right of J, here we have to check whether 52:07.570 --> 52:12.790 WK minus S is equal to WK, so these two are compared. 52:12.790 --> 52:20.570 This is exactly the formal specification of what I indicated in this 52:20.570 --> 52:26.750 drawing, and I hope that you see how that is done. 52:27.630 --> 52:32.210 The best way to understand these heuristics is to look at examples, 52:33.290 --> 52:43.250 and so if we look at this word here, banana, this suffix ANA occurs 52:43.250 --> 52:55.790 again, and here the symbol to the left of this suffix here is N, and 52:55.790 --> 53:00.290 at the next position where it occurs we have a B and also ANA. 53:00.970 --> 53:05.790 So here we have exactly that situation, the suffix ANA occurs again 53:05.790 --> 53:10.470 with the symbol B instead of N to the left of it. 53:12.710 --> 53:16.910 And so this is a word where you have such an occurrence. 53:17.410 --> 53:26.710 You can immediately imagine that for many situations you will not have 53:26.710 --> 53:34.010 any reoccurrence of the pattern in the document, and so you would get 53:34.010 --> 53:36.490 a maximum shift distance for that. 53:38.370 --> 53:46.050 So the match heuristic shifts W the more the further to the left this 53:46.050 --> 53:52.210 suffix occurs again, and if it does not occur again then you have the 53:52.210 --> 53:54.270 maximum value, the maximum shift value. 53:55.430 --> 54:01.990 So this shift heuristic is most effective for aperiodic W. 54:02.290 --> 54:05.170 If it's very periodic you get small shift distances. 54:07.520 --> 54:11.480 Now you can certainly combine those two heuristics to just compute the 54:11.480 --> 54:16.500 maximum value of those two heuristics, the occurrence heuristic and 54:16.500 --> 54:23.080 the match heuristic, and then you have the shift value that you need 54:23.080 --> 54:24.400 for your pattern matching. 54:24.400 --> 54:29.700 And that is essentially the original algorithm by Boyer-Moore. 54:30.180 --> 54:36.420 Meanwhile there are many variants of that algorithm around, and it is 54:36.420 --> 54:41.480 the fastest way of looking for patterns in documents. 54:42.020 --> 54:48.100 So if you have a program which allows you to search for the occurrence 54:48.100 --> 54:55.560 of some word in some file, and you notice that the longer your pattern 54:55.560 --> 55:02.760 is, the longer it takes to get a result, then your algorithm probably 55:02.760 --> 55:03.460 is very poor. 55:04.780 --> 55:11.960 Because if you have a longer pattern that you look for, the search 55:11.960 --> 55:13.360 should be much faster. 55:14.660 --> 55:19.980 And at least I noticed in some of the programs that I use, if I search 55:19.980 --> 55:25.800 for a certain value, it takes longer to look for longer values, which 55:25.800 --> 55:29.860 means that the search functions are not efficiently implemented. 55:32.860 --> 55:40.940 There is a funny statement in literature that this would not be 55:40.940 --> 55:43.220 effective since periodic words are rare. 55:44.040 --> 55:45.080 The opposite is true. 55:45.560 --> 55:50.960 If a word is very periodic, then you would have very short shift 55:50.960 --> 55:59.160 distances, because you would have many reoccurrences of words, and so 55:59.160 --> 56:08.780 one has to look carefully at what is written in the literature. 56:09.640 --> 56:13.620 Okay, what about the time it needs to compute these tables? 56:14.060 --> 56:18.820 The preprocessing time, you must remember we have to compute these 56:18.820 --> 56:26.660 things before we start the search, and so the time for computing these 56:26.660 --> 56:39.440 tables is just linear in the length of our pattern, and well, depends 56:39.440 --> 56:42.120 on what we use here. 56:43.520 --> 56:46.340 It can also be like in the, 56:50.910 --> 56:56.910 if we have this extended version, where we compute the two-dimensional 56:56.910 --> 57:02.310 table, we would need it, we would have a time of m times a, where a is 57:02.310 --> 57:03.310 the size of the alphabet. 57:04.730 --> 57:10.910 Okay, but at least this is only linear in the size of the pattern, so 57:10.910 --> 57:15.950 it certainly takes longer if the pattern is long, but the search gets 57:15.950 --> 57:17.750 much faster by that. 57:19.550 --> 57:23.170 I said already, there are several improved versions of the Boyer-Moore 57:23.170 --> 57:31.250 algorithm around, and they are standard in good packages on text 57:31.250 --> 57:31.710 processing. 57:32.510 --> 57:37.050 Then sometimes you don't look for just a single word, but for several 57:37.050 --> 57:42.650 words or several patterns, and then you certainly could try to look at 57:42.650 --> 57:50.050 several patterns at the same time, and that means you build a search 57:50.050 --> 57:55.990 structure that combines the information from these different words. 57:55.990 --> 58:01.850 So if you have your different words, maybe they coincide for some 58:01.850 --> 58:07.250 part, and then maybe they are different, maybe again coincide, so what 58:07.250 --> 58:12.270 you get actually is some kind of a tree, and at the leaves of these 58:12.270 --> 58:19.830 trees we have essentially checked for these different words, and at 58:19.830 --> 58:30.870 least it's much more efficient to immediately check for all the 58:30.870 --> 58:32.650 patterns in a search. 58:33.250 --> 58:36.530 This could again speed up the search significantly. 58:37.930 --> 58:43.470 And the naive approach would be to apply just k times the algorithm of 58:43.470 --> 58:47.670 Boyer -Moore, but as I just indicated, the improved approach would be 58:47.670 --> 58:53.350 to search concurrently for all k patterns, and then you compute shift 58:53.350 --> 58:59.690 distances with respect to all these k patterns, looking at such a tree 58:59.690 --> 59:07.650 -like pattern structure, and this leads to, again, a much more 59:07.650 --> 59:09.610 efficient search. 59:10.600 --> 59:19.010 So the tables get a bit larger, but the time that you have is about 59:19.010 --> 59:26.470 the same as for a single pattern, and so you get a much better 59:26.470 --> 59:27.030 algorithm. 59:27.030 --> 59:29.730 There are, like, A.O. 59:29.810 --> 59:35.730 Korazik actually published their algorithm on this before Knuth-Morris 59:35.730 --> 59:45.330 -Pratt, but they used a very similar idea, and a few years later there 59:45.330 --> 59:50.290 was another algorithm by Comins-Walter, who combined the ideas of A.O. 59:50.370 --> 59:56.290 Korazik, which is essentially the building of this pattern tree, and 59:56.290 --> 01:00:00.690 used that together with the ideas of Boyer-Moore, looking from left to 01:00:00.690 --> 01:00:02.890 right in the document. 01:00:04.810 --> 01:00:12.550 Now this was pattern matching, and so this approach is, we look at the 01:00:12.550 --> 01:00:20.770 pattern, and then we would like to search arbitrary documents as fast 01:00:20.770 --> 01:00:21.410 as possible. 01:00:22.200 --> 01:00:27.450 I already mentioned in the beginning of this chapter that there is an 01:00:27.450 --> 01:00:31.570 important other approach, which is followed in all the search engines. 01:00:31.910 --> 01:00:37.590 If you look for information in a large collection of documents, and 01:00:37.590 --> 01:00:41.670 you know you will have many queries, then it is reasonable to analyze 01:00:41.670 --> 01:00:46.390 the documents before you get these queries, to get an efficient search 01:00:46.390 --> 01:00:47.410 for arbitrary patterns. 01:00:47.410 --> 01:00:53.490 Now we get to what I had indicated on this slide, when I showed you 01:00:53.490 --> 01:00:56.350 the steps that a search engine has to follow. 01:00:57.130 --> 01:01:00.450 We look at how we actually can process a document. 01:01:01.090 --> 01:01:07.270 So we divide a document into words, and to divide a document into 01:01:07.270 --> 01:01:10.330 words essentially means, well, it looks simple. 01:01:10.510 --> 01:01:18.950 We just have here these very simple words, so you can immediately see 01:01:18.950 --> 01:01:22.790 what the words in this underlined line here are. 01:01:23.350 --> 01:01:25.570 But it's not that simple really. 01:01:26.110 --> 01:01:28.910 So you might have special characters. 01:01:29.550 --> 01:01:33.170 So what are the characters that you should use to actually separate 01:01:33.170 --> 01:01:37.090 the piece of text into words? 01:01:37.650 --> 01:01:39.450 This is called tokenizing. 01:01:39.450 --> 01:01:45.150 So we have some special characters and everything in between is 01:01:45.150 --> 01:01:46.130 supposed to be a word. 01:01:46.250 --> 01:01:50.430 But if you have something like Jean-Claude or state of the art, state 01:01:50.430 --> 01:01:55.310 of the art should be viewed as one word and should not be separated. 01:01:56.890 --> 01:01:59.990 Or MS-DOS, maybe somebody would look for MS-DOS. 01:01:59.990 --> 01:02:07.470 Or what about this here, Arbeitsrecht, something where you have split 01:02:07.470 --> 01:02:09.230 the word into two parts. 01:02:09.950 --> 01:02:13.310 This should be one word, not two words. 01:02:13.870 --> 01:02:17.330 Or chapter 2.3, is this one word? 01:02:18.310 --> 01:02:21.790 Or is this... how would you analyze that? 01:02:21.930 --> 01:02:25.050 So you have to retrieve all the different words and you see it's not 01:02:25.050 --> 01:02:26.030 that simple really. 01:02:27.210 --> 01:02:34.830 And then you could say strings without digits. 01:02:35.270 --> 01:02:40.830 But sometimes you would like to look for words with digits, which are 01:02:40.830 --> 01:02:43.270 important words, like BS-2000. 01:02:43.510 --> 01:02:45.910 Who of you knows what BS-2000 is? 01:02:47.890 --> 01:02:50.930 None of you knows what BS-2000 is. 01:02:50.930 --> 01:02:57.130 BS-2000 is one of the most successful operating systems that has been 01:02:57.130 --> 01:03:05.210 sold by Siemens, our famous German information processing company. 01:03:06.550 --> 01:03:10.630 BS-2000, very important mainframe operating system. 01:03:11.190 --> 01:03:15.070 Certainly when it was called BS-2000, there was some time in the 80s, 01:03:15.170 --> 01:03:18.130 but it may well be that it's still running in some mainframe 01:03:18.130 --> 01:03:18.670 installations. 01:03:18.670 --> 01:03:20.990 Very important operating system. 01:03:21.230 --> 01:03:28.570 Somebody who is looking at commercial IT applications might still get 01:03:28.570 --> 01:03:32.850 into contact with BS-2000. 01:03:34.530 --> 01:03:40.710 It was similar to the IBM operating system at that time, just the 01:03:40.710 --> 01:03:45.470 Siemens version of that operating system, but with many interesting 01:03:45.470 --> 01:03:45.950 features. 01:03:45.950 --> 01:03:52.190 Now F-16, maybe some people look for F-16 or chemists might look for 01:03:52.190 --> 01:03:53.590 chemical formulas. 01:03:54.670 --> 01:03:57.630 And so you have to look also for things like that. 01:03:58.670 --> 01:04:03.910 I just want to indicate it's not that simple to decide how should you 01:04:03.910 --> 01:04:11.790 actually separate a string of symbols into words that are relevant for 01:04:11.790 --> 01:04:17.370 future queries that might have to be answered. 01:04:19.710 --> 01:04:25.570 Then the question is, would you differentiate or distinguish between 01:04:25.570 --> 01:04:26.930 capital and small letters? 01:04:28.130 --> 01:04:31.330 Usually you would say it doesn't matter whether it is a capital or 01:04:31.330 --> 01:04:34.490 small letter, but sometimes it might be important. 01:04:35.130 --> 01:04:41.410 So actually some search engines do distinguish between capital and 01:04:41.410 --> 01:04:42.010 small letters. 01:04:42.750 --> 01:04:43.470 Some don't. 01:04:47.450 --> 01:04:51.430 Well, what you do here is essentially, as I said, lexical analysis. 01:04:51.950 --> 01:05:00.750 Lexical analysis is a simple operation that corresponds to just doing 01:05:00.750 --> 01:05:02.950 something with a finite automaton. 01:05:03.390 --> 01:05:06.710 You can do that with standard tools and you would never write your own 01:05:06.710 --> 01:05:07.610 algorithm for that. 01:05:08.810 --> 01:05:12.250 There are simple tools for that around. 01:05:12.810 --> 01:05:17.310 In Java, you have the tokenizing function that would do the job. 01:05:18.310 --> 01:05:23.090 But you certainly have to look at the indicators, the characters that 01:05:23.090 --> 01:05:28.170 you take for separating the text into these words. 01:05:29.050 --> 01:05:33.530 Now, assume you have already detected your words and you would like to 01:05:33.530 --> 01:05:36.510 find out what words are relevant. 01:05:37.130 --> 01:05:40.590 I mentioned that already that we have something like a stop list, 01:05:40.850 --> 01:05:43.770 which contains all the irrelevant words. 01:05:44.670 --> 01:05:48.690 And this list is a finite set of words. 01:05:48.690 --> 01:05:53.510 You can certainly integrate that into a lexical analysis. 01:05:54.310 --> 01:05:58.030 And then you just would discard all those words. 01:05:58.450 --> 01:06:11.750 So this is just a simple idea how you could actually check for 01:06:11.750 --> 01:06:15.770 occurrences of these words in a document. 01:06:15.770 --> 01:06:21.570 So whenever you would see one of these words, you would get into a 01:06:21.570 --> 01:06:23.230 final state here in this automaton. 01:06:24.110 --> 01:06:26.670 So this is simply done. 01:06:28.170 --> 01:06:30.570 And so this is also a simple operation. 01:06:30.730 --> 01:06:33.730 You just have to check for these words and you are done. 01:06:36.310 --> 01:06:38.670 Next step is stemming. 01:06:39.090 --> 01:06:44.990 We would like to reduce our words to the essential parts in order to 01:06:44.990 --> 01:06:50.270 be able to give responses to queries that are more general. 01:06:52.230 --> 01:06:58.370 So you have a suffix of a word, like for example here the word ponies. 01:06:59.290 --> 01:07:02.550 The stem for that would be pony, the ES. 01:07:02.870 --> 01:07:05.130 This refers not only to English words. 01:07:06.230 --> 01:07:10.990 So here you would just replace IES with I. 01:07:10.990 --> 01:07:15.210 You would replace S with nothing. 01:07:15.510 --> 01:07:18.690 You would just chop off the S. 01:07:19.130 --> 01:07:22.450 If you have an ED at the end, you would just ignore that. 01:07:22.570 --> 01:07:25.330 If you have an ing at the end, you would ignore that. 01:07:25.790 --> 01:07:29.650 If you have an AT at the end, for example here. 01:07:32.110 --> 01:07:33.990 Now this is something which occurs... 01:07:35.410 --> 01:07:37.930 Here you would have, for example, a word like conflated. 01:07:38.470 --> 01:07:45.530 And you chopped off the ED and then you have again to add an E there. 01:07:46.350 --> 01:07:48.010 So conflate, that would be the stem. 01:07:48.490 --> 01:07:52.190 So you have all kinds of... I don't want to go through all these 01:07:52.190 --> 01:07:53.690 examples step by step. 01:07:54.290 --> 01:08:00.310 Just to show you that there are many different suffixes that have to 01:08:00.310 --> 01:08:02.710 be replaced in a reasonable way. 01:08:02.710 --> 01:08:05.210 This certainly is language dependent. 01:08:06.010 --> 01:08:15.150 And we have to see if it's just looking at a table and doing all these 01:08:15.150 --> 01:08:15.910 replacements. 01:08:16.050 --> 01:08:20.830 The advantages of this are that you have to store in your table fewer 01:08:20.830 --> 01:08:22.610 words in your index. 01:08:23.250 --> 01:08:28.550 Because you do not have to store the words with all their variants, 01:08:28.690 --> 01:08:30.410 but only the word stems. 01:08:30.410 --> 01:08:44.870 And another advantage is that the responses to queries will report 01:08:44.870 --> 01:08:45.530 more hits. 01:08:45.810 --> 01:08:48.770 Because you have a generalized search. 01:08:49.030 --> 01:08:55.530 If somebody looks for monitoring, then you would also get the hits 01:08:55.530 --> 01:08:57.470 where you only have a match with monitor. 01:08:57.470 --> 01:09:02.830 And now we have to build an efficient search structure. 01:09:03.350 --> 01:09:05.090 So we have to build an index. 01:09:06.990 --> 01:09:11.890 An index, you all know, is... well, you have a document, you have an 01:09:11.890 --> 01:09:12.370 index. 01:09:12.510 --> 01:09:14.470 And here you have listed all the words. 01:09:14.670 --> 01:09:19.110 And for every word here, you have a pointer pointing to the position 01:09:19.110 --> 01:09:23.450 at our document where this word occurs. 01:09:23.750 --> 01:09:26.050 Maybe at several locations. 01:09:27.050 --> 01:09:34.730 And so for every word of the document, this inverted file specified 01:09:34.730 --> 01:09:38.130 where within the document occurred. 01:09:39.150 --> 01:09:43.650 It might also specify its relevance, its weight. 01:09:45.350 --> 01:09:52.470 So it might specify how often it occurs, and other things maybe. 01:09:54.030 --> 01:09:56.930 Now for that, there are many different data structures. 01:09:57.150 --> 01:10:04.050 You could use a hash table for that, which is done in search engines. 01:10:05.050 --> 01:10:09.330 Search or hash tables are important parts of those inverted files. 01:10:10.550 --> 01:10:13.070 You could use a sorted list with random access. 01:10:15.310 --> 01:10:19.550 This might be reasonable, you would have fast access. 01:10:22.850 --> 01:10:25.870 But you would have to have a simple structure. 01:10:26.010 --> 01:10:27.490 You have logarithmic access time. 01:10:28.450 --> 01:10:30.890 You have sorted entries. 01:10:31.030 --> 01:10:35.070 That means with binary search, you always find the word you are 01:10:35.070 --> 01:10:35.770 looking for. 01:10:36.550 --> 01:10:41.470 And then you have certainly a simple structure for that. 01:10:41.790 --> 01:10:44.830 The problem is that you have rather expensive administration. 01:10:44.830 --> 01:10:52.110 In particular, if this index is changing very often, so if you have a 01:10:52.110 --> 01:10:58.090 very dynamic collection of documents with a frequently changing index, 01:10:58.630 --> 01:11:04.030 then this would lead to quite some overhead to maintain such a sorted 01:11:04.030 --> 01:11:04.430 list. 01:11:05.430 --> 01:11:19.470 Tree structures would be an alternative, because you have more 01:11:19.470 --> 01:11:23.790 efficient operations for maintaining such a tree, 01:11:26.890 --> 01:11:32.690 like searching in a tree, modifying a tree, inserting elements in a 01:11:32.690 --> 01:11:35.070 tree is all done in logarithmic time. 01:11:35.750 --> 01:11:38.430 And so this is better than in the sorted list, where you would have 01:11:38.430 --> 01:11:41.210 linear time for inserting an element. 01:11:42.670 --> 01:11:48.050 B-trees might be one thing that could be used, which B-trees are used 01:11:48.050 --> 01:11:52.150 in databases quite widely. 01:11:52.970 --> 01:12:03.830 So B-trees are balanced search trees, where we have just some trees 01:12:03.830 --> 01:12:07.590 where every node here is rather large and contains about the 01:12:07.590 --> 01:12:10.930 information of one memory page. 01:12:11.910 --> 01:12:17.370 And this is very important if you have large search structures on hard 01:12:17.370 --> 01:12:17.890 disks. 01:12:18.350 --> 01:12:19.810 Why is that important for that? 01:12:19.810 --> 01:12:27.350 If you have the information of one page in one node, that means if you 01:12:27.350 --> 01:12:32.970 access the information of one node, you just get the complete page. 01:12:34.230 --> 01:12:40.350 And if you would organize it in a different way, you might have too 01:12:40.350 --> 01:12:41.910 many disk accesses. 01:12:42.450 --> 01:12:48.230 And disk accesses, as you know, are very expensive compared to main 01:12:48.230 --> 01:12:48.970 memory accesses. 01:12:48.970 --> 01:12:54.670 And so you should always try to minimize the disk accesses. 01:12:55.430 --> 01:13:00.690 And that's why B-trees are very important, because they minimize disk 01:13:00.690 --> 01:13:01.350 accesses. 01:13:02.230 --> 01:13:05.830 And then you might have a tree structure which is called a trie. 01:13:06.830 --> 01:13:17.550 And like this tree here, it should be pronounced trie. 01:13:19.070 --> 01:13:21.870 It comes from retrieval. 01:13:22.090 --> 01:13:26.930 That's why it's spelled T-R-I-E. 01:13:30.030 --> 01:13:35.730 From retrieval, it's a tree structure that is useful for information 01:13:35.730 --> 01:13:36.450 retrieval. 01:13:37.790 --> 01:13:50.510 And so these trees in this way from retrieval are some efficient 01:13:50.510 --> 01:13:52.250 structures which we will look at. 01:13:52.770 --> 01:13:56.990 And I will present to you the so-called Patricia trees, and you will 01:13:56.990 --> 01:14:03.550 find out what these are maybe today, otherwise next week. 01:14:05.350 --> 01:14:09.490 Okay, let me briefly present to you what a B-tree is. 01:14:11.490 --> 01:14:20.010 B, by the way, refers not to balanced, but to a scientist, Udolf 01:14:20.010 --> 01:14:23.690 Bayer, I think was his name, at the Technical University of Munich. 01:14:25.030 --> 01:14:31.550 And it's a data structure supporting an efficient search for words or 01:14:31.550 --> 01:14:32.910 keys from an ordered set. 01:14:33.050 --> 01:14:34.710 Let me give you this example here. 01:14:35.270 --> 01:14:38.790 So what is a B-tree like? 01:14:39.070 --> 01:14:42.370 All the leaves have the same depth, as you can see here. 01:14:42.490 --> 01:14:44.030 All the leaves have the same depth. 01:14:44.110 --> 01:14:47.190 In this case here, we have depth 2 of this tree. 01:14:48.970 --> 01:14:55.370 Every inner node has at least M over 2 successors. 01:14:55.370 --> 01:15:02.690 So if we talk about a B-tree of degree M, we have at least M over 2 01:15:02.690 --> 01:15:04.550 successors for every inner node. 01:15:06.310 --> 01:15:12.530 So if M is the page size, that would mean we would have half the page 01:15:12.530 --> 01:15:16.670 size, many successors of one node. 01:15:16.730 --> 01:15:21.310 As you can see here, we have different, in this example, different 01:15:21.310 --> 01:15:22.850 numbers of successors. 01:15:22.850 --> 01:15:28.050 Here we have just two successors, in this example, this node here and 01:15:28.050 --> 01:15:32.250 that node, and the other nodes have three successors. 01:15:32.810 --> 01:15:38.110 The example here is for M equals 3, and so for M equals 3, if we say 01:15:38.110 --> 01:15:42.850 we have at least M over 2 successors, that means we have at least two 01:15:42.850 --> 01:15:43.650 successors. 01:15:44.070 --> 01:15:52.690 These symbols here, you know, these ceiling symbols indicating the 01:15:52.690 --> 01:15:55.570 next integer larger than M over 2. 01:15:57.330 --> 01:16:00.890 Now the root has at least two successors, in this case here it has 01:16:00.890 --> 01:16:07.390 three successors, and every node has at most M successors, at most 3, 01:16:07.930 --> 01:16:11.030 so in this example, at most 3. 01:16:11.830 --> 01:16:20.310 And in every node, like a node with K successors, such a node will 01:16:20.310 --> 01:16:22.690 contain K minus 1 keys. 01:16:22.990 --> 01:16:27.430 So here we have three successors, that means we have two keys in 01:16:27.430 --> 01:16:27.770 there. 01:16:28.410 --> 01:16:29.250 Now what is a key? 01:16:29.830 --> 01:16:35.250 Let me just briefly think of an interesting example here. 01:16:36.270 --> 01:16:51.070 Maybe I just write here, for example, B and maybe an E here, and some, 01:16:52.490 --> 01:16:57.650 for example, C in there, no, E, 01:17:00.720 --> 01:17:04.640 this should be F, 01:17:08.060 --> 01:17:18.960 and for example, this could be M, U, X, and this could be, for 01:17:18.960 --> 01:17:20.540 example, K. 01:17:21.420 --> 01:17:30.480 So these would be just some example of possible keys in such a B-tree, 01:17:31.300 --> 01:17:36.460 and this means if we would look for a certain value, we would go into 01:17:36.460 --> 01:17:43.400 this tree, for example, if we would look for some symbol L, we would 01:17:43.400 --> 01:17:50.500 look into the root node, we see that L is larger than F, smaller than 01:17:50.500 --> 01:17:56.580 M, so we would have to go into this node here, we see L is larger than 01:17:56.580 --> 01:17:59.400 K, and we would branch into this leaf. 01:18:01.400 --> 01:18:03.060 Okay, L is not in here. 01:18:03.780 --> 01:18:07.180 So we would see L is not in this B-tree. 01:18:07.760 --> 01:18:14.700 Or we would look for U, then we would just go in here and we would 01:18:14.700 --> 01:18:19.360 just see U is larger than M, so we would follow that branch, and we 01:18:19.360 --> 01:18:21.660 would see U is here in that node. 01:18:22.780 --> 01:18:27.960 So it's just the normal search tree structure, that you use the keys 01:18:27.960 --> 01:18:36.680 inside a node for branching to the different nodes below, but you have 01:18:36.680 --> 01:18:45.920 several keys in these nodes in order to allow for a tree where the 01:18:45.920 --> 01:18:52.100 path from the root to the leaves is always the same. 01:18:56.480 --> 01:19:03.600 Okay, if you search in such a tree, you will notice that that can be 01:19:03.600 --> 01:19:05.640 done in logarithmic time. 01:19:08.060 --> 01:19:13.960 You just have to go through these nodes, you have to follow the path 01:19:13.960 --> 01:19:16.520 from the root at most to the leaf. 01:19:16.860 --> 01:19:22.600 If you find the key inside one of the nodes, you don't have to go all 01:19:22.600 --> 01:19:23.720 the way to a leaf. 01:19:23.840 --> 01:19:27.500 Otherwise, if it's not in there, you get down to the leaf. 01:19:28.420 --> 01:19:35.060 And the length of this path is at most logarithmic in N, the number of 01:19:35.060 --> 01:19:39.120 keys, where the logarithm is taken to the basis of M. 01:19:40.340 --> 01:19:44.140 M is the degree of our B-tree. 01:19:45.000 --> 01:19:54.140 And as you can easily see, if you insert something in here, certainly 01:19:54.140 --> 01:20:01.120 if you would insert, for example, the value C into this search 01:20:01.120 --> 01:20:06.740 structure, if you would insert C, that would have to go somewhere in 01:20:06.740 --> 01:20:07.880 this node here. 01:20:08.120 --> 01:20:14.120 But this has already the maximum size, and in such a case, you would 01:20:14.120 --> 01:20:18.380 have to build some new structure. 01:20:18.640 --> 01:20:21.080 You would get C in here, which is too large. 01:20:21.180 --> 01:20:23.680 You would have to move the C up there. 01:20:24.320 --> 01:20:28.940 You would move the C to the level above. 01:20:29.540 --> 01:20:38.200 Now, C up there means that is too large, so you would have to move the 01:20:38.200 --> 01:20:41.540 F up there, and you would get a new structure, where you would have 01:20:41.540 --> 01:20:52.660 the F up there, then you would have the C there, the M there, and here 01:20:52.660 --> 01:20:59.800 you would have a node with the B, there you would have a node with the 01:20:59.800 --> 01:21:08.260 E, and below the M you would still have this U and X. 01:21:08.260 --> 01:21:15.040 And so you again would have a tree, where the length of the paths are 01:21:15.040 --> 01:21:20.080 all the same, but they all increase by one, because we entered one new 01:21:20.080 --> 01:21:20.840 symbol there. 01:21:21.320 --> 01:21:27.760 Now, it looks as if we would have to change many parts of such a tree, 01:21:27.980 --> 01:21:32.200 if we insert something, but we only have to modify something on the 01:21:32.200 --> 01:21:36.640 path from the root to the position where we insert some new key. 01:21:36.640 --> 01:21:44.580 And so the number of operations is again bound by logarithm in N, and 01:21:44.580 --> 01:21:48.600 for deletion you have the same, you never have more than logarithmic 01:21:48.600 --> 01:21:53.700 time for these operations, and in practice this M is about the memory 01:21:53.700 --> 01:22:00.940 page size, and this leads to quite an efficient structure for looking 01:22:00.940 --> 01:22:04.720 up elements in a large database. 01:22:08.100 --> 01:22:15.580 Okay, and if you have here just one page of memory in one node, then 01:22:15.580 --> 01:22:21.320 you know that if you retrieve a node from a hard disk, you get all the 01:22:21.320 --> 01:22:25.320 information that you actually have to look at. 01:22:26.880 --> 01:22:33.980 So this is an efficient structure for databases. 01:22:34.920 --> 01:22:47.640 Now, I have to explain to you what a try is, but I see it's 11.14, so 01:22:47.640 --> 01:22:50.620 I'll actually look up whether this is... 01:22:51.280 --> 01:22:56.840 I'm always not sure whether I should pronounce that try or tree. 01:22:57.620 --> 01:22:59.540 Maybe I should stick to tree. 01:23:00.280 --> 01:23:02.340 It's just written in a different way. 01:23:02.720 --> 01:23:05.680 So if you would not know that this comes from retrieval, you would 01:23:05.680 --> 01:23:09.660 pronounce it try, but we know that it comes from retrieval, so we 01:23:09.660 --> 01:23:10.380 pronounce it tree. 01:23:11.240 --> 01:23:18.860 Okay, and here what we would like to do here is to produce a data 01:23:18.860 --> 01:23:23.300 structure that is particularly suited for efficient retrieval of words 01:23:23.300 --> 01:23:25.060 by character-based comparisons. 01:23:26.200 --> 01:23:30.720 And initial example is to look for the elements of this set, which 01:23:30.720 --> 01:23:33.840 could be done by this search structure here. 01:23:34.380 --> 01:23:39.760 And we will go into this more deeply in our next lecture next week. 01:23:40.120 --> 01:23:41.020 Okay, that's it for today.