WEBVTT 00:00.000 --> 00:04.400 Okay, welcome back to the lecture or the course on algorithmic data 00:04.400 --> 00:05.020 notifications. 00:05.820 --> 00:08.400 Currently there is the course evaluation running. 00:08.560 --> 00:11.400 In other courses you might have been asked already to evaluate the 00:11.400 --> 00:11.700 course. 00:12.280 --> 00:17.620 In this course I would like to do that immediately before the bonus 00:17.620 --> 00:21.440 exam, because most of you will take part in the bonus exam, but most 00:21.440 --> 00:25.880 of you don't take part in the live lectures, and I would like to get 00:25.880 --> 00:27.000 feedback from all of you. 00:27.160 --> 00:33.060 And so I will just ask you just before the start of the bonus exam to 00:33.060 --> 00:34.220 briefly evaluate the course. 00:34.380 --> 00:37.780 Then it's also a bit more time that has passed in the course, so you 00:37.780 --> 00:41.020 have a broader basis for actually evaluating the course. 00:41.400 --> 00:44.640 Another point is that, speaking about the bonus exam, it will be on 00:44.640 --> 00:49.820 the 19th of January, as you know, and there should be the possibility 00:49.820 --> 00:52.560 now to register for the bonus exam. 00:52.940 --> 00:56.220 I will check that with Mark Miltin, because for the other course that 00:56.220 --> 01:00.840 I'm teaching, the registration period already started for the same 01:00.840 --> 01:01.120 day. 01:01.300 --> 01:06.120 So I guess that the registration will be open pretty soon, and at 01:06.120 --> 01:13.180 least we'll get information on the lecture area here in the student 01:13.180 --> 01:18.100 portal to inform you about the start of registration. 01:18.800 --> 01:21.400 Okay, so then another remark. 01:21.960 --> 01:27.300 Some time ago, I think it was three weeks ago already, I was asked, or 01:27.300 --> 01:32.520 I presented to you the IP version 6 addressing format, and I said, 01:32.640 --> 01:37.940 okay, for the lecture to embed the old IP version 4 addresses, the 01:37.940 --> 01:41.740 initial bits would be, like 80 initial bits, would be zero. 01:42.260 --> 01:46.820 But certainly there are, we have to talk about the 16 bits that are 01:46.820 --> 01:50.900 still missing, and these are 16 ones, which I did not have in there 01:50.900 --> 01:52.200 when I presented to you this slide. 01:52.620 --> 01:58.260 So it's 80 zeros, 16 ones, and then there is the IP version 4 address 01:58.260 --> 02:00.160 with 32 bits that are then still missing. 02:00.660 --> 02:05.360 Yeah, and so in this way, it is a simple embedding of the IP version 4 02:05.360 --> 02:05.760 format. 02:06.260 --> 02:13.980 That was something I had to add there, which somehow was missing on 02:13.980 --> 02:15.080 that slide before. 02:15.740 --> 02:21.540 Now let's go to the chapter that we are currently in. 02:21.880 --> 02:25.660 That's the searching for information chapter, and there I had several 02:25.660 --> 02:28.600 things that I presented to you already. 02:29.980 --> 02:34.240 These were, there are no annotations on these, because this was 02:34.240 --> 02:40.000 presented to you as a recorded lecture, and then last time we looked 02:40.000 --> 02:43.340 at the pattern matching algorithms, which are not that difficult 02:43.340 --> 02:43.800 actually. 02:44.380 --> 02:47.600 Somehow I had a few problems to actually present to you the examples, 02:47.940 --> 02:49.620 but things like that happen sometime. 02:50.760 --> 02:58.480 So we had looked at the algorithm for, this is funny, the algorithm 02:58.480 --> 03:02.980 for Knuth-Morris-Pratt, and you remember that when I presented this 03:02.980 --> 03:06.400 slide, let me just do it again, just to check what happened. 03:06.640 --> 03:09.680 So on this slide, as you see, everything is aligned correctly 03:09.680 --> 03:13.960 underneath the appropriate positions, and I would have done that 03:13.960 --> 03:19.740 smoothly in explaining it, but somehow I had a problem when I did 03:19.740 --> 03:20.120 that. 03:20.480 --> 03:24.640 So let's just see what happens today. 03:24.780 --> 03:25.340 Everything is okay. 03:26.400 --> 03:27.680 This, I didn't change anything. 03:28.640 --> 03:30.400 Yeah, so this is really funny. 03:30.600 --> 03:37.180 Somehow I was, something was working against me last time. 03:37.680 --> 03:39.240 So now it's completely correct. 03:39.460 --> 03:43.680 I didn't do anything to that, so somehow this was modified when I 03:43.680 --> 03:46.540 presented the lecture. 03:46.760 --> 03:52.020 Okay, and then after that we looked at how we compute the next 03:52.020 --> 03:55.980 function, I explained to you how that works, I gave you this example, 03:56.640 --> 04:00.460 with the pattern abracadabra, which is a very nice pattern, you will 04:00.460 --> 04:04.180 see it again just in a moment, and then I showed you the Boyer-Moore 04:04.180 --> 04:08.600 algorithm, where different from what we do in Knuth-Morris-Pratt, we 04:08.600 --> 04:12.720 just start from the rightmost symbol of the pattern and then work 04:12.720 --> 04:19.080 backwards to the left, and if we have mismatches very early, we are 04:19.080 --> 04:22.460 quite often able to really shift the pattern by quite a large 04:22.460 --> 04:27.040 distance, and so we get an expected performance that is sub-linear in 04:27.040 --> 04:30.420 the size of the document, which certainly is very nice. 04:31.100 --> 04:34.900 And you remember that we had two heuristics there that we used, one 04:34.900 --> 04:37.380 was the occurrence heuristic, where we look for the occurrence of 04:37.380 --> 04:42.080 symbols in the pattern, and use that information to calculate a shift 04:42.080 --> 04:45.260 distance, and the other was an occurrence heuristic, here on the next 04:45.260 --> 04:49.520 slide, no, occurrence heuristic, the match heuristic, which looks at 04:49.520 --> 04:53.600 the reoccurrence of a suffix that we have already looked at, and that 04:53.600 --> 04:58.440 appeared in the document, whether that suffix, indicated in red here, 04:58.700 --> 05:03.500 reappears at some position to the left, and then this determines 05:03.500 --> 05:09.220 another possibility to determine the, or this resides in another shift 05:09.220 --> 05:10.400 distance calculation. 05:10.980 --> 05:15.900 And certainly one would combine those two heuristics, and then get a 05:15.900 --> 05:21.120 combined heuristic, which actually always uses the maximum shift 05:21.120 --> 05:25.540 distance that we get from both heuristics. 05:26.580 --> 05:35.820 And so, I also showed you, or told you something about examples, here 05:35.820 --> 05:41.880 we had another example for Boyamur, and by the way, here on that 05:41.880 --> 05:47.120 slide, I had a, this was explained in a way that maybe was also not 05:47.120 --> 05:51.840 that instructive, and although, when I listened to that again, I think 05:51.840 --> 05:52.520 it was okay. 05:53.020 --> 05:58.680 And so, I decided to just present to you another example, this was a 05:58.680 --> 06:01.980 pattern example, now you get another pattern, where I would like to 06:01.980 --> 06:07.140 just briefly reiterate what we did there with respect to that 06:07.140 --> 06:12.940 heuristic, because Mark Murchin told me that in recent years, students 06:12.940 --> 06:16.960 always have problems in really finding out what that heuristic, in 06:16.960 --> 06:18.920 particular the match heuristic, really is about. 06:19.580 --> 06:27.800 And so, let's briefly look at that heuristic again. 06:28.100 --> 06:33.880 The match heuristic that we have for the Boyamur algorithm. 06:34.140 --> 06:38.560 Now the match heuristic was about, no, the occurrence heuristic, first 06:38.560 --> 06:38.880 of all. 06:38.940 --> 06:42.920 The occurrence heuristic was defined using this formula. 06:43.060 --> 06:50.520 We compute, first of all, the, we compute, oops, this is the wrong 06:50.520 --> 06:54.880 color, nobody chose that color, let's take red. 06:55.280 --> 07:01.920 Okay, so we first have to calculate the distance at which the symbols 07:01.920 --> 07:05.960 occur in the pattern, counting from the right end. 07:06.600 --> 07:13.420 Now, if we look at A, our pattern is abracadabra, yeah, the A occurs 07:13.420 --> 07:16.960 several times, but the rightmost occurrence is the last position, so 07:16.960 --> 07:18.820 the distance from the last position is zero. 07:19.700 --> 07:24.800 The B is two from the right end, the D four positions, the K six 07:24.800 --> 07:30.040 positions, the R one position, and every other symbol is 11 positions 07:30.040 --> 07:31.420 away from, because it doesn't occur. 07:32.320 --> 07:39.700 Yeah, so that's the distance of those symbols from the right end of 07:39.700 --> 07:41.900 the pattern. 07:42.400 --> 07:46.480 And then we have to calculate our shift distance depending on the 07:46.480 --> 07:51.960 current position that we actually are in the pattern, and have to look 07:51.960 --> 07:57.200 at the way we actually calculate, then, the shift distance. 07:57.280 --> 08:01.960 And you remember that we had to distinguish two situations if this 08:01.960 --> 08:06.560 here, like this is our pattern, and now if we are at some position, 08:08.560 --> 08:12.940 and we are looking for, like we will see that in a moment, so if we 08:12.940 --> 08:14.520 are, for example, at position one. 08:14.700 --> 08:16.160 Position one is this here. 08:17.060 --> 08:18.200 Yeah, that's position one. 08:18.940 --> 08:23.880 Now at position one, we have an A, so we will never calculate the 08:23.880 --> 08:27.420 shift distance for that position and symbol A, because it's not a 08:27.420 --> 08:27.900 mismatch. 08:28.740 --> 08:33.140 Yeah, it cannot be a mismatch, so we're only considering symbols which 08:33.140 --> 08:35.040 are different from the current symbol in the pattern. 08:35.560 --> 08:36.880 So let's look at B. 08:37.240 --> 08:42.820 If we are at position one and we notice a B, then we are at this 08:42.820 --> 08:47.340 position here, and B is two from the right end. 08:47.440 --> 08:52.760 Now M minus J, here it says the shift distance is computed in two 08:52.760 --> 08:57.660 different ways, depending on whether M minus J is greater or equal to 08:57.660 --> 09:03.680 that distance delta of the current pattern, or whether it is less than 09:03.680 --> 09:04.480 that delta. 09:05.380 --> 09:08.480 Now what does it mean, M minus J is greater or equal? 09:09.080 --> 09:18.120 M minus J in this case is 10, so that is definitely larger than delta 09:18.120 --> 09:18.580 of C. 09:19.300 --> 09:24.280 Yeah, because we are here, we are at the left of the position of the 09:24.280 --> 09:26.140 first occurrence of that symbol. 09:26.960 --> 09:32.400 And so why do we, how do we move the pattern in that case? 09:32.480 --> 09:34.480 We move it by delta C plus one. 09:35.200 --> 09:36.280 Why do we do that? 09:36.800 --> 09:41.400 We are having a B at that position in the document, and we notice 09:41.400 --> 09:43.160 everything else was correct. 09:45.340 --> 09:52.000 And now, well, we just use now the symbol B for recalculating our, or 09:52.000 --> 09:56.160 the position that we need in, or the shift position. 09:56.660 --> 10:01.840 The B occurs here in the pattern, and the first point where this 10:01.840 --> 10:06.500 symbol can reoccur again in the document is the position right next to 10:06.500 --> 10:10.760 that, because that's true for every rightmost occurrence of a symbol, 10:11.260 --> 10:15.360 that we will just move the pattern to the right such that the symbol 10:15.360 --> 10:19.520 under consideration will be compared to the symbol in the document 10:19.520 --> 10:23.700 that is right next to the right end of that pattern. 10:24.420 --> 10:24.500 Yeah? 10:25.260 --> 10:26.300 Nothing else makes sense. 10:26.680 --> 10:32.500 And so we have three there for the B, for the D, it's again like the M 10:32.500 --> 10:37.300 minus J is 10, so in this case these distances are all smaller than M 10:37.300 --> 10:42.680 minus J, and so here we just compute delta C plus one in every case. 10:43.660 --> 10:48.560 And now we have a symbol 11, some other symbol, and for that some 10:48.560 --> 10:50.800 other symbol, we know it does not occur. 10:52.180 --> 10:57.500 This is this case, and here it is delta of C, which is 11, minus M 10:57.500 --> 11:00.880 minus J, which is 10, so we have to shift it by one position. 11:01.600 --> 11:02.760 Why is that the case? 11:03.040 --> 11:11.280 If that symbol does not occur here, so we are at this position, 11:11.940 --> 11:19.360 there's some other symbol, and so in this case we 11:22.860 --> 11:27.520 don't know, well let me, 11:30.740 --> 11:39.680 ridiculous, M minus J is 10, delta C is 11, so if this is a symbol 11:39.680 --> 11:52.360 that is not occurring in that pattern, we have it here, yes, we have 11:52.360 --> 11:52.860 it there. 12:00.080 --> 12:00.940 What do we know? 12:01.040 --> 12:06.140 We don't know anything, like definitely we know it's a pattern, a 12:06.140 --> 12:10.360 symbol which is not occurring at this position, but we don't know 12:10.360 --> 12:11.040 anything else. 12:11.900 --> 12:15.360 Yeah, and so we just have to move it by one position to the right, 12:15.540 --> 12:20.020 because this is just a symbol at this position 1, we don't know 12:20.020 --> 12:25.140 anything about that symbol there, so we just have to move it by one 12:25.140 --> 12:27.020 position. 12:27.140 --> 12:30.520 We know that this symbol does not occur in the pattern, so certainly 12:30.520 --> 12:35.760 it might occur to the, or we only have to, or have the information 12:35.760 --> 12:39.360 that we have to shift the pattern by one position, because then this 12:39.360 --> 12:46.580 is, this might be another occurrence, but we know for other reasons 12:46.580 --> 12:52.080 that it won't be probably an occurrence of that pattern, but we will 12:52.080 --> 12:54.400 look at those other situations later. 12:55.100 --> 13:02.400 Okay, so this is everything we know if we are to the, if our distance 13:02.400 --> 13:07.200 is larger than this M minus J, that means we are to the, essentially 13:07.200 --> 13:09.140 to the left of the current position of the pattern. 13:09.720 --> 13:18.080 Let's look now for position 2, here M minus J is 9, and so this is 13:18.080 --> 13:23.580 exactly the same as before, only at position 2 we have a B, so here we 13:23.580 --> 13:27.400 don't do anything, and here we have to shift by two positions. 13:27.600 --> 13:30.420 If it's any other symbol, we only know that we have to shift the 13:30.420 --> 13:31.400 pattern by two positions. 13:32.140 --> 13:36.880 And then this all stays the same, with the only difference that the 13:36.880 --> 13:41.980 position where we have a match with the, like the same symbol as in 13:41.980 --> 13:44.160 the pattern, are at different positions here. 13:44.820 --> 13:49.780 And then the first thing that is different is at, like here, for the 13:49.780 --> 13:53.960 other symbol, the distance is increased by one position every time, 13:54.420 --> 13:56.920 and then we have a difference here. 13:57.920 --> 14:02.820 So here, no, must be a bit earlier, no, it's correct. 14:04.260 --> 14:16.360 So here we have position 7, M minus J is, at this time it is 4, and so 14:16.360 --> 14:19.620 this stays the same, here we don't do anything, here we have a 14:19.620 --> 14:24.940 difference, here also we had a difference, here, at 6, we also had a 14:24.940 --> 14:33.900 difference at 6, M minus J is 5, there we have 6, and so we have to 14:33.900 --> 14:36.920 move by 6 minus 5, which is 1. 14:37.480 --> 14:39.080 That's why we have the 1 in there. 14:40.040 --> 14:40.140 Yeah? 14:41.240 --> 14:50.200 And the next line here, we have small distances here, M minus J is 4, 14:50.360 --> 14:53.740 so we are at this position where we have something different, here we 14:53.740 --> 14:58.480 have to increase again that, like delta of C, which is 6, minus 4 in 14:58.480 --> 14:59.360 this case, which is 2. 15:00.280 --> 15:05.580 And then this just goes on in this way, and so you see that 15:05.580 --> 15:14.640 increasingly here, because we move to positions that are more to this 15:14.640 --> 15:21.180 end here, to the right end, those occurrences of symbols to the left 15:21.180 --> 15:27.780 of that position will just lead to a shift distance which is 15:27.780 --> 15:34.740 calculated like this, we just subtract M minus J from the delta of C. 15:35.120 --> 15:38.940 Let's just move it a bit to the right, as you see in this table. 15:39.760 --> 15:39.780 Yeah? 15:39.880 --> 15:44.100 So the pattern is a bit more complex, and you see how the occurrence 15:44.100 --> 15:46.400 heuristic actually works for this pattern. 15:47.820 --> 15:55.660 Okay, so we have a few large shift distances, like 7 for the K in some 15:55.660 --> 16:00.520 cases, we have a few large shift distances here, if early in the 16:00.520 --> 16:04.980 pattern we see a mismatch because we have a symbol which is not in the 16:04.980 --> 16:09.160 pattern, definitely we can shift over a very large distance. 16:09.920 --> 16:15.560 Yeah, this is intuitively obvious immediately. 16:16.700 --> 16:22.040 And so the other thing was the match heuristic, and now if we look at 16:22.040 --> 16:26.220 our work abracadabra, and look at the match heuristic, we have this a 16:26.220 --> 16:30.400 bit complicated formula in here, this definition of that shift 16:30.400 --> 16:31.060 distance. 16:31.660 --> 16:37.320 And the idea was that we wanted to find the smallest s, like the 16:37.320 --> 16:43.400 rightmost reoccurrence of that suffix, such that the symbol to the 16:43.400 --> 16:48.160 left of that sequence of symbols is different. 16:49.220 --> 16:54.460 Yeah, so the red part reoccurs, and those two symbols at positions J 16:54.460 --> 16:55.900 and J minus s are different. 16:56.060 --> 16:59.780 That was the definition, because then we know if we shift it by 16:59.780 --> 17:05.800 distance s, then this part will be exactly matching with the same part 17:05.800 --> 17:11.340 here in the document, and so this will be the next potential match, 17:11.400 --> 17:14.020 and we have to take the rightmost position, because otherwise we would 17:14.020 --> 17:15.180 shift the pattern too far. 17:15.920 --> 17:17.520 Now how does this work? 17:17.600 --> 17:23.400 If we look at position, at that final position here, if we have a 17:23.400 --> 17:29.700 mismatch there, yeah, that's our position J, the rightmost position. 17:30.160 --> 17:35.000 What is the shift distance with respect to that formula that we have 17:35.000 --> 17:35.260 here? 17:36.040 --> 17:41.840 There, this suffix is empty, and so we just look for the next symbol 17:41.840 --> 17:42.600 which is different. 17:43.280 --> 17:47.540 The next symbol which is different is the R, and so we have to shift 17:47.540 --> 17:48.360 by one position. 17:48.760 --> 17:56.000 That's the minimum shift distance such that we have the same suffix 17:56.000 --> 18:00.540 but a different symbol at that position to the left of that suffix, so 18:00.540 --> 18:02.920 this is exactly a distance one. 18:03.600 --> 18:12.180 If we are at R and the A matched already, then we have, in order to 18:12.180 --> 18:19.160 find the next reasonable position, we have to look for, well, the next 18:19.160 --> 18:24.440 occurrence of an A, which is here, there's the next occurrence of an 18:24.440 --> 18:28.000 A, and the symbol to the left of that is different. 18:29.380 --> 18:37.140 This is a D, and so a D is at position seven, so the shift distance in 18:37.140 --> 18:41.440 this case is three, ten minus seven, three, that's why we have the 18:41.440 --> 18:41.920 three there. 18:42.800 --> 18:44.020 Now we go to the next position. 18:44.540 --> 18:49.360 Now we have already dealt with these things here, and we have to go to 18:49.360 --> 18:50.980 look at this here. 18:51.380 --> 18:52.660 Now what happens in this case? 18:53.600 --> 18:57.940 We have to look for the suffix R A, where does R A reoccur? 18:58.140 --> 18:59.560 R A reoccurs here, 19:02.840 --> 19:05.700 but the symbol to the left of that is the same. 19:08.260 --> 19:09.720 Yeah, so this doesn't help. 19:10.700 --> 19:12.860 So what is the next position that we have to look at? 19:13.760 --> 19:17.960 We have to look for the smallest S, so this was not sufficient, we 19:17.960 --> 19:21.220 have to, it's too small, we have to go to a larger distance. 19:22.920 --> 19:25.240 And now, there's no other R A here. 19:26.140 --> 19:34.680 But there is an A, and A is a suffix of that suffix. 19:35.760 --> 19:40.600 And this is exactly the case that we have here, if the shift like S 19:40.600 --> 19:43.200 certainly may be larger than J. 19:44.960 --> 19:49.620 If S is larger than J, the shift distance is larger than J, this 19:49.620 --> 19:52.980 actually is to the left of the pattern somewhere. 19:54.640 --> 20:03.240 And that means that we have to look for, well, the reoccurring, like, 20:03.780 --> 20:07.740 a suffix which is reoccurring as a prefix of the pattern. 20:08.580 --> 20:13.740 In this case, this is, like, the suffix is here, the R A, the current 20:13.740 --> 20:19.240 suffix, we have to look for the suffix of that suffix, the largest 20:19.240 --> 20:26.400 suffix of that suffix, which is reoccurring here, as a prefix of the 20:26.400 --> 20:26.620 pattern. 20:27.100 --> 20:31.540 This is stated, like, this is the case that S is greater or equal to 20:31.540 --> 20:42.300 J, and then we have here, S is, here, WK minus S is equal to WK, as 20:42.300 --> 20:46.340 long as S is smaller or equal to K. 20:47.960 --> 20:53.280 Okay, so this is exactly treating that K, so it's all in that formula, 20:54.400 --> 21:02.860 and that means we have to, like, this is the reoccurring prefix, and 21:02.860 --> 21:07.320 so we just subtract 11 and 1, which is the shift distance of K. 21:08.700 --> 21:14.920 Now, the next position, the A, if we are here, this was, we did also 21:14.920 --> 21:17.940 correctly, let's look at the next situation. 21:18.840 --> 21:21.840 We have this A here now. 21:23.360 --> 21:33.940 We have a B R A to the right of that, B R A is a reoccurring here, and 21:33.940 --> 21:41.400 again, it is having the same symbol to the left, the A, so we have the 21:41.400 --> 21:42.500 same situation again. 21:43.500 --> 21:50.080 The largest suffix of that sequence here, of that suffix, which 21:50.080 --> 21:54.080 reoccurs as a prefix, is just the A, so again, we have a 10 there. 21:55.500 --> 21:57.000 Let's look at the next situation. 21:58.740 --> 22:02.440 We look for, we are now at this D. 22:04.480 --> 22:13.920 In this case, we have ABRA as the suffix, we have ABRA here as the 22:13.920 --> 22:19.060 prefix, and there's no, like, this symbol might be different, but this 22:19.060 --> 22:24.200 is exactly, again, the situation that I just described, and here, the 22:24.200 --> 22:28.080 complete suffix, which is there, reoccurs as a prefix. 22:29.000 --> 22:32.660 So now, we have to subtract from 22:35.960 --> 22:42.140 position, the start of that suffix, we have to subtract from that the 22:42.140 --> 22:46.420 start of that prefix, which is just 7 in this case. 22:47.980 --> 22:53.740 And now, we look at the next, from this position on, if we look at 22:53.740 --> 22:58.320 other patterns here, like that, that is the current position, we have 22:58.320 --> 23:03.560 a mismatch there, we look at the suffix, DABRA does not reoccur, but 23:03.560 --> 23:09.200 the largest suffix of that which reoccurs is ABRA, and again, we have 23:09.200 --> 23:11.860 the 7, and this stays the same for the remaining positions. 23:12.700 --> 23:18.020 And so, for the remaining positions, we always get the 7 as our shift 23:18.020 --> 23:18.340 distance. 23:19.040 --> 23:24.680 I think this example, this pattern, very clearly shows the different 23:24.680 --> 23:31.600 cases that we run into if we determine that those values, those shift 23:31.600 --> 23:34.060 distance with respect to the match heuristic. 23:34.720 --> 23:38.240 And now, we take, for every position, we take always the maximum of 23:38.240 --> 23:45.760 both, and you see that in many cases, we will have larger, or the 23:45.760 --> 23:52.320 largest shift distances here for the match heuristic, and if we are 23:52.320 --> 23:59.680 far to the right end, here we also have large shift distances here, 24:00.620 --> 24:08.700 and so, we see that in this way we can get quite large values for the 24:08.700 --> 24:16.300 shift distance in these mismatching situations, and so get the 24:16.300 --> 24:22.340 sublinear behavior that we had analyzed last time, or had postulated 24:22.340 --> 24:22.960 last time. 24:23.680 --> 24:29.080 Okay, this was another example which I showed to you last week, don't 24:29.080 --> 24:33.240 have to go into that again, but this just indicated that we have this 24:33.240 --> 24:35.880 reduction in the number of comparisons that we have. 24:36.320 --> 24:40.060 I don't want to give another example, I think that's now I showed you 24:40.060 --> 24:41.560 a sufficient number of things. 24:41.760 --> 24:48.420 I also, with respect to those algorithms, I also showed you these good 24:48.420 --> 24:56.920 and bad examples, like, which are behaving positively, like having 24:56.920 --> 25:01.780 little time, or the worst case certainly can occur here for Boyl Moore 25:01.780 --> 25:06.860 that we have actually n times m, but that's a very extreme pattern 25:06.860 --> 25:12.600 which really is not occurring in reality normally. 25:13.300 --> 25:17.040 Yeah, so if you look at typical patterns, then you will get you will 25:17.040 --> 25:19.680 get sublinear behavior. 25:20.380 --> 25:27.820 Okay, so this was what we looked at last time, and now we finally come 25:27.820 --> 25:35.880 back to the new stuff, but I think it was important to show you that 25:35.880 --> 25:41.280 example again because it explained, I think, this approach of Boyl 25:41.280 --> 25:43.980 Moore much better than the examples I had before. 25:44.860 --> 25:48.280 Okay, so let's look now at a different approach. 25:48.700 --> 25:55.420 What we did with Mooth-Morris-Pratt and Boyl Moore was to take a 25:55.420 --> 26:01.020 pattern and compute something, compute those heuristics, and then get 26:01.020 --> 26:04.620 any document and make a full-text search and look for the occurrence 26:04.620 --> 26:06.720 of those patterns and documents. 26:07.580 --> 26:11.100 But although it is sublinear time, still it will take some time to 26:11.100 --> 26:11.940 actually do that. 26:12.580 --> 26:16.700 And so what you could also do is pre-compute information about the 26:16.700 --> 26:20.440 documents if you have all the documents beforehand, which is the case 26:20.440 --> 26:23.280 in the World Wide Web where we have all the documents, at least some 26:23.280 --> 26:26.420 information about those documents, and then we can prepare for 26:26.420 --> 26:27.220 possible queries. 26:28.420 --> 26:34.080 And so now we have to find out what are actually potential ways of 26:34.080 --> 26:37.620 preparing for a query and making that query very efficient. 26:38.540 --> 26:41.660 So the first thing is, normally we will look for words. 26:43.440 --> 26:48.000 Yes, maybe we will also look for sub-words, but normally we just look 26:48.000 --> 26:50.760 for words, at least for the start of words. 26:51.880 --> 26:56.360 And so if we would like to look for the occurrence of words, we need 26:56.360 --> 26:58.180 some notion of what a word actually is. 26:58.760 --> 27:01.120 And this is not immediately clear. 27:01.200 --> 27:07.720 Certainly if you look at this at this phrase here, analyze the 27:07.720 --> 27:11.380 document to allow for an efficient search for arbitrary patterns, you 27:11.380 --> 27:14.180 definitely immediately see all the words, because you can distinguish 27:14.180 --> 27:18.600 them or can separate them by looking at the so-called special 27:18.600 --> 27:21.300 characters, which in this case would be just a blank. 27:22.400 --> 27:26.200 Yes, we have a blank in between here, and so this is clearly 27:26.200 --> 27:30.040 separating the words, the sequence of words, or the sequence of 27:30.040 --> 27:31.740 symbols into words. 27:31.860 --> 27:35.060 We can immediately do that, and you know that in Java you have a 27:35.060 --> 27:39.040 tokenize function which we can use, we can specify the symbols that we 27:39.040 --> 27:42.600 use for separators and then easily get the separation into words. 27:43.760 --> 27:46.880 But it's not that easy really. 27:48.300 --> 27:53.500 So you could say it is a string without special characters, which 27:53.500 --> 27:58.600 might be a colon, a blank, or a hyphen. 28:00.480 --> 28:02.440 So blank immediately is clear. 28:03.420 --> 28:06.200 But if you look at this, for example, Jean-Claude, there is a hyphen 28:06.200 --> 28:06.640 in between. 28:07.520 --> 28:09.440 Is that one word or is it two words? 28:10.880 --> 28:13.900 Or state of the art, is that one word? 28:15.140 --> 28:20.440 MS-DOS, whatever that is, just also a hyphen in between. 28:21.140 --> 28:28.680 Something like this, Arbeitsrecht, that's just by separating a word 28:28.680 --> 28:33.540 over lines, like breaking it up into two parts, you have a hyphen in 28:33.540 --> 28:33.820 there. 28:35.000 --> 28:37.980 Should be discarded, should be treated as one word, but you have to 28:37.980 --> 28:40.280 distinguish, or you have to detect that. 28:41.220 --> 28:46.900 And then you have something like chapter 2.3, definitely separated by 28:46.900 --> 28:49.100 a blank, and you have a colon in there. 28:51.000 --> 28:53.400 So what are we doing with that? 28:55.140 --> 29:01.120 So it looks a little bit different, a little bit difficult to actually 29:01.120 --> 29:03.940 find out what the appropriate words are. 29:04.220 --> 29:08.320 Just wanted to mention that this is not really clear. 29:08.480 --> 29:11.080 Also, for example, strings without digits. 29:11.980 --> 29:15.920 But if you have something like BS-2000, who of you knows what BS-2000 29:15.920 --> 29:16.260 is? 29:18.840 --> 29:22.540 One of the most famous products that was ever developed in German 29:22.540 --> 29:27.320 history of computer science, the operating system designed by Siemens 29:27.320 --> 29:31.560 for the Siemens computers, BS-2000, a very innovative operating 29:31.560 --> 29:38.600 system, which was very innovative, certainly designed sometime in 1970 29:38.600 --> 29:39.320 or 80. 29:39.860 --> 29:42.860 And it really lasted for a long, long, long time because it was the 29:42.860 --> 29:46.140 basic operating system in all the commercial computers sold by 29:46.140 --> 29:46.400 Siemens. 29:46.900 --> 29:53.700 So it was very similar to the IBM operating system for the 360 29:53.700 --> 29:58.380 machines, very similar to that, but it was one of the major success 29:58.380 --> 30:03.500 stories of the Siemens sales of computers. 30:04.120 --> 30:07.680 Okay, you know what an F-16 is, so these are words. 30:08.520 --> 30:15.560 And also a chemical formula, H2O, would also be some word. 30:16.040 --> 30:19.360 So you see, it's hard to actually do that. 30:19.420 --> 30:22.220 Just wanted to show you the problems. 30:22.360 --> 30:26.480 Then again, what do we do with capital or small letters? 30:26.800 --> 30:32.880 If you would like to find out all the words in a document, do we 30:32.880 --> 30:38.140 actually distinguish whether a word is starting with a capital letter 30:38.140 --> 30:38.960 or a small letter? 30:39.340 --> 30:40.120 Normally not. 30:41.400 --> 30:48.300 So we would just treat them the same, but these are different symbols. 30:49.140 --> 30:55.640 So we have to detect that, that they are at a fixed distance, just the 30:55.640 --> 30:57.380 distance between small and capital letters. 30:58.560 --> 31:02.000 Okay, so these are things you have to consider. 31:02.640 --> 31:08.860 And if you do all that, you can actually tokenize your documents and 31:08.860 --> 31:16.840 find out all the words that are occurring in such a document. 31:17.980 --> 31:22.320 And what we do here essentially is some kind of lexical analysis. 31:22.520 --> 31:24.420 You can do that with a final state machine. 31:25.380 --> 31:28.600 Now that's not that difficult. 31:28.860 --> 31:33.960 You can do that in a rather simple way, but rather simple means we 31:33.960 --> 31:36.540 have to consider all these problems that are indicated here. 31:37.880 --> 31:44.260 Okay, and now the second problem is that sometimes we have words which 31:44.260 --> 31:45.400 are not really relevant. 31:45.880 --> 31:49.400 You only want to extract the information that you need for later on 31:49.400 --> 31:50.460 answering queries. 31:50.860 --> 31:53.900 Who would look for the word are? 31:54.340 --> 31:55.020 Nobody. 31:56.140 --> 31:58.500 You can immediately discard that. 31:59.260 --> 32:01.280 Would anybody look for which? 32:01.760 --> 32:02.460 Don't know. 32:04.020 --> 32:06.620 Yeah, maybe you have to detect that. 32:07.660 --> 32:12.560 Or would anybody look for on or off or eh? 32:12.840 --> 32:13.740 Definitely not. 32:14.700 --> 32:19.980 So there are certain words which have to be considered as potential 32:19.980 --> 32:22.680 words or terms occurring in a query. 32:23.600 --> 32:28.800 You have to distinguish them from those which are definitely not 32:28.800 --> 32:29.160 occurring. 32:30.340 --> 32:37.140 And so we call them stop words or words that are just neglected. 32:38.200 --> 32:42.500 So you can just, for example, if you say these words here are so 32:42.500 --> 32:46.660 -called stop words which we just delete from the sequence or from the 32:46.660 --> 32:48.140 set of words that we actually get. 32:48.560 --> 32:51.700 You can easily do that while you do lexical analysis. 32:52.200 --> 32:57.180 This is just a toy example how you could actually build an automaton 32:57.180 --> 33:02.560 which would recognize exactly those stop words. 33:02.740 --> 33:09.480 And then at those points here where we have final states, we have 33:09.480 --> 33:13.260 always detected some stop words and could discard those words. 33:13.640 --> 33:17.940 A simple way just to indicate this is just simple stuff can be done in 33:17.940 --> 33:20.260 a linear time scanning through a document. 33:20.760 --> 33:23.080 You can immediately find out all these things. 33:24.340 --> 33:29.240 Certainly in some way you have to transform such a graphical structure 33:29.240 --> 33:33.300 of a automaton into a code in Java, but this can be done in a simple 33:33.300 --> 33:33.600 way. 33:33.740 --> 33:35.620 There are ways of actually doing that. 33:35.620 --> 33:39.760 Lexical analysis is a standard operation, and I don't want to spend 33:39.760 --> 33:40.800 that much time on that. 33:41.260 --> 33:44.160 I just had to mention we have to delete all the stop words. 33:44.760 --> 33:52.760 Okay, then another point is that the information may be too specific 33:52.760 --> 33:53.460 that we get. 33:55.100 --> 34:00.900 For example, if we look for the word example, wouldn't you also like 34:00.900 --> 34:05.780 to get a document where you have examples with the S in the end? 34:08.100 --> 34:15.980 So what we do is we just modify the words and reduce them to their 34:15.980 --> 34:16.320 stems. 34:17.760 --> 34:19.640 So what are the stems of a word? 34:19.760 --> 34:25.620 If we have something like ponies, we would reduce it to pony. 34:26.460 --> 34:29.780 That's the stem of the word ponies. 34:30.860 --> 34:34.000 Or if we have, like this certainly is different between different 34:34.000 --> 34:38.320 languages, the word stems and the endings that we can call suffixes 34:39.840 --> 34:43.220 that we can actually delete are different. 34:44.000 --> 34:49.300 So an S in the end can definitely, the plural S can be deleted. 34:50.300 --> 34:56.100 The E D in the end, like in here plastered, can be reduced to plaster. 34:57.460 --> 34:58.600 We can reduce that. 34:59.540 --> 35:02.700 And then there are all kinds of other things, like the I N G in the 35:02.700 --> 35:03.020 end. 35:03.900 --> 35:06.420 Motor ring can be reduced to motor. 35:07.080 --> 35:15.620 Or the eight can be replaced in this case with A T E. 35:16.320 --> 35:23.720 You see sometimes, as here, if you use the first rule for the word 35:23.720 --> 35:26.940 conflated, you would cut out E D. 35:27.840 --> 35:31.240 But the real stem in this case is conflate. 35:33.020 --> 35:35.420 So there are all kinds of rules. 35:36.000 --> 35:37.280 This is just some listing. 35:37.400 --> 35:38.420 It's not complete, certainly. 35:39.100 --> 35:42.640 But there are rules how to modify the words that you actually have in 35:42.640 --> 35:45.060 a document in order to get the word stem. 35:45.860 --> 35:48.020 Now what is the effect with respect to searching? 35:49.300 --> 35:55.560 If you search for a certain term, and now you reduce the search term 35:55.560 --> 36:01.420 to a stem, you have more or less broadened your search. 36:04.280 --> 36:08.940 Certainly you need fewer words to store, because all the endings, all 36:08.940 --> 36:14.280 the different versions of some word, if you look for example at 36:14.280 --> 36:22.880 algorithm, now there are many different endings of that. 36:23.820 --> 36:31.020 It could be E N or S or U S if we have a German ending. 36:32.480 --> 36:35.320 We could have algorithmic and so on. 36:36.120 --> 36:40.680 All kinds of different query terms, they would all be reduced to 36:40.680 --> 36:41.100 algorithm. 36:41.760 --> 36:48.780 And in this way we have a broadened extension of the search to related 36:48.780 --> 36:49.280 words. 36:50.480 --> 36:57.940 Although we made a search for, let's say, algorithm, we at the same 36:57.940 --> 37:02.340 time would look for algorithms, algorithmus and algorithmic. 37:04.680 --> 37:08.260 So in this case we have an automatic extension of the search to 37:08.260 --> 37:10.100 related words, we get more results. 37:10.740 --> 37:14.440 And we have to store fewer words, we only have to store the word 37:14.440 --> 37:16.980 stems, and not all the variants of the word. 37:17.360 --> 37:21.400 So this reduces actually the search structure significantly. 37:22.880 --> 37:24.820 And then we have to build such a search structure. 37:25.380 --> 37:26.260 Now how do we do that? 37:26.980 --> 37:30.620 You all know search structures if you look into a book, you have an 37:30.620 --> 37:31.420 index in the end. 37:32.140 --> 37:38.160 So you have your very, very thick book, many different pages, and then 37:38.160 --> 37:39.480 in the end you have an index. 37:40.000 --> 37:45.200 And in that index you have a listing of all kinds of words, and for 37:45.200 --> 37:50.220 every word you get, in principle, the page number. 37:50.800 --> 37:54.640 So you get the page number where you have to look for the specific 37:54.640 --> 37:59.620 symbol, maybe the first occurrence, or maybe also a list of 37:59.620 --> 38:03.380 occurrences of a certain word in the document. 38:03.920 --> 38:11.020 That's what you know from printed books, at least for books, like 38:11.020 --> 38:12.380 scientific books, for example. 38:13.280 --> 38:15.960 So there you have this index. 38:16.440 --> 38:20.840 Now this is some way you can do it, so where it occurs within the 38:20.840 --> 38:21.220 document. 38:22.800 --> 38:29.140 You could also try to calculate something like relevance for the word. 38:29.220 --> 38:31.600 Now what is the relevance or weight for a word? 38:31.720 --> 38:33.960 We will come back to that in a moment. 38:34.960 --> 38:40.680 And intuitively, how well does, or how strongly does a certain word 38:40.680 --> 38:42.720 characterize that document? 38:43.060 --> 38:46.640 Because a word might occur in many different documents, and you would 38:46.640 --> 38:55.180 like to present to the querier that document which has the most 38:55.180 --> 38:55.680 relevance. 38:55.900 --> 39:00.980 That means the document where the word that he or she looks for has 39:00.980 --> 39:02.180 the highest weight. 39:04.700 --> 39:10.900 The weight can also refer, for example, to the number of occurrences. 39:12.760 --> 39:16.560 So you could say I have a list of all the different positions where it 39:16.560 --> 39:19.740 occurs, or I just count how often it occurs. 39:22.240 --> 39:25.320 And then we have to look for possible data structures. 39:25.440 --> 39:29.500 We could have a sorted list as we do it in the printed version of the 39:29.500 --> 39:29.740 book. 39:29.780 --> 39:34.740 We have a sorted list of all the words, and then we have the links to 39:34.740 --> 39:35.300 the positions. 39:36.000 --> 39:38.640 So that's a sorted list with random access. 39:39.020 --> 39:45.260 It's not really random access, it's a mixture of sequential and random 39:45.260 --> 39:48.880 access, because we have, on the different pages, we can look at the 39:48.880 --> 39:52.500 pages and have more or less random access, and then we have to turn 39:52.500 --> 39:54.460 the pages in a printed book. 39:54.700 --> 39:58.660 But in a computer we can do a sorted list with random access, and then 39:58.660 --> 40:04.640 we know we have logarithmic access time by, for if we have some word, 40:04.700 --> 40:07.780 we just have to locate the right position, which means logarithmic 40:07.780 --> 40:12.700 access time by binary search, and it's a very simple structure. 40:12.920 --> 40:18.240 But we have to rebuild that index any time or every time we get a new 40:18.240 --> 40:21.560 entry into that list. 40:22.260 --> 40:26.960 We know that rebuilding a sorted list is expensive, because we might 40:26.960 --> 40:33.040 have to shift certain certain positions quite, like if we have to 40:33.040 --> 40:36.800 enter something here, all the remainder has to be shifted by one 40:36.800 --> 40:38.000 position, which is expensive. 40:39.040 --> 40:42.920 Okay, so if you have a dynamically changing 40:46.280 --> 40:52.620 document, or number of documents, then it will be expensive to have a 40:52.620 --> 40:55.040 sorted list, because it would be changing all the time. 40:55.620 --> 40:58.560 And if we look for having an index for the documents in the World Wide 40:58.560 --> 41:03.500 Web, we definitely know that it's changing all the time, so a sorted 41:03.500 --> 41:05.400 list is not really the answer. 41:06.020 --> 41:09.940 It's the answer for a fixed document, it's perfect. 41:11.180 --> 41:12.900 It can be very nice. 41:13.080 --> 41:17.760 We will see also other possibilities to do that. 41:18.340 --> 41:21.120 Then the other possibilities definitely are tree structures, as you 41:21.120 --> 41:25.340 know from introductory courses to informatics, tree structures always 41:25.340 --> 41:30.640 have the example that we have a structure which has logarithmic time 41:30.640 --> 41:35.580 for all the interesting lexicographic or dictionary operations like 41:35.580 --> 41:40.380 insertion, deletions, and searches can all be done in an appropriate 41:40.380 --> 41:46.660 tree structure in time that is logarithmic, the size of the tree. 41:47.320 --> 41:48.720 So that's an advantage. 41:50.240 --> 41:52.960 So tree structures could be a choice. 41:54.040 --> 41:56.400 And then there are many different possibilities for that. 41:57.040 --> 42:02.500 So a very common tree structure for large sets of data are B-trees. 42:03.600 --> 42:04.940 Have you ever seen a B-tree? 42:05.900 --> 42:06.540 Any of you? 42:07.280 --> 42:07.740 Not? 42:08.020 --> 42:10.600 Then I will briefly give you an example of that. 42:11.200 --> 42:14.060 And there are other kinds of trees, like many different types of 42:14.060 --> 42:14.440 trees. 42:14.820 --> 42:22.640 I will show you in particular the trees spelled in a strange way, with 42:22.640 --> 42:23.440 an I-E. 42:24.240 --> 42:31.360 And this I-E, like T-R-I-E, is referring to a tree structure which is 42:31.360 --> 42:34.620 designed for supporting information retrieval. 42:35.480 --> 42:42.260 And here the tree is actually spelled with I-E. 42:42.780 --> 42:47.660 That's why we call it a tree with an I-E, indicating that this is 42:47.660 --> 42:49.100 something for information retrieval. 42:49.700 --> 42:54.420 So there have been specific structures that have been designed for 42:54.420 --> 42:58.800 information retrieval, tree structures, and I will show you in 42:58.800 --> 43:04.080 particular the so-called Patricia trees, which have certain, or just 43:04.080 --> 43:05.840 nice properties. 43:06.540 --> 43:11.040 These are specific versions of special cases of so-called suffix 43:11.040 --> 43:11.320 trees. 43:11.920 --> 43:16.900 Suffix trees are basic data structure in information retrieval. 43:18.420 --> 43:22.260 Okay, but first let me briefly show you what a B-tree is. 43:22.320 --> 43:27.600 A B-tree, the B comes, or originates from the author of that paper 43:27.600 --> 43:31.260 where this structure was introduced a long, long time ago. 43:32.900 --> 43:37.220 Rudolf Bayer, a professor at the Technical University of Munich, a 43:37.220 --> 43:39.780 long time ago, he designed the B-trees. 43:40.800 --> 43:46.540 And it's a completely balanced structure, and you will see, like I 43:46.540 --> 43:53.000 show you this example here, it has no entries, I will fill it with a 43:53.000 --> 43:56.640 few notes, or with a few keys in the moment. 43:57.060 --> 44:06.400 So a B-tree of degree m is a tree where, well first of all, all the 44:06.400 --> 44:09.960 leaves have the same, are at the same depth. 44:10.460 --> 44:15.720 That means the distance to the root is the same for all trees, for all 44:15.720 --> 44:21.520 leaves, as you can see here, this is the layer where you have like the 44:21.520 --> 44:27.560 third layer of the root, the first layer, the second layer, or 44:27.560 --> 44:29.560 whatever, however you count. 44:30.000 --> 44:34.120 Let's, if we start at zero, that's zero, one, and layer two. 44:34.560 --> 44:39.600 So here we have all the leaves, distance two from the root. 44:40.540 --> 44:46.180 Every inner node, except for the root, has at least m over two 44:46.180 --> 44:46.980 successors. 44:48.720 --> 44:53.700 Yeah, so we have, if we have, like here m is three, m over two 44:53.700 --> 44:57.440 successors means at least two successors. 44:59.380 --> 45:04.480 And at most m successors, in this case, the simple case, at most 45:04.480 --> 45:04.980 three. 45:05.380 --> 45:10.880 If m is one thousand, usually it's in the range of one k or two k or 45:10.880 --> 45:17.080 something, or maybe just five hundred, then it's, assume it's two to 45:17.080 --> 45:22.860 the ten, then we would have at least five hundred successors, and at 45:22.860 --> 45:24.460 most one thousand successors. 45:25.860 --> 45:28.100 Why do you need that many successors? 45:28.780 --> 45:36.840 The reason is that if you fetch the information for such a node, then 45:36.840 --> 45:44.260 this node should be about one block in main memory, and in secondary 45:44.260 --> 45:46.360 memory, in particular in secondary memory. 45:46.520 --> 45:52.580 So you always fetch the complete node if you look for information, and 45:52.580 --> 45:56.820 then certainly you have further possibilities to branch out. 45:58.000 --> 46:03.300 But if you look for a specific element in that tree, you would like to 46:03.300 --> 46:07.920 reduce the number of disk accesses as much as possible. 46:09.280 --> 46:13.440 With every disk access, you get one block. 46:15.220 --> 46:20.240 And so you don't want, like if you need all the information here, you 46:20.240 --> 46:24.700 don't want to have many disk accesses, and so you want to reduce the 46:24.700 --> 46:27.300 number of accesses as much as possible. 46:28.360 --> 46:34.480 The maximum thing you can get with one access is one block, and so if 46:34.480 --> 46:40.400 this block is just one node, you have maximum utilization, and so this 46:40.400 --> 46:42.420 is why it is designed in this way. 46:42.600 --> 46:47.900 It's reducing the number of disk accesses in a tree structure as much 46:47.900 --> 46:48.500 as possible. 46:49.660 --> 46:52.320 So it's used for database structures. 46:53.420 --> 47:01.380 And then, not every node has m successors, but they might have at 47:01.380 --> 47:09.000 least m over 2, at most m, and if there are k minus one keys in there, 47:09.400 --> 47:11.580 then we have k successors. 47:11.660 --> 47:17.440 Because k minus one keys, every key, every item in a node can be used 47:17.440 --> 47:22.820 to branch out to different children of that node. 47:23.660 --> 47:25.360 So let's look at an example. 47:25.640 --> 47:30.560 Let's, for example, like here, the dots indicate here the keys. 47:31.160 --> 47:35.580 So if m is three, the maximum number of keys that we can have in a 47:35.580 --> 47:36.140 node is two. 47:37.280 --> 47:47.080 So assume here that we have, for example, 15 and, for example here, 32 47:47.080 --> 47:49.480 numeric values. 47:52.380 --> 47:59.380 And here, like, we branch out whenever we have, or when we're looking 47:59.380 --> 48:04.000 for a value which is smaller than 15, we would go to this node here. 48:04.400 --> 48:09.060 And this node, assume that we have here, let's say just 5 and 10. 48:10.880 --> 48:17.020 Now if we would look for 5, we would look in, we would get into that 48:17.020 --> 48:21.820 root node, see, okay, it's smaller than 15, so we have to take that 48:21.820 --> 48:26.480 branch, get to this node, and we would find the 5 in there. 48:26.840 --> 48:32.420 If we would look for 12, we would also branch to that node and find 48:32.420 --> 48:38.500 out, well, 12 is larger than 10, so 12 is not in that tree at the 48:38.500 --> 48:38.820 moment. 48:39.340 --> 48:41.880 If we would have to insert it, we would have to do something with 48:41.880 --> 48:42.100 that. 48:43.360 --> 48:46.760 We would have to insert it in some way, now it cannot be inserted into 48:46.760 --> 48:50.680 that node, then we would have to split that node and do certain things 48:50.680 --> 48:53.520 in order to, like in this case, if we would insert something here, 48:54.060 --> 48:57.680 this would lead to a rebuilding of the tree, which can be done in 48:57.680 --> 48:58.600 logarithmic time. 48:59.520 --> 49:04.600 Now, here, let's assume we have something like 20, and then here could 49:04.600 --> 49:08.820 be, for example, 32 and maybe 50. 49:09.340 --> 49:16.100 Yeah, so here, that would be a potential or possible selection of 49:16.100 --> 49:22.040 keys, or association of keys with those nodes in accordance with that 49:22.040 --> 49:23.460 structure that I indicated here. 49:25.060 --> 49:32.180 And then you can, if you now look for certain elements, you can use 49:32.180 --> 49:33.740 that tree structure in a simple way. 49:33.840 --> 49:34.780 So this is the B-tree. 49:35.980 --> 49:43.560 It's having many advantages, has a nice structure, and in particular 49:43.560 --> 49:50.020 for very large data or sets of data items, this is a very convenient 49:50.020 --> 49:53.740 structure because it is, as I said, reducing the number of disk 49:53.740 --> 49:54.360 accesses. 49:54.900 --> 50:02.340 So if you have, for example, 1,000 elements here in such a node, and 50:02.340 --> 50:07.500 now you have to find the appropriate position in between those 1,000 50:07.500 --> 50:13.060 elements, now for that we use, then you use again binary search, which 50:13.060 --> 50:15.660 is very fast if you do it in main memory. 50:16.780 --> 50:20.500 So this is, you have to, you need time to actually find the 50:20.500 --> 50:25.980 appropriate position in such a node, which has many keys, to find the 50:25.980 --> 50:31.040 appropriate next branch that you have to look at if you are not 50:31.040 --> 50:34.140 successful in finding the key that you're looking for. 50:35.040 --> 50:39.220 And that is logarithmic in the size of the node. 50:40.220 --> 50:50.880 And so you have that logarithmic time there, but it is done in main 50:50.880 --> 50:54.720 memory, which can be done very fast, much faster than just one disk 50:54.720 --> 50:55.580 access as we know. 50:56.820 --> 51:02.420 So search, insert, and delete can be done easily in time, logarithmic 51:02.420 --> 51:06.840 in the number of keys, base to the base m in this case, because that's 51:06.840 --> 51:11.300 the branching degree, so the size, the number of nodes that we have 51:11.300 --> 51:15.080 there is a bit smaller, although if you have logarithmic to the base m 51:15.080 --> 51:20.240 of n, it's the same as logarithm, like if m is a constant, it's the 51:20.240 --> 51:23.100 same as the dual logarithm of n. 51:23.740 --> 51:23.920 Okay. 51:25.180 --> 51:32.160 So, as I said, m is usually about half the memory page size, and so 51:32.160 --> 51:35.740 all the keys of a node fit into one page of memory, and in one access 51:35.740 --> 51:41.360 to the secondary memory, you can get here one complete node, which is 51:41.360 --> 51:47.840 an important feature, because then you can do the selection of the 51:47.840 --> 51:54.400 next page just by looking at those elements in one, in the information 51:54.400 --> 51:56.340 that you just retrieved from disk. 51:56.680 --> 51:56.800 Okay. 51:57.480 --> 51:58.540 That's the B-tree. 51:59.120 --> 52:01.980 I don't want to go into all the details, so I don't present to you 52:01.980 --> 52:07.440 here the algorithms for inserting, for deleting, for... well, for 52:07.440 --> 52:10.800 searching is simple, but for insertion and deletions, you have to 52:10.800 --> 52:14.680 think a bit more about how you do that in order to preserve this 52:14.680 --> 52:19.800 structure that is in there, because it should never be below m over 52:19.800 --> 52:26.440 two descendants, and should never have more than m descendants, or 52:26.440 --> 52:27.240 children of a node. 52:27.880 --> 52:32.720 But the more interesting point here is the structure that has been 52:32.720 --> 52:37.820 designed specifically for the information retrieval purpose, and what 52:37.820 --> 52:40.240 we are doing when we are searching for information on the World Wide 52:40.240 --> 52:43.540 Web, is that we have an information retrieval situation. 52:45.140 --> 52:51.660 And so we need a data structure for the efficient retrieval of words 52:51.660 --> 52:59.780 by character-based comparisons, and the branching degree here will be 52:59.780 --> 53:01.920 about the size of the alphabet. 53:02.700 --> 53:03.940 We'll see that in a moment. 53:04.300 --> 53:08.720 So here, for example, we have a set of words, and we would like to 53:08.720 --> 53:11.620 build a tree resembling that set of words. 53:11.760 --> 53:17.120 And we would like, like, now we have... we look for a certain... we 53:17.120 --> 53:21.200 get a query, and there's a certain word in that query, and now we 53:21.200 --> 53:24.520 would like to locate that word, find out whether we have that word in 53:24.520 --> 53:29.980 our document, or in our index, and so how would we represent such a 53:29.980 --> 53:30.200 set? 53:31.300 --> 53:35.060 We could do that by looking at the symbols that we have, the first 53:35.060 --> 53:35.500 symbol. 53:36.360 --> 53:39.780 So we look at the first symbol, there we have either a w or an s, so 53:39.780 --> 53:43.820 we only have a branching degree of two here, other symbols don't occur 53:43.820 --> 53:46.280 as the first symbols in the words that we have here. 53:46.800 --> 53:50.380 So we have here a branching degree of two in this case, from the root, 53:51.160 --> 53:55.220 and if we have an s, we know immediately this must be the word zind. 53:55.980 --> 54:00.180 Or we can, if we have some word that we are looking for, a certain 54:00.180 --> 54:03.840 pattern, which is starting with an s, we can immediately compare it to 54:03.840 --> 54:07.900 zind, and we know whether it is... whether we look for zind, or 54:07.900 --> 54:09.540 whether we look for a different word. 54:09.980 --> 54:12.640 If we have the w as the first symbol, there are many different 54:12.640 --> 54:13.340 possibilities. 54:13.920 --> 54:19.640 The next symbol there is either an e or an i or an o. 54:20.540 --> 54:25.180 Just ordered here lexicographically, e, i, o is the next branches, 54:25.800 --> 54:29.980 then we have, if it's an i, we know it can only be the word wir. 54:30.380 --> 54:33.060 If it's an o, it can only be the word wo. 54:33.580 --> 54:38.140 And if it is an e, it can be either wir or weiss, and we have to look 54:38.140 --> 54:39.220 at the next symbol again. 54:40.160 --> 54:45.720 And so then we know what actually these... or how we can represent 54:45.720 --> 54:46.260 those words. 54:46.340 --> 54:51.340 So that is a tree resembling or representing that set of words. 54:51.520 --> 54:57.740 And so we have a tree structure for representing that set of words, a 54:57.740 --> 54:59.200 very simple set of words. 54:59.880 --> 55:03.480 The benefit is not that obvious here in the moment, but you can 55:03.480 --> 55:06.600 imagine if you have a larger set of words, you immediately get 55:06.600 --> 55:07.980 benefits for that. 55:08.960 --> 55:15.280 So this is the first idea, to use the... essentially build a tree that 55:15.280 --> 55:17.480 resembles a set of patterns. 55:18.020 --> 55:22.860 This is actually also what would have been done if you would do a 55:22.860 --> 55:26.380 pattern search, like pattern matching, for a set of patterns, a finite 55:26.380 --> 55:27.140 set of patterns. 55:27.700 --> 55:31.360 We would build a similar tree and then use that kind of a tree for 55:31.360 --> 55:31.900 pattern matching. 55:32.640 --> 55:37.580 But what we are actually doing is that we have some document, and a 55:37.580 --> 55:42.900 document can be viewed as a long sequence of symbols. 55:44.200 --> 55:49.040 Certainly a document rather looks like a certain... like we have 55:49.040 --> 55:53.040 certain lines there, but I can just view that as a sequence of 55:53.040 --> 55:53.300 symbols. 55:54.280 --> 56:00.020 And if we look at a word, what we actually do is we look for a certain 56:00.020 --> 56:03.560 position where a certain word occurs. 56:03.840 --> 56:10.300 So for example, if we look for the word bus, then we would have it... 56:10.300 --> 56:15.340 and it starts there, then we would have a blank before that, and 56:15.340 --> 56:16.660 that's what we look for. 56:17.040 --> 56:20.260 And we look for the first occurrence of the word bus, or maybe for all 56:20.260 --> 56:23.560 the occurrences of the word bus in the document. 56:25.580 --> 56:35.420 And to find that position, we can just look for a suffix of our 56:35.420 --> 56:39.920 document which is starting with a pattern that we are looking for. 56:42.260 --> 56:48.700 And so this is something which is called a semi-infinite string, or a 56:48.700 --> 56:49.200 sys string. 56:50.740 --> 56:53.500 So these are suffixes of a character sequence. 56:55.720 --> 57:00.600 So in this case, I look for all the suffixes, or if I look for bus, I 57:00.600 --> 57:10.100 would look for all the positions where the suffix starts having bus as 57:10.100 --> 57:11.000 the first symbol. 57:13.760 --> 57:17.860 Then maybe it is longer, maybe here we have buses. 57:19.300 --> 57:22.600 It doesn't matter, bus is the start of that. 57:23.520 --> 57:28.500 And so, if we try to characterize that, and we would like to, now here 57:28.500 --> 57:31.560 in a simplified way, just have a binary sequence. 57:32.520 --> 57:38.240 Just look at the first eight suffixes of that sequence of binary 57:38.960 --> 57:39.700 values. 57:40.680 --> 57:47.320 One, two, three, four, five, six, seven, eight. 57:49.860 --> 57:54.920 So we just look at those suffixes of this string. 57:55.660 --> 58:00.100 We would like to build a search structure which resembles exactly 58:00.100 --> 58:02.480 those eight different suffixes. 58:03.820 --> 58:05.820 How can we distinguish those suffixes? 58:06.760 --> 58:10.520 It's shown here immediately in that tree. 58:10.600 --> 58:11.540 Now what is this showing? 58:12.580 --> 58:18.780 Maybe we have a zero as the first symbol. 58:19.660 --> 58:23.100 Now there are several suffixes starting with a zero. 58:25.000 --> 58:25.060 Yeah? 58:25.660 --> 58:28.180 There, there, there, there. 58:28.320 --> 58:33.020 So we have one, two, three, four, five different suffixes starting 58:33.020 --> 58:33.800 with a zero. 58:34.620 --> 58:37.060 Now the next symbol can be a zero. 58:38.540 --> 58:41.720 We don't have that many suffixes starting with two zeros. 58:42.660 --> 58:44.120 There and there. 58:45.520 --> 58:47.700 And this one also, three. 58:49.680 --> 58:50.340 Now what is the next? 58:50.380 --> 58:54.940 If the next symbol is another zero, three zeros, this is only 58:54.940 --> 58:56.920 occurring at this position. 58:57.180 --> 58:58.420 That is position seven. 59:01.040 --> 59:04.820 All the others have different starting sequences, different prefixes. 59:06.440 --> 59:11.640 And then if after two zeros we have a one, after two zeros we have a 59:11.640 --> 59:11.880 one. 59:12.040 --> 59:14.080 This can happen here. 59:16.780 --> 59:18.280 Two zeros and a one. 59:19.420 --> 59:22.200 And there we also have two zeros and a one. 59:22.620 --> 59:29.060 And now you notice that those two suffixes have the same next symbol, 59:29.360 --> 59:32.240 namely a zero in both cases. 59:33.240 --> 59:38.020 And the first position where they are different is the next position. 59:38.160 --> 59:42.360 There they have either a zero or a one, and then we know which is the 59:42.360 --> 59:44.300 position of that suffix we are looking for. 59:44.380 --> 59:47.900 It's either position four or position eight. 59:49.400 --> 59:55.460 Because that's indicating the positions where those suffixes can be 59:55.460 --> 59:55.880 distinguished. 59:56.660 --> 01:00:00.540 And if we have just one starting zero and then a one, then we have two 01:00:00.540 --> 01:00:01.660 different situations. 01:00:01.880 --> 01:00:06.980 It's either that one or that one, and those can be distinguished by 01:00:06.980 --> 01:00:10.880 looking at the next symbol, which is either a zero or a one, and then 01:00:10.880 --> 01:00:12.360 we know which positions we are at. 01:00:12.680 --> 01:00:14.500 And the same is happening for the remainder. 01:00:15.900 --> 01:00:21.540 So this way we look at the... we have a certain pattern that we look 01:00:21.540 --> 01:00:21.900 for. 01:00:22.600 --> 01:00:27.480 For example, for zero, zero, one, one. 01:00:30.280 --> 01:00:31.800 We don't have that in there. 01:00:32.300 --> 01:00:36.740 So zero, zero, one, one does not occur, so that's not in the word. 01:00:36.740 --> 01:00:42.760 If it is zero, zero, one, zero, zero, zero, one, zero, we know... not 01:00:42.760 --> 01:00:46.240 really, but we know that it occurs, but we know it occurs twice. 01:00:46.720 --> 01:00:55.360 If we get to like zero, zero, one, zero, we are at this node, and this 01:00:55.360 --> 01:01:01.200 node is a node having... it's like we have a subtree below that having 01:01:01.200 --> 01:01:01.920 two leaves. 01:01:02.380 --> 01:01:08.320 And so we know it's occurring twice, two times, and we also see the 01:01:08.320 --> 01:01:08.680 positions. 01:01:10.160 --> 01:01:14.100 And if we would just look for a suffix starting with zero, one, we 01:01:14.100 --> 01:01:16.600 would get to that position, and so on. 01:01:17.480 --> 01:01:21.300 We have immediately the number of occurrences, which is the size of 01:01:21.300 --> 01:01:25.480 the subtree, or the number of leaves in that subtree, which you could 01:01:25.480 --> 01:01:27.240 actually store in that node. 01:01:28.680 --> 01:01:32.840 Yeah, you can always calculate the number of leaves that you have, and 01:01:32.840 --> 01:01:36.920 so if you are in a certain node here, you know how many leaves are 01:01:36.920 --> 01:01:44.080 below that, and so you have immediately for a certain prefix of a 01:01:44.080 --> 01:01:49.840 suffix, you have immediately the number of occurrences of that prefix 01:01:49.840 --> 01:01:53.180 in your complete document. 01:01:54.720 --> 01:01:57.580 And now we have to refine that, and make that more efficient. 01:01:58.820 --> 01:02:00.060 Why is this not efficient? 01:02:00.280 --> 01:02:01.760 What you see here is the following. 01:02:02.440 --> 01:02:09.120 Here, for example, you have not really something which is giving you 01:02:09.120 --> 01:02:13.560 more information, because you look at a position where you know the 01:02:13.560 --> 01:02:16.400 suffixes will not be different in this case. 01:02:16.840 --> 01:02:18.380 In this case, here you have the same. 01:02:19.200 --> 01:02:22.720 So you can actually, you could reduce that. 01:02:23.800 --> 01:02:32.480 And so we will look at more efficient versions of that in a moment. 01:02:32.920 --> 01:02:37.140 This is just another explanation here that the different systrings are 01:02:37.140 --> 01:02:40.620 identified by the starting position, what I showed you already, and 01:02:40.620 --> 01:02:41.740 now we get to the improvement. 01:02:42.860 --> 01:02:45.740 So we would like to delete redundant comparisons. 01:02:47.080 --> 01:02:50.820 We would like to delete those non-branching paths, and there are two 01:02:50.820 --> 01:02:56.060 of those here, two indicated in green, those nodes could be deleted. 01:02:56.660 --> 01:03:02.140 We would only like to look at those occurrences of symbols which 01:03:02.140 --> 01:03:04.600 distinguish different suffixes. 01:03:06.260 --> 01:03:10.140 And so we can delete those non-branching paths and have a slightly 01:03:10.140 --> 01:03:10.920 smaller version. 01:03:11.020 --> 01:03:15.620 But you can imagine that there will be more such possibilities if you 01:03:15.620 --> 01:03:20.240 have a more interesting suffix structure, more interesting documents. 01:03:20.900 --> 01:03:25.420 And this will lead to a larger reduction in the size of the trees. 01:03:26.720 --> 01:03:31.680 So this, again, would be just the first eight suffixes of that string 01:03:31.680 --> 01:03:32.460 that we looked at. 01:03:33.200 --> 01:03:37.440 And now this is actually a Patricia tree. 01:03:38.100 --> 01:03:44.080 And Patricia will be, I guess that it was a certain name of a person 01:03:44.080 --> 01:03:48.580 that the author liked, and you always try to get an acronym which is 01:03:48.580 --> 01:03:53.220 nice, so the Patricia certainly has nothing to do with a woman, but 01:03:53.220 --> 01:03:58.680 only with practical algorithms to retrieve information coded in 01:03:58.680 --> 01:03:59.400 alphanumeric. 01:04:00.080 --> 01:04:00.680 Yeah? 01:04:01.360 --> 01:04:02.280 So this is Patricia. 01:04:02.980 --> 01:04:05.860 This is not coded in alphanumeric, this is just binary. 01:04:06.400 --> 01:04:11.900 So we are actually looking or interested in trees where we have a 01:04:11.900 --> 01:04:15.480 larger alphabet, for example the Latin alphabet, and then look for 01:04:15.480 --> 01:04:21.560 documents and for patterns in those documents having alphanumeric 01:04:21.560 --> 01:04:22.180 representation. 01:04:24.180 --> 01:04:29.000 And another version of that is an abbreviation, not a Patricia tree, 01:04:29.220 --> 01:04:36.040 but a Pat tree, where you look at all the suffixes of a text, and what 01:04:36.040 --> 01:04:40.020 you look at particularly is at the beginning of a word. 01:04:40.940 --> 01:04:45.600 So that certainly reduces significantly the number of suffixes that 01:04:45.600 --> 01:04:50.320 you have to store in that structure, because you also only look at the 01:04:50.320 --> 01:04:57.180 suffixes starting at the beginnings of words, and not all the other 01:04:57.180 --> 01:04:57.640 ones. 01:04:59.320 --> 01:04:59.440 Yeah? 01:04:59.480 --> 01:05:03.300 Because usually we look for words, and words, or you could say 01:05:03.300 --> 01:05:09.920 starting at, after a separator symbol, as we have looked at before, 01:05:10.480 --> 01:05:14.900 how we would actually separate a document into words. 01:05:15.920 --> 01:05:19.780 And so if we have this, again, simple example, you know that I always 01:05:19.780 --> 01:05:22.880 have to take simple examples because they have to fit on a page, on a 01:05:22.880 --> 01:05:23.240 slide. 01:05:24.420 --> 01:05:35.120 If we have this document, we have vice versa, then we can build a tree 01:05:35.120 --> 01:05:40.600 from that, a suffix tree, or a Pat tree, where we only look at the 01:05:40.600 --> 01:05:46.640 suffixes starting at the startings, or the positions where a word is 01:05:46.640 --> 01:05:52.060 starting, and so we only have two different initial symbols, P or W. 01:05:54.660 --> 01:06:01.900 Now if we have a P as the first symbol, we have two such... if we have 01:06:01.900 --> 01:06:11.720 a P, we know, oh, there are two possible suffixes, and those suffixes 01:06:11.720 --> 01:06:15.540 have quite a large initial prefix that is the same. 01:06:16.180 --> 01:06:21.020 So the first position where they actually differ is after the R. 01:06:21.400 --> 01:06:24.180 Either you have a blank there, or you have an S. 01:06:26.360 --> 01:06:32.440 And so here, we just, now we have this simplified version, we have 01:06:32.440 --> 01:06:36.940 deleted all the nodes in between, we are at position six, and if at 01:06:36.940 --> 01:06:41.720 position six, after that initial position, we have a blank or an S, we 01:06:41.720 --> 01:06:48.360 know we are either at location 13 here, or there at position 19. 01:06:49.700 --> 01:06:53.460 And if it started with a W, then we look at, we have to, the next 01:06:53.460 --> 01:06:59.480 difference is at position two, either an E or an O, and then at 01:06:59.480 --> 01:07:03.860 position three, we have either an I or an R, or if it was an O, we 01:07:03.860 --> 01:07:06.280 have either a blank or an H. 01:07:07.980 --> 01:07:12.020 And so using this simple structure, we have actually stored all the 01:07:12.020 --> 01:07:16.520 information about the starting positions of suffixes which are of 01:07:16.520 --> 01:07:20.600 relevance with respect to potential patterns that occur in that 01:07:20.600 --> 01:07:21.740 document. 01:07:23.840 --> 01:07:26.180 Potential words that occur in that document. 01:07:27.120 --> 01:07:29.560 And so this is the complete information that you need. 01:07:29.620 --> 01:07:35.400 But certainly you could say, well, if I get to this position six here, 01:07:37.660 --> 01:07:44.920 I notice P was the same, and now I look for the word pattern. 01:07:46.960 --> 01:07:48.900 I did not check the second symbol. 01:07:49.700 --> 01:07:52.120 I only checked the symbol number six. 01:07:55.560 --> 01:08:00.960 And so I would assume that I have the same, that it is an occurrence 01:08:00.960 --> 01:08:01.400 of that. 01:08:01.760 --> 01:08:08.780 So if I only look at a few symbols, I certainly have to afterwards, 01:08:09.280 --> 01:08:13.180 like when I know whether it occurs, I have to actually compare the 01:08:13.180 --> 01:08:18.920 word that I have, that I'm looking for with the actual sequence in 01:08:18.920 --> 01:08:20.540 that document. 01:08:21.580 --> 01:08:23.660 Or I could do something different. 01:08:24.780 --> 01:08:32.540 I could just, rather than storing positions of symbols in the notes, I 01:08:32.540 --> 01:08:36.840 could store sequences on the edges. 01:08:38.640 --> 01:08:43.920 And then I would indicate that if I start with a pattern, and if that 01:08:43.920 --> 01:08:49.760 pattern starts with a Peter, then the next thing I have to look at is 01:08:49.760 --> 01:08:53.400 whether you have a blank or an S, and then you get the different 01:08:53.400 --> 01:08:53.880 positions. 01:08:56.180 --> 01:09:04.240 So I just use the strings as labels of the edges, which are identical, 01:09:04.540 --> 01:09:09.800 and then if I look at a query, or execute a query, look for a certain 01:09:09.800 --> 01:09:16.720 term, then I have to compare my pattern with the symbols that are on 01:09:16.720 --> 01:09:17.440 the edge. 01:09:18.500 --> 01:09:25.780 And in this way I can locate the occurrences of patterns in the 01:09:25.780 --> 01:09:28.120 document using that search structure. 01:09:30.320 --> 01:09:36.880 Now, and as you see, if it's just, if you get to a certain position 01:09:36.880 --> 01:09:42.260 there, you immediately know how many leaves are underneath that, so 01:09:42.260 --> 01:09:46.600 that means how many occurrences you have, and you can locate the 01:09:46.600 --> 01:09:50.600 occurrences by just going to those leaves, and then you have the 01:09:50.600 --> 01:09:53.780 specific occurrences that you are interested in. 01:09:54.520 --> 01:09:59.640 So in this way we get a search structure for identifying the words 01:09:59.640 --> 01:10:05.080 that occur in a document, and as you see here, it's quite a reduced 01:10:05.080 --> 01:10:05.960 structure. 01:10:06.100 --> 01:10:10.060 You can imagine that it will be quite, or what kind of structures you 01:10:10.060 --> 01:10:10.240 get. 01:10:10.780 --> 01:10:14.520 So, if we search in a pet tree, how can we do that? 01:10:14.660 --> 01:10:19.460 We just, we can, we determine the starting point for pattern matching. 01:10:19.640 --> 01:10:24.120 So if we have the second version, we just locate, or look at the 01:10:24.120 --> 01:10:30.020 pattern on the edge, and compare that pattern on the edge with the, or 01:10:30.020 --> 01:10:34.080 that sequence on the edge with the sequence that we have in the 01:10:34.080 --> 01:10:36.640 pattern that we are currently looking for. 01:10:38.420 --> 01:10:46.720 And then we can also compare, like we compare the search term and the 01:10:46.720 --> 01:10:53.140 suffix, which is only necessary if we use the initial version where we 01:10:53.140 --> 01:10:58.460 only have letters as labels and not the sequences, and we have to 01:10:58.460 --> 01:11:02.180 store positions in the nodes, because then we would skip certain 01:11:02.180 --> 01:11:06.400 symbols in between and would have to do the comparison afterwards. 01:11:07.180 --> 01:11:10.840 This is a trade-off of when you have to do certain things. 01:11:12.280 --> 01:11:17.780 And then, what do we do if we insert something? 01:11:18.580 --> 01:11:24.180 This is similar to inserting something in search trees, which is a 01:11:24.180 --> 01:11:25.040 standard operation. 01:11:25.580 --> 01:11:31.980 You just rebuild the tree in some way, and on the next slide, which is 01:11:31.980 --> 01:11:41.100 slide 42, you see here a pet tree for that very strange... here again, 01:11:42.140 --> 01:11:49.600 it is not really a case for a pet tree, because all the suffixes 01:11:49.600 --> 01:11:53.800 starting at those positions, not just starting at the starting 01:11:53.800 --> 01:11:58.440 positions of words, but to make it simpler, to have just the, like 01:11:58.440 --> 01:12:01.900 these are, you could say, the starting positions at words, and just 01:12:01.900 --> 01:12:07.280 look at a tree that is being built from that. 01:12:08.240 --> 01:12:17.860 Just try to build the pet tree starting from an empty tree, insert all 01:12:17.860 --> 01:12:22.280 the different symbols that you have there, and then gradually get a 01:12:22.280 --> 01:12:24.040 structure which should be similar to that one. 01:12:26.020 --> 01:12:30.320 We were here, we would like to insert something, we can do that, it's 01:12:30.320 --> 01:12:31.060 not that difficult. 01:12:31.640 --> 01:12:34.140 We can look for the frequency of a word. 01:12:34.200 --> 01:12:39.740 As I said, we just look for the number of leaves underneath a certain 01:12:39.740 --> 01:12:43.260 node, the number of leaves in the corresponding subtree of the pet 01:12:43.260 --> 01:12:47.760 tree, and that can be easily stored in the node, because you know how 01:12:47.760 --> 01:12:54.080 many differences you actually computed, and so this frequency is 01:12:54.080 --> 01:12:56.700 easily stored in the node. 01:12:58.200 --> 01:13:01.620 The most frequent word in the text, how can we determine that? 01:13:02.620 --> 01:13:11.540 The most frequent word in the text, well, we search all the paths from 01:13:11.540 --> 01:13:19.180 the root to the next blank, so if we have our document, we have a 01:13:19.180 --> 01:13:22.800 certain sequence, and then we might have a blank in there, so that's a 01:13:22.800 --> 01:13:29.580 word that is in our document, and so we just have to look at all the 01:13:29.580 --> 01:13:33.780 different branches that we have in the suffix tree on the pet tree. 01:13:34.280 --> 01:13:42.120 We can determine the starting points there, determine the words, and 01:13:42.120 --> 01:13:48.100 then we just look for the word leading to the largest subtree. 01:13:48.100 --> 01:13:56.000 You know, having the largest number of leaves, and so we can, just by 01:13:56.000 --> 01:13:59.800 looking at that search structure, we can easily compute the largest 01:13:59.800 --> 01:14:03.300 number of, or the most frequent word in that text. 01:14:04.240 --> 01:14:08.900 Because for every word we know, if we have a specific word, we get to 01:14:08.900 --> 01:14:14.720 the node, like from our starting point here, in some way we get to a 01:14:14.720 --> 01:14:21.420 node by branching appropriately, and then we just notice the size of 01:14:21.420 --> 01:14:21.980 that subtree. 01:14:22.560 --> 01:14:25.800 That's the frequency of that word in the text, and we do that for all 01:14:25.800 --> 01:14:29.120 the potential words in the text, and can do that just by looking at 01:14:29.120 --> 01:14:30.620 that suffix tree for that document. 01:14:31.700 --> 01:14:37.240 And then you can do a prefix search, which is easily done because you 01:14:37.240 --> 01:14:41.900 just be always looking at prefixes here. 01:14:42.700 --> 01:14:47.360 You can look at range searches, like all the words that are in between 01:14:47.360 --> 01:14:53.060 certain symbols, like in between ABC and ACC, looking, leading to 01:14:53.060 --> 01:15:02.320 different areas in the tree, and you can determine all the words that 01:15:02.320 --> 01:15:05.920 are in between there, like you have different branches and everything 01:15:05.920 --> 01:15:11.260 that is in between there, in between those things, are occurrences of 01:15:11.260 --> 01:15:13.000 this kind of range search. 01:15:14.040 --> 01:15:15.420 Longest repetition search. 01:15:16.340 --> 01:15:20.100 Search for the longest text repeated in the document. 01:15:21.080 --> 01:15:26.060 Now when does a word occur? 01:15:26.420 --> 01:15:27.360 At least twice. 01:15:29.840 --> 01:15:35.420 Definitely if it's leading to some position where you have at least 01:15:35.420 --> 01:15:40.880 two different leaves underneath, because that's two different 01:15:40.880 --> 01:15:41.280 positions. 01:15:42.440 --> 01:15:47.200 So you just have to look for the longest text, or the longest path, 01:15:47.360 --> 01:15:51.340 from the root to some inner node. 01:15:53.780 --> 01:16:02.940 Because the longest path to an inner node is the longest sequence that 01:16:02.940 --> 01:16:04.140 is occurring at least twice. 01:16:05.620 --> 01:16:11.200 Because underneath an inner node, you always have at least two leaves. 01:16:11.980 --> 01:16:14.140 And so, otherwise it would be a leaf. 01:16:15.360 --> 01:16:20.360 And so the longest path from the root to an inner node indicates the 01:16:20.360 --> 01:16:24.380 longest repetition search in, or the longest text repeated in the 01:16:24.380 --> 01:16:24.660 document. 01:16:25.840 --> 01:16:29.140 Then you can also do things like regular expression search and so on, 01:16:29.160 --> 01:16:33.180 so the suffix tree allows for many different operations that you would 01:16:33.180 --> 01:16:35.480 classically do in an information retrieval. 01:16:36.140 --> 01:16:41.100 Therefore it's a very convenient data structure which is used in 01:16:41.100 --> 01:16:44.380 searching in large sets of documents. 01:16:44.500 --> 01:16:49.360 For every document you build such a suffix tree, then you have to 01:16:49.360 --> 01:16:51.580 combine that information in appropriate ways. 01:16:52.460 --> 01:16:54.660 I showed you that slide already. 01:16:55.520 --> 01:16:57.620 And then there are all kinds of implementation variants. 01:16:57.800 --> 01:17:00.060 We had, like before, we looked at the B-tree. 01:17:00.160 --> 01:17:02.120 And in the B-tree we had very large nodes. 01:17:03.000 --> 01:17:06.160 Here we have rather small nodes. 01:17:07.760 --> 01:17:15.200 So if you look at this example that we had, you could combine certain 01:17:15.200 --> 01:17:21.060 nodes, like if you would combine those here on the right, those three 01:17:21.060 --> 01:17:25.600 nodes, those three inner nodes, into one supernode, certainly you 01:17:25.600 --> 01:17:32.480 would get into that node by just having a word starting with a W, and 01:17:32.480 --> 01:17:37.140 then you would have to do something inside that node in order to find 01:17:37.140 --> 01:17:39.060 the appropriate further positions. 01:17:41.860 --> 01:17:47.280 So you could just combine information from different parts of the tree 01:17:47.280 --> 01:17:53.080 into supernodes and then have a reduced structure, but you have to do 01:17:53.080 --> 01:17:54.620 more within the different nodes. 01:17:56.380 --> 01:17:59.360 The extreme case would be a pad array. 01:18:00.720 --> 01:18:01.760 What is a pad array? 01:18:02.780 --> 01:18:04.840 A pad array actually is not a tree, definitely. 01:18:05.660 --> 01:18:06.360 It's an array. 01:18:08.640 --> 01:18:12.560 And if you have an array, you obviously have all the problems with 01:18:12.560 --> 01:18:16.920 respect to dynamic changes of the document, but just to show you what 01:18:16.920 --> 01:18:22.440 you would get if you would actually reduce or transform a tree into an 01:18:22.440 --> 01:18:32.920 array, what you do there essentially is, well the leaves are ordered 01:18:32.920 --> 01:18:34.220 lexicographically. 01:18:35.320 --> 01:18:37.200 That's exactly what you see here. 01:18:38.080 --> 01:18:46.520 The first leaf is here Peter, then you have Petersen, then you have 01:18:50.080 --> 01:18:53.640 Weiss, Wehr, Wohl, und Wohlt. 01:18:54.480 --> 01:19:00.620 That's a lexicographical ordering of the suffixes of the initial verbs 01:19:00.620 --> 01:19:01.420 in this case. 01:19:03.540 --> 01:19:08.140 So it's a lexicographical ordering of the suffixes, the starting 01:19:08.140 --> 01:19:09.380 points of those suffixes. 01:19:09.960 --> 01:19:12.720 And now you're looking for a certain, like how do you use such a pad 01:19:12.720 --> 01:19:12.940 array? 01:19:13.600 --> 01:19:17.060 You're looking for a certain word, and then you just do binary search. 01:19:20.080 --> 01:19:23.480 So the retrieval in this case is rather simple. 01:19:23.640 --> 01:19:35.940 So retrieval, the search, would be just binary search with respect to 01:19:35.940 --> 01:19:40.500 the lexicographical ordering of the patterns in the words. 01:19:40.580 --> 01:19:43.840 So here you just have numbers, so you would have to look at the 01:19:43.840 --> 01:19:47.500 appropriate positions, or you could certainly also store, like what 01:19:47.500 --> 01:19:49.840 you store there depends on what you like to do. 01:19:49.840 --> 01:19:56.380 You could store there the first word, and then compare your pattern 01:19:56.380 --> 01:19:57.280 with the first word. 01:19:57.640 --> 01:20:02.660 You could also just store the position and link back to the document 01:20:02.660 --> 01:20:04.340 and look at what you have there. 01:20:04.860 --> 01:20:09.260 But simpler certainly would be to have the first words or some initial 01:20:09.260 --> 01:20:15.600 part at those locations in the pad array, and then do just binary 01:20:15.600 --> 01:20:19.280 search if you have a specific pattern that you look for, do binary 01:20:19.280 --> 01:20:20.640 search on that array. 01:20:21.300 --> 01:20:25.060 And you would have logarithmic time for retrieval of that information, 01:20:25.260 --> 01:20:28.000 or for carrying out that pattern matching. 01:20:30.720 --> 01:20:35.080 So that's nice, but if you have to rebuild it because you get a new, 01:20:35.720 --> 01:20:38.680 somehow you have a change in the document, you have to completely 01:20:38.680 --> 01:20:41.860 rebuild that thing, and you get linear time for that. 01:20:41.860 --> 01:20:46.880 So the more you compress such a structure, the more you have to do 01:20:46.880 --> 01:20:51.080 when you are rebuilding it, or when you have to rebuild it, because of 01:20:51.080 --> 01:20:52.080 changes in the document. 01:20:53.860 --> 01:20:58.260 Okay, so this is just showing you the implementation variants, and now 01:20:58.260 --> 01:20:59.400 just a few remarks. 01:21:00.480 --> 01:21:07.060 Just as some historic remark, how those structures had been designed, 01:21:07.720 --> 01:21:10.960 it's a long, long time ago in the 80s, 30 years ago. 01:21:12.300 --> 01:21:15.400 And at that time, the computers and storage capacities were very 01:21:15.400 --> 01:21:15.800 different. 01:21:16.980 --> 01:21:20.880 And so it was done at the University of Waterloo, one of the major 01:21:20.880 --> 01:21:22.720 competent centers for computer science. 01:21:23.660 --> 01:21:28.480 And they got a task, they had to construct an index for the Oxford 01:21:28.480 --> 01:21:29.540 English Dictionary. 01:21:29.620 --> 01:21:33.380 And the Oxford English Dictionary had about 600 megabits of text. 01:21:33.500 --> 01:21:37.300 That's not that much compared to current standards, what we have. 01:21:37.400 --> 01:21:43.980 But at that time, it was quite some task, quite some challenge. 01:21:44.100 --> 01:21:45.160 And why is that a challenge? 01:21:45.620 --> 01:21:47.560 Because 600 megabits of text. 01:21:48.260 --> 01:21:49.560 Now, what do we have to do? 01:21:50.640 --> 01:21:56.120 If we have a, over the thumb, very simple estimate of the time that 01:21:56.120 --> 01:21:56.960 you have to invest. 01:21:58.380 --> 01:22:04.300 Not a very optimistic, but a bit pessimistic. 01:22:04.840 --> 01:22:07.820 Very quick and naive estimate of the necessary time. 01:22:08.460 --> 01:22:12.300 So you assume, if you are building a search structure for that 01:22:12.300 --> 01:22:18.800 document, now there are many words in that document, and you are 01:22:18.800 --> 01:22:21.360 looking for all the words occurring in that document. 01:22:22.400 --> 01:22:27.400 Now, if you insert a new entry into the current index, if you build it 01:22:27.400 --> 01:22:32.180 up, you have to gradually start with some document, and then it's 01:22:32.180 --> 01:22:32.560 growing. 01:22:32.720 --> 01:22:38.700 It's getting larger and larger until you finally have all the words in 01:22:38.700 --> 01:22:39.260 that document. 01:22:41.060 --> 01:22:45.700 So initially it is a simple task, but then it grows more difficult, 01:22:45.820 --> 01:22:47.060 more difficult, and so on. 01:22:47.840 --> 01:22:50.680 And if you would just do that in linear ordering, take all the 01:22:50.680 --> 01:22:56.800 different words in your dictionary, and you could assume that you have 01:22:56.800 --> 01:23:03.860 some average size index structure, some kind of tree structure, and 01:23:03.860 --> 01:23:06.920 assume that it has, that it's built nicely. 01:23:08.080 --> 01:23:13.280 Then, if you have n different entries in such a tree structure, you 01:23:13.280 --> 01:23:17.880 have about log n accesses to that disk. 01:23:18.640 --> 01:23:22.600 And if you are unlucky, you have random accesses to disk. 01:23:23.460 --> 01:23:26.180 And if you have random accesses to disk, it means you need 01:23:26.180 --> 01:23:29.800 repositioning, and it's not a sequential access. 01:23:30.040 --> 01:23:35.380 And if you need repositioning of the, like within the disk, it means 01:23:35.380 --> 01:23:39.680 the access time is 5, here it says 5 to 50. 01:23:40.320 --> 01:23:45.420 Even, like, it's still, if you look at a disk in the moment, you are 01:23:45.420 --> 01:23:51.460 at 5 to 10 milliseconds for one disk access, because of the mechanical 01:23:51.460 --> 01:23:56.720 time you have to reposition the reading head. 01:23:58.120 --> 01:24:02.500 And, like, unless you have a solid state disk, as I have in my 01:24:02.500 --> 01:24:03.880 computer, it's much faster, therefore. 01:24:05.200 --> 01:24:10.340 But if you have a typical disk, then you have this access time. 01:24:10.760 --> 01:24:14.880 That means that, like, here it is pessimistic, just 30 disk accesses, 01:24:15.260 --> 01:24:20.300 even, like, let's just assume it's in that range, 30 disk accesses per 01:24:20.300 --> 01:24:20.600 second. 01:24:22.360 --> 01:24:27.260 Now you have 120 million index positions, 01:24:30.720 --> 01:24:35.960 600 megabits of text, so this is what they calculated is something 01:24:35.960 --> 01:24:38.160 like 120 million index positions. 01:24:40.000 --> 01:24:45.380 Now if you do that, and for every index, or every position, every 01:24:45.380 --> 01:24:52.060 information that you enter into the text, you need about log n random 01:24:52.060 --> 01:24:57.880 accesses, then if you calculate that appropriately, you get something 01:24:57.880 --> 01:25:04.500 like 30,000 hours for that, or 3.5 years to build that structure. 01:25:06.760 --> 01:25:12.880 Now, of course, we assume every time we have these random, these log n 01:25:12.880 --> 01:25:14.020 random access to disk. 01:25:14.340 --> 01:25:19.440 If we are more optimistic, and we say, well, we just have one disk 01:25:19.440 --> 01:25:23.220 access for one new entry, this is optimistic. 01:25:24.580 --> 01:25:25.440 Just one access. 01:25:26.940 --> 01:25:31.460 Even then, you would need 46 days to build that complete structure, 01:25:32.600 --> 01:25:37.760 because of the restriction of the time that we have for disk accesses. 01:25:38.260 --> 01:25:42.320 So we have to do something about that, and what we, what you do about 01:25:42.320 --> 01:25:46.260 that is you need some kind of practically efficient algorithm, which 01:25:46.260 --> 01:25:51.180 is taking into consideration the time you need for disk accesses, and 01:25:51.180 --> 01:25:55.960 just to show you briefly that next slide here, it's indicated what you 01:25:55.960 --> 01:25:59.720 do essentially, is that you do as much as possible in main memory, you 01:25:59.720 --> 01:26:06.420 avoid disk accesses, and you do, if you access the disk, you only use 01:26:06.420 --> 01:26:10.760 sequential access, so you have to modify your, or organize your 01:26:10.760 --> 01:26:14.900 structure, such that whenever you access the disk, you have sequential 01:26:14.900 --> 01:26:19.900 access, which can be done very fast, and random access only in main 01:26:19.900 --> 01:26:20.180 memory. 01:26:21.080 --> 01:26:23.860 And in that way, you can reduce the time that you actually need, so 01:26:23.860 --> 01:26:25.640 that's a practically efficient algorithm. 01:26:25.940 --> 01:26:29.980 You do as much as possible in main memory, and you reduce the number 01:26:29.980 --> 01:26:31.900 of disk accesses as much as possible. 01:26:32.080 --> 01:26:36.700 Details are in the book that I gave you, as one of the books in the 01:26:36.700 --> 01:26:37.340 reference list. 01:26:37.680 --> 01:26:39.540 That's it for today, thanks for your attention.