WEBVTT 00:00.920 --> 00:02.120 Okay, good morning. 00:02.280 --> 00:05.040 Welcome to another session of Algorithms for Internet Applications. 00:06.760 --> 00:09.860 Just five minutes delay today, because now we know how to deal with 00:09.860 --> 00:10.700 the technical problems. 00:13.220 --> 00:18.180 Okay, last time we looked at, again, last time at Internet Technology, 00:18.420 --> 00:22.360 we looked at some aspects of the TCP protocol. 00:23.220 --> 00:30.760 I showed you the header for TCP, right, that was it. 00:30.840 --> 00:37.900 I told you something about the logical connections about ports and 00:37.900 --> 00:43.700 sockets and all the different aspects of the header fields. 00:44.220 --> 00:48.520 We talked about the connection management and in particular talked 00:48.520 --> 00:52.340 about the flow control, which is one of the major tasks of TCP. 00:53.340 --> 00:55.940 And that was more or less it. 00:55.940 --> 01:04.220 I mentioned that TCP has problems if we look at specific applications 01:04.220 --> 01:07.880 where it is important to have a sustainable bandwidth and where it's 01:07.880 --> 01:14.380 not that essential if some of the datagrams are lost, because in audio 01:14.380 --> 01:20.240 transmission, for example, that would just be a small mistake in the 01:20.240 --> 01:26.340 audio signal, but it's important to maintain a certain frequency of 01:26.340 --> 01:26.700 data. 01:26.920 --> 01:30.240 And so for that, TCP is not that reasonable. 01:30.580 --> 01:35.560 So for that we have UDP and then I briefly showed you this slide on 01:35.560 --> 01:40.860 ATM, where the most essential point is that that is a protocol where 01:40.860 --> 01:45.840 the quality of service is an important aspect that we can have 01:45.840 --> 01:51.040 guaranteed quality there for different service classes. 01:52.580 --> 01:56.440 And that was the last slide of the last lecture. 01:57.280 --> 02:02.680 And so now I would like to come to the next chapter where we talk 02:02.680 --> 02:08.460 about something which is more using the Internet, using services on 02:08.460 --> 02:13.740 the Internet, and in particular one point or one topic which is very 02:13.740 --> 02:16.940 relevant for the Internet, as you all know, is dealing with 02:16.940 --> 02:17.440 information. 02:18.020 --> 02:22.680 Lots of things have evolved there and we know that there is, well, 02:22.880 --> 02:25.800 here I say there are currently about 300 million web searches per day. 02:25.920 --> 02:29.080 Probably this is much larger. 02:29.140 --> 02:32.560 Meanwhile, funny, all of a sudden I have a black pen. 02:33.040 --> 02:35.900 Don't know why the pen switched to black. 02:36.000 --> 02:41.640 I did not choose that. 02:41.880 --> 02:44.380 So I would take red again. 02:44.380 --> 02:51.180 Okay, so definitely there might be more than that, but it's just, the 02:51.180 --> 02:54.600 important point is that there are millions and millions of web 02:54.600 --> 02:56.940 searches per day, and so this is something where we really have to 02:56.940 --> 03:00.800 look at algorithms, how things like that actually are supported, how 03:00.800 --> 03:03.420 we can get information. 03:04.840 --> 03:08.300 Searching for information is definitely one of the most popular 03:08.300 --> 03:08.760 applications. 03:08.920 --> 03:09.540 We all do it. 03:09.580 --> 03:10.780 We all search for information. 03:10.780 --> 03:16.740 Very often we don't type in the address of a website, but type it in 03:16.740 --> 03:23.500 the search field and then just go to the appropriate location using a 03:23.500 --> 03:26.560 web service, a web search service. 03:27.260 --> 03:30.820 And so what we have to look at briefly is what search engines are 03:30.820 --> 03:34.580 about, how they operate, what some essential aspects of these search 03:34.580 --> 03:35.260 engines are. 03:35.560 --> 03:40.760 We should look at some basics of information retrieval, and it's 03:40.760 --> 03:45.240 always a problem that you have, there are different points in your 03:45.240 --> 03:50.620 courses that you are taking here in your programs of study where you 03:50.620 --> 03:54.860 might have already looked at topics related to this. 03:55.020 --> 04:00.020 So for example, if we talk about retrieving information, then we very 04:00.020 --> 04:04.020 often look for certain words in some documents. 04:04.260 --> 04:08.760 So if we would look for information retrieval and would like to get 04:08.760 --> 04:12.640 this document that I just presented to you, it means we would have to 04:12.640 --> 04:15.420 look for exactly the occurrence of that word in that document. 04:15.900 --> 04:19.120 So that means we would have to do some kind of pattern matching in 04:19.120 --> 04:19.880 text. 04:21.080 --> 04:24.080 And this would be something which would take a long time because we 04:24.080 --> 04:25.860 would have to look through all the different documents. 04:26.100 --> 04:27.080 Certainly we don't do that. 04:27.600 --> 04:31.300 And so what we usually do is, or not we, but the search engines do is 04:31.300 --> 04:36.980 they create a huge index where we can actually jump immediately to the 04:36.980 --> 04:37.920 relevant documents. 04:38.160 --> 04:41.920 That means we don't search in documents but search in catalogs and 04:41.920 --> 04:47.820 indexes where all the information is structurally available. 04:49.300 --> 04:53.720 Then the search engine definitely has to analyze search phrases. 04:54.200 --> 04:57.900 We formulate some queries in some way and they have to be interpreted 04:57.900 --> 04:58.880 in a reasonable way. 04:58.880 --> 05:00.820 We will look at that briefly. 05:01.020 --> 05:03.380 We have to measure the relevance of the retrieved documents. 05:03.380 --> 05:05.620 We don't want to get all kinds of documents. 05:06.380 --> 05:09.520 And we will look at that problem for a moment. 05:10.660 --> 05:17.140 And then there definitely is quite a large range of search engines 05:17.140 --> 05:17.820 available. 05:19.300 --> 05:23.040 And, well, most of you probably know at least one. 05:23.280 --> 05:25.520 Namely, you all know... 05:25.520 --> 05:27.980 Did I list it here? 05:28.040 --> 05:28.880 Yeah, I listed Google. 05:30.100 --> 05:33.720 So Google is one of many, many, many search engines. 05:34.380 --> 05:36.520 It certainly is one of the major ones. 05:37.080 --> 05:45.320 There is still quite a range of different search engines available. 05:47.160 --> 05:49.580 Some old list... 05:49.580 --> 05:53.740 Netfine, Excite, Google, certainly Hotbot, Infoseek, Lycos, 05:53.860 --> 05:57.940 Webcrawler, Yahoo, Metacrawler, and so on and so on. 05:58.120 --> 05:59.460 Lots of search engines. 05:59.660 --> 06:00.940 They all have different aspects. 06:01.900 --> 06:05.060 Somehow we use almost only one. 06:06.620 --> 06:08.960 But this is another problem. 06:11.200 --> 06:17.020 So at this website that I mentioned here... 06:17.020 --> 06:21.420 Actually, I think it's not important to go to the website now. 06:22.060 --> 06:28.280 At that website, you get all kinds of information on functionalities 06:28.280 --> 06:31.520 of search engines. 06:31.640 --> 06:39.580 And in particular, what you get there is information on how you 06:39.580 --> 06:42.420 actually should design your document. 06:42.640 --> 06:43.720 So if you write a document... 06:44.660 --> 06:46.800 This was supposed to be completely Google. 06:47.660 --> 06:52.100 So if this is a document, you have several documents and you have 06:52.100 --> 06:55.700 certain important information in there, and you would like to make 06:55.700 --> 07:01.440 sure that if you put a query to Google, then the result should be a 07:01.440 --> 07:06.740 list and the top documents should be exactly your documents. 07:07.610 --> 07:14.500 Whenever it is information that was looked for which is relevant for 07:14.500 --> 07:15.720 your documents. 07:16.400 --> 07:22.260 So if you are designing the webpages of a certain company, or of your 07:22.260 --> 07:26.760 own company, or you have a certain interest that your information is 07:26.760 --> 07:32.100 available to the relevant users as a response to a query, you must 07:32.100 --> 07:36.240 make sure that your website is listed as the top ranked. 07:37.140 --> 07:41.020 And so in order to know how to do that, you have to know how actually 07:41.020 --> 07:47.600 the search engines classify webpages, websites, documents, how they 07:47.600 --> 07:52.340 are ranked, and how you can make sure that you don't end up somewhere 07:52.340 --> 07:56.240 down there where you never look at, but that you can jump up to some 07:56.240 --> 07:57.200 places over there. 07:57.720 --> 08:03.400 This has to be done in a way that is justified, and not considered to 08:03.400 --> 08:10.140 be website or some kind of spamming, that you have unjustified 08:10.640 --> 08:14.240 information in there, and in that way try to get to the top ranked. 08:14.340 --> 08:19.440 We know that if we look at the webpage that we get as a result to a 08:19.440 --> 08:25.940 query, there are always some elements at the top listing which are 08:25.940 --> 08:26.800 paid entries. 08:27.400 --> 08:29.940 This is something which has not been there in the beginning of the 08:29.940 --> 08:33.180 search engines, but certainly popped up because the companies would 08:33.180 --> 08:40.600 like to get to make money, and so they get payment from companies who 08:40.600 --> 08:45.260 would like to be always listed as the top entries, and if you look 08:45.260 --> 08:50.040 more closely you will notice that certain sources of information are 08:50.040 --> 08:54.180 always in the top rank, at least with Google, like for example 08:54.180 --> 08:58.860 Wikipedia is always in the top ranks because it's owned by Google, and 08:58.860 --> 09:01.300 so they always make sure that their information is on the top. 09:02.580 --> 09:09.700 So, this is all stuff about when we talk about searching for 09:09.700 --> 09:14.320 information we have to know how you can actually locate information, 09:14.520 --> 09:17.140 and then how you can present that information. 09:17.860 --> 09:21.220 And so you are shaking your head in the background there. 09:21.820 --> 09:22.380 What's wrong? 09:25.860 --> 09:27.720 As far as I know, yes. 09:31.820 --> 09:36.940 That's what I heard some time ago, that they are very closely related 09:36.940 --> 09:37.340 to Google. 09:39.360 --> 09:44.160 So it has not been founded by Google, but they are very closely 09:44.160 --> 09:46.380 connected, at least very closely connected to Google. 09:48.740 --> 09:52.540 Okay, so Google owns many, many different services. 09:53.100 --> 09:53.780 They are very powerful. 09:54.920 --> 09:57.280 And they really provide perfect services. 10:00.000 --> 10:05.840 What I wanted to tell you is that at this website, which changed its 10:05.840 --> 10:11.100 appearance significantly in recent years, so yesterday I just wanted 10:11.100 --> 10:14.560 to briefly update the information I have in my slides here on this 10:14.560 --> 10:18.060 topic, and I noticed that all the nice sites where I had those 10:18.060 --> 10:20.640 informations have disappeared somewhere. 10:20.800 --> 10:21.640 I don't know why. 10:22.020 --> 10:27.320 It's more difficult to get exact information on certain web search 10:27.320 --> 10:27.960 statistics. 10:28.800 --> 10:30.820 Then I noticed a few things again. 10:30.980 --> 10:38.200 So this URL that I listed here now has a list of tips on links to 10:38.200 --> 10:44.500 information where you get all kinds of things about search engines, 10:44.680 --> 10:47.280 facts and funds, status reports, resources, and so on. 10:47.400 --> 10:52.840 And here the point of view of this website is always information for 10:52.840 --> 10:56.780 the designer of websites, what they should consider when they design 10:56.780 --> 11:02.240 websites in order to make sure that they are adequately listed in 11:02.240 --> 11:04.660 search engine rankings. 11:05.100 --> 11:06.500 So this is an important thing. 11:07.060 --> 11:11.320 It's not sufficient to just produce information and make sure it can 11:11.320 --> 11:15.840 be found, but you have to make sure that it is presented in the right 11:15.840 --> 11:19.240 way, that it's made available and visible to the persons that you 11:19.240 --> 11:21.540 think are the relevant target audience. 11:22.240 --> 11:28.640 So this is what we will at least look at to some extent. 11:29.140 --> 11:34.040 I cannot present you all the different algorithms that are around 11:34.040 --> 11:37.520 there, but we have to briefly classify what's going on there. 11:37.960 --> 11:41.440 So first of all, what is it that we talk about when we talk about 11:41.440 --> 11:42.200 search engines? 11:42.560 --> 11:43.900 Most of you use them. 11:43.900 --> 11:45.360 You know what they actually do. 11:45.800 --> 11:49.620 They constantly visit websites on the internet in order to create 11:49.620 --> 11:50.940 catalogs of webpages. 11:51.360 --> 11:58.160 So the search engines are usually created automatically by some 11:58.160 --> 12:06.140 program which is visiting the web and so this is done without human 12:06.140 --> 12:06.760 interference. 12:07.160 --> 12:10.380 You don't have to manually look at the results and then put it in some 12:10.380 --> 12:14.220 catalog, but the search engines do that automatically. 12:14.840 --> 12:18.480 Then there are directories, not catalogs, but directories. 12:18.620 --> 12:21.260 This is just justification. 12:21.820 --> 12:27.880 Directories are actually manually created catalogs of webpages. 12:28.120 --> 12:32.180 That means somebody has looked at those resources that are listed 12:32.180 --> 12:34.980 there and classified them and made some quality check. 12:35.680 --> 12:42.700 One of the major original examples is Yahoo, where Yahoo nowadays is 12:42.700 --> 12:46.720 not just a directory but also a directory extended with catalogs. 12:46.800 --> 12:50.560 That means it is manually created content plus additional content. 12:50.940 --> 12:56.600 Another example of that was WebDE. 12:58.920 --> 13:04.220 So this was, they were organizing the internet, they said, so they had 13:06.020 --> 13:10.980 classified information, organized information and quality checks on 13:10.980 --> 13:15.320 the links that are actually available there and as a provider of 13:15.320 --> 13:19.660 information you can submit information and submit websites to be 13:19.660 --> 13:21.520 listed in these directories. 13:21.640 --> 13:25.200 So this is something like an official catalog of information that is 13:25.200 --> 13:27.040 in some way quality checked. 13:27.360 --> 13:33.340 Whereas the catalogs of search engines are not quality checked, just 13:33.340 --> 13:39.060 all the information you have or that you get access to is actually 13:39.060 --> 13:41.540 listed in those catalogs. 13:42.000 --> 13:44.920 And then certainly there are the hybrid search engines which combine 13:44.920 --> 13:48.920 both, where Yahoo again is a good example because they have search 13:48.920 --> 13:53.240 engines which automatically create catalogs but also have some more 13:53.240 --> 13:55.740 organized and quality checked directories. 13:56.540 --> 13:59.100 So how do these search engines work? 13:59.100 --> 14:05.320 They have, as I said, they visit the major, or they visit the websites 14:05.320 --> 14:10.200 the pages on all the websites regularly this is done by programs 14:10.200 --> 14:15.020 called spiders or crawlers, that means we have here the internet and 14:15.020 --> 14:20.760 now you could think, well this program is actually, this spider is 14:20.760 --> 14:26.700 actually visiting all these different nodes in this building or in 14:26.700 --> 14:31.480 this web of information and so you could think as if the program would 14:31.480 --> 14:33.020 visit all these different nodes. 14:33.300 --> 14:36.360 One could do it that way, one could use mobile code for that, but we 14:36.360 --> 14:37.660 know we don't have to do that. 14:37.980 --> 14:47.180 We can just access all the websites and by just entering all the 14:47.180 --> 14:53.160 different, or checking all the different URLs for the website or the 14:53.160 --> 15:00.120 addresses but it's obvious for every check of a website we have to 15:00.120 --> 15:06.780 execute the HTTP protocol and access or communicate with the web 15:06.780 --> 15:09.820 server at the site where we would like to get some information. 15:10.300 --> 15:14.340 So we have to visit the page, that means retrieve the information from 15:14.340 --> 15:14.660 there. 15:15.080 --> 15:19.600 You have to read the page and then in the page you might follow other 15:19.600 --> 15:24.980 links and then these links to these other pages may be within that 15:24.980 --> 15:28.540 site or other sites will also be followed in that way. 15:29.640 --> 15:33.100 In this way these spiders are crawling the web because they just 15:33.100 --> 15:39.080 follow all the links that they can actually access and in this way get 15:39.080 --> 15:40.280 more and more information. 15:40.980 --> 15:44.460 And this is just one point that you have to discover information on 15:44.460 --> 15:47.640 the web and then you have to make sure that the information that you 15:47.640 --> 15:52.200 list in your index or in your catalog actually is up to date. 15:52.320 --> 15:58.420 So you have to revisit the sites on a regular basis every month or two 15:58.420 --> 16:01.820 or maybe every three weeks, every five weeks, every eight weeks. 16:02.320 --> 16:07.780 This revisiting interval will depend on the frequency of change that 16:07.780 --> 16:08.960 you actually observe. 16:09.300 --> 16:13.780 So you are just visiting a certain web page and this is the time you 16:13.780 --> 16:15.500 visit that at regular intervals. 16:15.620 --> 16:18.740 If there is no change then you increase the intervals. 16:19.320 --> 16:22.620 If there are more changes then you have to decrease the intervals and 16:22.620 --> 16:28.240 visit it more often in order to have always updated current contents 16:28.240 --> 16:28.500 there. 16:29.560 --> 16:34.740 So we know how many websites there are, quite a few. 16:35.760 --> 16:43.080 So Google for example some five, six years ago had something like 16:43.080 --> 16:55.880 eight billions that means ten to the nine websites in its catalog and 16:55.880 --> 16:59.420 just like we will come back to that probably a bit later but to just 16:59.420 --> 17:03.540 make a simple calculation what that would mean if you have to revisit 17:03.540 --> 17:08.980 eight billion websites every day or every three weeks. 17:09.220 --> 17:10.780 Just every three weeks. 17:11.040 --> 17:14.460 But that means for the number of websites you have to visit per day 17:14.460 --> 17:18.340 and you know how long it takes to visit a server. 17:18.480 --> 17:22.540 If you look at the time it takes to execute a ping operation. 17:23.260 --> 17:28.920 A ping operation like if you just want to go from one server to the 17:28.920 --> 17:40.100 other just communicate you just have to you are counting the people 17:40.100 --> 17:41.000 here what are you doing? 17:41.560 --> 17:41.680 No? 17:43.940 --> 17:51.220 Okay, so it's a huge number of websites that you have to visit and you 17:51.220 --> 17:55.680 know how long it takes to actually visit an individual site how long 17:55.680 --> 18:01.340 it takes to access a webpage and then you can simply calculate how 18:01.340 --> 18:06.260 much time you have to spend to visit all these websites or how much 18:06.260 --> 18:11.020 computing power you have to provide in order to support something like 18:11.020 --> 18:17.920 eight billion websites that are always or that always have to be up to 18:17.920 --> 18:22.860 date or the content should not be older than at most three weeks. 18:23.740 --> 18:29.380 You always expect that it is the current information and then how much 18:29.380 --> 18:33.080 computing power you would have to provide in order to be able to do 18:33.080 --> 18:33.240 that. 18:33.300 --> 18:35.040 I don't want to go into details here. 18:35.360 --> 18:35.980 I'll do that later. 18:37.660 --> 18:39.000 So, that's the spider. 18:39.300 --> 18:44.680 The spider is just checking the information and then the index is 18:44.680 --> 18:50.140 built this catalog and we know what an index is if we have a book at 18:50.140 --> 18:57.800 the end we have some listing and we have all kinds of words like some 18:57.800 --> 19:01.840 word like web or something and then we have here a listing of all the 19:01.840 --> 19:04.400 locations where this word actually is occurring. 19:04.580 --> 19:08.940 That essentially is an index as you know it from every textbook where 19:08.940 --> 19:13.520 you have an index at the end in order to retrieve very quickly the 19:13.520 --> 19:19.040 relevant locations where a certain word that you are interested in is 19:19.040 --> 19:19.800 actually occurring. 19:20.380 --> 19:28.080 This is what has to be built and if you have 8 billion web pages you 19:28.080 --> 19:32.860 have many, many words that might occur there. 19:34.120 --> 19:40.880 Certainly the number of words that are currently looked at is not that 19:40.880 --> 19:41.420 large. 19:41.720 --> 19:45.780 That's by the way an interesting information provided on the Search 19:45.780 --> 19:53.500 Engine Watch website you can look up the most frequent search terms of 19:53.500 --> 19:58.400 today, yesterday or the last week or things like that and in that way 19:58.400 --> 20:01.440 see what are the most common search queries. 20:02.040 --> 20:07.280 So you have to make sure that search queries are supported, are 20:07.280 --> 20:12.000 executed very fast and so you need efficient data structures and 20:12.000 --> 20:14.080 access methods for such an index. 20:14.220 --> 20:22.400 To build up an index is a very complex and challenging task and it 20:22.400 --> 20:26.780 needs a lot of computing power to actually execute all the queries. 20:27.360 --> 20:30.540 And this is done, this executing the queries is done by the Search 20:30.540 --> 20:33.780 Engine software which has to analyze your query. 20:33.940 --> 20:37.380 If it's just one word it's simple but if you have a sequence of words 20:37.380 --> 20:43.380 and maybe even complex search query then this has to be analyzed 20:43.380 --> 20:45.640 adequately this is the smallest task. 20:46.080 --> 20:50.760 Then you have to search the index for documents matching the query the 20:50.760 --> 20:55.820 time for that depends on the efficiency of your data structures there 20:55.820 --> 21:01.620 and then the software has to rank the matching documents in order of 21:01.620 --> 21:01.980 relevance. 21:02.120 --> 21:07.720 So you have to know something about relevance of the document for a 21:07.720 --> 21:08.420 certain query. 21:09.740 --> 21:16.060 Now let us briefly look at what kind of measurements we would have to 21:16.060 --> 21:18.620 talk about the quality of information retrieval. 21:19.280 --> 21:24.660 So information retrieval in general which is much older than all the 21:24.660 --> 21:25.580 search engine 21:30.480 --> 21:34.780 activities information retrieval is a very old subject and there are 21:34.780 --> 21:42.940 two standard measures which are assessing the quality of information 21:42.940 --> 21:43.560 retrieval. 21:43.820 --> 21:46.020 One is called recall and the other is called precision. 21:46.260 --> 21:51.880 So recall means assume you have a certain database of documents so 21:51.880 --> 21:53.640 this is all the documents you have. 21:53.760 --> 21:55.600 Now you ask for a certain document. 21:55.740 --> 22:01.100 You ask for documents containing let's say words about the Karlsruhe 22:01.100 --> 22:02.160 Institute of Technology. 22:03.380 --> 22:07.720 Some documents will contain information on that some won't contain 22:07.720 --> 22:08.400 that information. 22:08.560 --> 22:15.340 So you can split up your database into your collection of documents 22:15.340 --> 22:19.040 into at least two subsets. 22:19.220 --> 22:22.280 One which is irrelevant, one which is containing the relevant 22:22.280 --> 22:22.840 documents. 22:23.480 --> 22:27.460 Now this assumes that we can exactly say this document is relevant 22:27.460 --> 22:28.800 that one is not relevant. 22:29.340 --> 22:34.260 Very often we don't have such a 0-1 decision but we have a degree of 22:34.260 --> 22:34.780 relevance. 22:34.960 --> 22:39.640 But here I simplify that and assume that we say this is relevant and 22:39.640 --> 22:40.460 that is not relevant. 22:41.200 --> 22:45.800 And now you get as a result of your query you get a certain response 22:45.800 --> 22:47.580 you get a certain number of documents. 22:48.600 --> 22:53.940 And the quality of that query of that response to a query can be 22:53.940 --> 22:55.580 measured in two ways. 22:56.200 --> 23:01.160 One is well, you retrieved a certain number of documents and some of 23:01.160 --> 23:01.840 them are relevant. 23:03.400 --> 23:08.280 And you know in your database you may have more relevant documents. 23:08.460 --> 23:12.400 So you look at how many of those relevant documents are actually 23:12.400 --> 23:12.920 recorded. 23:13.660 --> 23:16.200 This is what this is about. 23:16.780 --> 23:22.620 The number of relevant retrieved documents in relation to all the 23:22.620 --> 23:23.440 relevant documents. 23:23.580 --> 23:27.880 How many of those relevant documents did you actually get in the 23:27.880 --> 23:28.920 response to your query? 23:30.860 --> 23:35.420 Another point is how precise is the response to your query? 23:36.580 --> 23:42.180 How precisely did your search engine actually check whether the 23:42.180 --> 23:44.780 documents are relevant or not? 23:45.320 --> 23:49.100 And so what you now look at is you have a certain number of retrieved 23:49.100 --> 23:49.600 documents. 23:49.740 --> 23:52.580 Here this part of your documents is relevant. 23:53.120 --> 23:56.180 But you may also get other documents which are not relevant. 23:57.500 --> 24:04.880 And so you look at the number of or the fraction of relevant retrieved 24:04.880 --> 24:10.560 documents with respect to the number of retrieved documents that you 24:10.560 --> 24:10.760 got. 24:10.960 --> 24:17.440 So here you look at how much irrelevant documents there actually are 24:17.440 --> 24:25.740 or what is the quality of the response with respect to the percentage 24:25.740 --> 24:26.980 of relevant documents. 24:27.520 --> 24:32.880 And certainly this is important to look at. 24:33.600 --> 24:37.500 And the problem is that there can be different strategies. 24:37.760 --> 24:41.200 You could say, well I would like to provide a service which is always 24:41.200 --> 24:41.620 relevant. 24:42.140 --> 24:47.900 So I only return very few documents where I'm certain these documents 24:47.900 --> 24:49.120 are relevant. 24:49.980 --> 24:51.960 But then the recall will be small. 24:52.160 --> 24:56.980 If there is a huge number of documents which might be relevant then if 24:56.980 --> 25:01.340 you are lazy you just return one document which is actually 25:04.920 --> 25:09.560 relevant and then you have a very precise response to the query 25:09.560 --> 25:13.560 because everything you return is relevant. 25:14.620 --> 25:21.240 But if you say, okay, I would like to have also a high recall, you 25:21.240 --> 25:24.120 could just return all the documents. 25:24.800 --> 25:28.660 Then you have a very high recall because you have provided all the 25:28.660 --> 25:32.060 relevant documents but it's not the task of the user to actually 25:32.060 --> 25:36.820 search through that huge number of documents to find out which ones 25:36.820 --> 25:38.360 are relevant and which ones are not. 25:39.000 --> 25:45.720 You can have a high recall but a very small precision and the task or 25:45.720 --> 25:48.920 challenge is to have high recall and high precision. 25:50.300 --> 25:55.460 Now since the decision on whether a document is relevant or not is not 25:55.460 --> 26:03.100 a simple 0-1 decision you have to look at that more closely. 26:03.160 --> 26:05.200 We will do that a bit later. 26:06.780 --> 26:11.520 You can easily achieve high recall or high precision but if you look 26:11.520 --> 26:18.780 at both criteria then you are closer to getting something which is 26:18.780 --> 26:22.560 measuring the real quality of your search engine. 26:23.400 --> 26:27.920 Now let's briefly look at this notion of relevance. 26:28.480 --> 26:31.700 When would we say that a document is relevant for a query? 26:32.260 --> 26:38.400 So if we get a link to a document and we look at that document then we 26:38.400 --> 26:41.920 have looked for a certain term a search term and then we certainly 26:41.920 --> 26:46.900 assume that there should be a match of that term. 26:47.040 --> 26:51.080 So this term that we looked at should appear in the document. 26:52.480 --> 26:55.880 And certainly it's nicer if it appears many times. 26:56.760 --> 26:59.160 So a number of query terms with matches. 26:59.500 --> 27:07.020 Or maybe you have a list of terms, not just one term but some list of 27:07.020 --> 27:12.320 k query terms and certainly you would like to see as many as possible 27:12.320 --> 27:17.240 of those terms in your documents that are presented to you as being 27:17.240 --> 27:17.620 relevant. 27:18.300 --> 27:21.740 So the number of query terms with matches certainly is an important 27:21.740 --> 27:25.940 point but then also the number of matches if you have one word which 27:25.940 --> 27:30.020 is appearing several times the document probably will be more relevant 27:30.020 --> 27:32.940 than a document where this term appears only once. 27:34.100 --> 27:39.680 Another point is, where do we actually notice those terms? 27:41.100 --> 27:46.780 If in the first line of the document we see one or several of these 27:46.780 --> 27:48.400 query terms, we are happy. 27:48.520 --> 27:50.100 It must be a very relevant document. 27:50.960 --> 27:54.120 This is an indication of relevance for a term. 27:54.200 --> 28:01.440 If it appears in the first lines of a document it should be more 28:02.380 --> 28:06.280 relevant than terms which just appear somewhere in the end. 28:08.840 --> 28:13.440 Or, you could say, if at the end you have the conclusion of a paper or 28:13.440 --> 28:17.320 something so maybe the terms appearing there could again be relevant 28:17.320 --> 28:21.900 but something which is just in the middle somewhere would not be that 28:21.900 --> 28:22.220 relevant. 28:22.340 --> 28:25.580 So these are indications of relevance. 28:25.720 --> 28:29.700 The location, the number of matches, the number of query terms which 28:29.700 --> 28:39.320 actually match and then certainly the quality of the matches if you 28:39.320 --> 28:47.240 look for a certain term like match and you also get a link where you 28:47.240 --> 28:52.740 have a word like this, well you would not really think that that is 28:52.740 --> 28:53.060 relevant. 28:53.640 --> 28:57.080 But it's just very close to the term that you looked for. 28:57.180 --> 29:01.740 Just one misspelled letter there. 29:01.920 --> 29:05.380 So you have one additional letter very close to the term you actually 29:05.380 --> 29:10.140 looked for and sometimes you are very interested in actually getting 29:10.140 --> 29:14.580 hits for words that are very similar to the word that you are actually 29:14.580 --> 29:15.280 interested in. 29:16.100 --> 29:21.860 And so the question whether you are only looking for complete matches 29:21.860 --> 29:27.920 or also for partial matches is important because if you allow for 29:27.920 --> 29:33.060 looking for partial matches then you get more documents back. 29:33.820 --> 29:37.860 And maybe you have not completely specified the term that you are 29:37.860 --> 29:41.020 actually interested in and that way you get the really relevant 29:41.020 --> 29:41.540 documents. 29:42.720 --> 29:46.660 Then you might have misspelled your query. 29:47.140 --> 29:52.380 You notice when you put queries to Google and you misspell the search 29:52.380 --> 29:58.580 term usually Google suggests certain other words which might be the 29:58.580 --> 30:00.640 intended query term. 30:01.020 --> 30:04.400 Then they ask, isn't that the actual query term that you looked for? 30:04.400 --> 30:08.360 So this is something looking or considering misspellings. 30:08.680 --> 30:14.360 This all has to be done by the search engine software. 30:14.860 --> 30:19.440 Then there may be explicit information on relevance. 30:21.380 --> 30:25.440 Explicit information, direct information on relevance may be that you 30:25.440 --> 30:29.520 have a certain header of your document which is not visible directly 30:29.520 --> 30:34.560 in the web browser but is information contained in the file. 30:34.680 --> 30:37.580 You know that you have meta tags in your documents and you can 30:37.580 --> 30:41.840 explicitly specify their keywords and things like that and in that way 30:41.840 --> 30:49.940 enter certain keywords that are important for search engines to 30:49.940 --> 30:57.500 evaluate such that queries will also be linked to that document even 30:57.500 --> 31:00.960 if a certain term does not appear directly in that document. 31:02.080 --> 31:08.640 So this might be important if, for example, you are having a certain 31:08.640 --> 31:13.480 term and this term is also known under different names. 31:13.580 --> 31:17.420 You have synonyms for that and you could just put certain synonyms for 31:17.420 --> 31:23.140 important words into your meta tags and so in this way you could list 31:23.140 --> 31:29.640 here many different terms and in that way enhance the probability that 31:29.640 --> 31:34.500 your document actually will get listed as the result of a query. 31:34.700 --> 31:39.540 So this explicit information in the meta tags is important and 31:39.540 --> 31:44.780 obviously the knowledge of the method of evaluation will influence the 31:44.780 --> 31:47.340 way you present your document. 31:48.560 --> 31:53.740 And also these statements on relevance are not unique. 31:53.920 --> 31:55.540 They depend on the method of evaluation. 31:56.020 --> 32:02.100 How you actually combine all these different aspects into some rank. 32:02.520 --> 32:08.440 There are others I did not mention all the things but I should at 32:08.440 --> 32:11.100 least indicate it briefly. 32:11.760 --> 32:17.000 If you have a document and there are many more documents which are 32:17.000 --> 32:23.020 linking to that page, then usually this is also considered to be an 32:23.020 --> 32:24.040 indication of relevance. 32:24.340 --> 32:29.900 This actually is the major indicator of relevance for Google that says 32:29.900 --> 32:36.680 well, if a page is actually very popular in the number of links that 32:36.680 --> 32:40.660 are pointing to that page, then this must be a very relevant page. 32:41.400 --> 32:43.980 And if you know that, you know how to set up your webpage. 32:43.980 --> 32:46.500 Or how to create links to your page. 32:47.420 --> 32:51.540 There are services available creating links to your page such that you 32:51.540 --> 32:53.860 get a high popularity index. 32:54.800 --> 32:57.720 But this certainly has to be justified. 32:58.480 --> 33:04.000 So this is always this tradeoff between or this problem that you would 33:04.000 --> 33:08.820 like to get you know how ranking is done, so you know what you have to 33:08.820 --> 33:13.440 do in order to get to a higher location but it has to be justified, it 33:13.440 --> 33:14.600 has to be an adequate ranking. 33:14.780 --> 33:19.040 And this has to do with marketing we are not talking about marketing, 33:19.200 --> 33:22.760 we are talking about algorithms but certainly in marketing people also 33:25.580 --> 33:26.500 use algorithms. 33:27.720 --> 33:31.420 Another point which I would like to briefly mention I just told you 33:31.420 --> 33:34.980 about the task of the spiders and so on, they visit all the webpages. 33:35.740 --> 33:40.620 Now assume you are setting up a very modern webpage or website and all 33:40.620 --> 33:42.780 you have there are dynamic contents. 33:42.960 --> 33:48.260 You have certain services which will create contents depending on the 33:48.260 --> 33:51.500 personal choices of the person who is visiting that webpage. 33:52.620 --> 33:53.880 That is a problem. 33:54.160 --> 33:59.640 These webpages will never be indexed by a search engine because an 33:59.640 --> 34:03.240 automatic crawler can only notice, oh there are certain services, 34:03.580 --> 34:10.280 certain scripts that actually can access information but since there 34:10.280 --> 34:14.760 is no person behind that, these contents which can be dynamically 34:14.760 --> 34:19.920 adjusted will never be indexed, it will never enter the search engines 34:19.920 --> 34:22.500 or the catalogs and the indexes and so on. 34:23.160 --> 34:28.020 And so if you put all your information in a very fancy way in dynamic 34:28.020 --> 34:31.800 or using dynamic techniques for presenting your content in your 34:31.800 --> 34:35.860 website, this information will never be available to other places. 34:36.420 --> 34:42.080 So this is, you always have to add extra information either in meta 34:42.080 --> 34:48.260 tags or on static webpages which can actually be listed or checked by 34:49.400 --> 34:54.840 search engines, by the spiders and then indexed or entered into these 34:55.760 --> 34:56.520 catalogs. 34:57.040 --> 35:03.480 Okay, so this is a lot of extra information on this slide where I just 35:03.480 --> 35:07.700 wanted to tell you what actually makes a document relevant for a 35:07.700 --> 35:07.960 query. 35:09.120 --> 35:13.220 The next question is we'll come back to the notion of relevance a bit 35:13.220 --> 35:13.440 later. 35:14.040 --> 35:14.800 What is a query? 35:15.300 --> 35:18.260 When we talk about queries so what is actually in there? 35:18.720 --> 35:23.740 There are many different ways of actually stating a query. 35:24.640 --> 35:33.420 You can actually put in some natural language or some phrase in normal 35:33.420 --> 35:36.100 language and this will be interpreted. 35:36.280 --> 35:42.580 But you could also just enter a few terms and so a query normally 35:42.580 --> 35:46.820 consists of something like, some people have analyzed all the queries, 35:47.280 --> 35:49.180 2.35 terms in a query. 35:49.600 --> 35:52.320 Don't know how many terms you put in a query when you search for 35:52.320 --> 35:52.680 something. 35:53.580 --> 35:56.980 I think this may increase slightly. 35:57.400 --> 36:01.280 If you type in something again at Google, you get suggestions what you 36:01.280 --> 36:05.760 might actually be interested in and then you get, well, certain 36:05.760 --> 36:11.260 numbers of terms maybe two or three but usually not more. 36:11.960 --> 36:14.960 So 2.35 actually is quite a large number. 36:15.320 --> 36:20.280 I don't know what your habit is when you ask something in a query. 36:20.680 --> 36:25.460 So, let's assume we want to search for documents containing 36:25.460 --> 36:27.160 Universität Karlsruhe. 36:27.980 --> 36:32.500 Nobody knows what that is, but maybe there's still something around 36:32.500 --> 36:35.240 there or the name Algorithmus. 36:35.300 --> 36:36.320 How could we do that? 36:37.280 --> 36:41.700 So, now we have to decide what we actually want to do. 36:41.800 --> 36:45.760 We want to search for all documents containing these words. 36:45.760 --> 36:53.900 First of all, we have to notice a document here is essentially just a 36:53.900 --> 36:55.280 sequence of symbols. 36:56.020 --> 37:01.960 So we could have here a very long sequence of symbols with a sequence 37:01.960 --> 37:03.420 of symbols over some alphabet. 37:03.940 --> 37:10.100 We know how to talk about languages, about words and so on. 37:10.300 --> 37:16.580 So, we could simply formalize that and say there's a match for a query 37:16.580 --> 37:22.260 for example the query A that we have here, Universität Karlsruhe, if 37:22.260 --> 37:26.320 we have a document D which is an element of this set. 37:26.400 --> 37:27.240 What is that set? 37:27.700 --> 37:34.120 It is a set of words starting with any symbol from this alphabet sigma 37:34.120 --> 37:40.880 then having the letters Universität blank Karlsruhe and then again 37:40.880 --> 37:42.680 some sequence of letters. 37:43.280 --> 37:51.720 That means this term here occurs somewhere in some document, in some 37:51.720 --> 37:52.140 word. 37:53.260 --> 37:58.640 Now this should remind you of something we have looked at we have 37:58.640 --> 38:02.720 looked at if you are students of business engineering or if you are 38:02.720 --> 38:07.440 students of other programs then you have looked at other courses So 38:07.440 --> 38:08.860 this is just regular set. 38:09.160 --> 38:14.340 Regular set we know we can analyze using finite automata so if we 38:14.340 --> 38:19.960 would like to execute such a query we could just run or let some 38:19.960 --> 38:24.820 finite automata, some state machine actually analyze all the documents 38:24.820 --> 38:29.740 and find out which documents are acceptable to that finite state 38:29.740 --> 38:30.040 machine. 38:31.100 --> 38:35.260 Then we have actually, this actually is the algorithm to build this 38:35.260 --> 38:42.020 finite state machine which will find out whether a document contains a 38:42.020 --> 38:44.540 certain pattern. 38:45.260 --> 38:48.400 This is one approach that you could look at. 38:48.500 --> 38:55.460 So here the query corresponds to a regular expression we can actually 38:55.460 --> 38:59.820 find out whether there is a match if we just execute this finite 38:59.820 --> 39:04.520 automaton it's not just any finite automaton we have to do that in a 39:04.520 --> 39:09.440 reasonable way but definitely we know what kind of system that is that 39:09.440 --> 39:10.200 we have to look at. 39:12.580 --> 39:17.960 This certainly means every query corresponds to a finite automaton 39:17.960 --> 39:23.600 that means for every query before we can execute that on a set of 39:23.600 --> 39:28.800 documents we have to generate that automaton Now this can be done 39:28.800 --> 39:34.440 easily in an automated way and we will see how we can actually define 39:34.440 --> 39:40.020 or design very efficient algorithms for pattern matching in documents. 39:40.740 --> 39:48.260 The other assumption is that your document is represented within an 39:48.260 --> 39:52.920 index that means you have a data structure which allows for efficient 39:52.920 --> 39:57.180 retrieval of all the relevant words of a document and so there you 39:57.180 --> 40:03.060 would not analyze the document, you would just go into the index 40:03.060 --> 40:08.320 search for the words for University of Karlsruhe and then follow the 40:08.320 --> 40:13.180 link that is showing you all the different documents but this is 40:13.180 --> 40:13.960 actually occurring. 40:14.320 --> 40:21.040 But this certainly means you have to analyze the documents before we 40:21.040 --> 40:24.420 actually execute the queries and this is what I mentioned the search 40:24.420 --> 40:28.040 engines actually do, that they look at all the different websites and 40:28.040 --> 40:32.740 analyze the websites but certainly for that they have to find out what 40:32.740 --> 40:37.460 is actually the list of relevant words that might be looked at later 40:37.460 --> 40:43.080 on by some query so if you are interested in full text search you 40:43.080 --> 40:48.940 actually might have to go through all those documents and you know if 40:48.940 --> 40:54.540 you for example search through all the email messages that you have on 40:54.540 --> 40:55.100 your computer. 40:55.420 --> 40:59.800 If you don't have an index it takes quite some time because the 40:59.800 --> 41:06.100 standard procedure would be to perform it following assumption 1 that 41:06.100 --> 41:11.460 you have actually to build or to execute a query on all the email 41:11.460 --> 41:14.540 messages that you have and search for the occurrence of certain words 41:14.540 --> 41:22.960 if you have an index on your database of email messages then it's much 41:22.960 --> 41:27.640 faster you just have to access the index but you have to build that 41:27.640 --> 41:32.880 index and this takes quite a long time so this is just following the 41:32.880 --> 41:38.420 different approaches to searching for information and documents we 41:38.420 --> 41:42.880 will look at both ways of analyzing documents I will present to you 41:42.880 --> 41:47.580 ways of actually looking for patterns in documents, so full-text 41:47.580 --> 41:47.980 search. 41:48.540 --> 41:53.000 We will also briefly look at how we can actually build up a search 41:53.000 --> 41:56.380 structure for the words within a document. 41:58.000 --> 42:00.780 Now you remember what a regular expression is? 42:01.740 --> 42:06.480 You know that this is the standard notion. 42:06.480 --> 42:11.320 We have certain symbols that are regular expressions. 42:11.780 --> 42:16.660 So the symbol for the empty set is a regular expression, or the 42:16.660 --> 42:19.480 elements of the alphabet are regular expressions. 42:19.680 --> 42:23.260 And if you have two regular expressions, then you know that you can 42:23.260 --> 42:28.340 combine them with plus, dot, and the star. 42:28.580 --> 42:33.300 So sum, product, and iteration are the three operations that we can 42:33.300 --> 42:34.080 form there. 42:34.080 --> 42:39.720 Whereas these are essentially only sequences of some letters or some 42:39.720 --> 42:44.800 symbols, and then we name them regular expressions, and we have to 42:44.800 --> 42:46.320 interpret them adequately. 42:46.860 --> 42:47.600 You know all that. 42:47.940 --> 42:53.280 Now certainly we don't want... if you write a query, sometimes you 42:53.280 --> 42:58.180 have these notation available and you can write something, for 42:58.180 --> 43:04.140 example, write a question mark after a certain term, which means it 43:04.140 --> 43:08.300 might occur, but it not necessarily occurs there. 43:08.980 --> 43:13.400 Or you say, you can have the empty word there, or you can say, okay, I 43:13.400 --> 43:18.120 just want to specify that some of the letters in between, for example, 43:18.380 --> 43:20.340 A to F should appear there. 43:21.020 --> 43:25.620 Then you can specify it in this way, which is simpler than specifying 43:25.620 --> 43:27.980 it as a sum of all the individual symbols. 43:28.680 --> 43:32.100 Or you could say, well, I would like to look at all the documents 43:32.100 --> 43:35.060 where a certain term appears at most k times. 43:35.640 --> 43:38.200 This would be something like this. 43:38.640 --> 43:41.840 Or you say, I would like to look for documents where a certain term 43:41.840 --> 43:46.280 appears at least k times, and you could specify it like that, which 43:46.280 --> 43:51.360 would be much more difficult to specify if you would do it in a 43:51.360 --> 43:51.840 different way. 43:51.840 --> 43:57.720 So this is just extensions, and you know that in many queries, you can 43:57.720 --> 44:02.020 actually specify search terms like that using this notation from 44:02.020 --> 44:04.580 regular expressions. 44:05.180 --> 44:09.080 So we could, for example, I don't assume that you would do that 44:09.080 --> 44:14.040 actually, but one could specify a search where we look for all kinds 44:14.040 --> 44:18.840 of variants of the word algorithmos, and this should occur at least 44:18.840 --> 44:22.860 five times, in the following way that it should start with any symbol 44:22.860 --> 44:28.140 from sigma, it might be followed by any symbol from sigma, and then it 44:28.140 --> 44:32.980 should either start with a capital or small a, and then have here a 44:32.980 --> 44:37.920 certain word in there, and then we would have to have either the 44:37.920 --> 44:42.600 ending s, or us, or en, or ic, or isch. 44:42.600 --> 44:47.740 All different variants of algorithmos, or algorithmen, or 44:47.740 --> 44:49.420 algorithmisch, or whatever. 44:51.060 --> 44:56.920 And so this here might occur, but does not necessarily occur, it's a 44:56.920 --> 45:03.460 potential ending, and there could be anything following that, and we 45:03.460 --> 45:06.560 would assume it should be there at least five times. 45:07.180 --> 45:12.240 So it means there are five occurrences, at least five occurrences of 45:12.240 --> 45:15.580 such a term in between. 45:16.780 --> 45:23.560 A way of specifying a more complex or more general query, but this 45:23.560 --> 45:28.700 would be something for computer scientists who would be familiar with 45:28.700 --> 45:32.240 this way of specifying queries, but normally you don't do that if you 45:32.240 --> 45:36.000 have something for everybody, so there we have different ways of 45:36.000 --> 45:42.960 specifying queries, and so internally this can be done in this way, 45:43.120 --> 45:47.580 but this is usually presented to the user in a different way. 45:49.580 --> 45:56.820 So normally we have certain Boolean queries where we just search for, 45:57.400 --> 46:03.300 for example, conjunctive or disjunctive combinations of words. 46:03.440 --> 46:08.480 We would say, okay, I list a certain number of words, so for example 46:08.480 --> 46:13.440 if I would have here these words, what is a regular expression, this 46:13.440 --> 46:18.940 is standardly interpreted as if you would search for the occurrence of 46:18.940 --> 46:23.540 any of those words, at least one of those words, where you could say, 46:23.620 --> 46:30.620 okay, is and if are not really relevant, so you would delete those 46:30.620 --> 46:34.980 words, but you would assume you have here, and what also is not that 46:34.980 --> 46:39.380 important, so you would have here a search for at least one of those 46:39.380 --> 46:42.820 that are occurring in a list, or you could make that more explicit and 46:42.820 --> 46:49.160 say you explicitly write there a disjunctive sequence of terms, or you 46:49.160 --> 46:52.640 combine it with an and, and then you have a conjunctive search, or you 46:52.640 --> 46:56.000 could actually have more Boolean operations in there, and then have 46:56.000 --> 46:56.880 more complex queries. 46:57.080 --> 47:00.860 Usually if you look at more advanced search inputs, then you can 47:00.860 --> 47:02.560 specify exactly those things. 47:03.660 --> 47:10.560 And now I have made a few, just for examples, a few search queries 47:10.560 --> 47:15.560 where you could, so where you see what actually happens if you search 47:15.560 --> 47:16.320 for certain words. 47:16.320 --> 47:21.320 Actually I did not only in Google, I looked at, this was interesting, 47:21.880 --> 47:27.020 that one of the first search engines was AltaVista, still like 47:27.020 --> 47:34.400 AltaVista, and so I entered, or I searched at AltaVista, and actually 47:34.400 --> 47:41.280 what is happening is that the search engine of AltaVista now is the 47:41.280 --> 47:42.580 search engine used by Yahoo. 47:43.780 --> 47:49.720 So it's still presented under the name of AltaVista, but if you ask a 47:49.720 --> 47:54.260 query there, you get a link which is just a Yahoo link. 47:55.740 --> 48:03.820 And now I think this is interesting, I updated that last night, and so 48:03.820 --> 48:05.320 this is different every year. 48:05.320 --> 48:10.160 I have, for comparison, I just left there the indicator of the year 48:10.160 --> 48:18.300 2007, could have updated that from the data I had last year, but I 48:18.300 --> 48:23.460 think it's, it tells the story that I wanted to present. 48:24.280 --> 48:29.480 So first of all, here is a query which could be simplified without 48:29.480 --> 48:34.600 listing all the or's in there, but here I wanted to just indicate I'm 48:34.600 --> 48:38.100 interested in one of the words that are listed here, Angewandte 48:38.100 --> 48:40.100 Informatik Universität Kassel. 48:41.180 --> 48:46.880 And you notice that at AltaVista you had 33 million pages that are 48:46.880 --> 48:49.920 listed, at Google you have 199 million. 48:51.160 --> 48:51.580 Perfect. 48:51.700 --> 48:55.180 And now we can check all these pages and find out which are relevant 48:55.180 --> 48:56.080 and which are not relevant. 48:57.340 --> 48:59.720 Probably most of them will be irrelevant. 49:01.780 --> 49:06.220 2007 I had 88 million, so something in between. 49:09.040 --> 49:15.520 I have not listed here whether that was a Google or Yahoo search, like 49:15.520 --> 49:19.060 these 88 million, but just to show you that there are differences in 49:19.060 --> 49:19.260 there. 49:19.580 --> 49:25.520 Then if I look for all the words in, like all these four words should 49:25.520 --> 49:32.060 occur, Angewandte Informatik Universität Kassel, then I have 36,000 49:32.060 --> 49:35.820 pages at AltaVista, 201,000 at Google. 49:38.360 --> 49:45.920 Well, and in 2007 I had 268,000, even more. 49:45.920 --> 49:51.040 You would assume that the number of pages has increased from 2007. 49:51.620 --> 49:55.540 Maybe it has decreased because we don't have any more Universität 49:55.540 --> 49:57.660 Kassel, but the Kassel Institute of Technology. 49:58.120 --> 50:02.540 Maybe that certain pages just disappeared, but I don't know why that 50:02.540 --> 50:07.680 happens, but it just reflects the information that is available in the 50:07.680 --> 50:09.600 catalogs of those search engines. 50:09.780 --> 50:12.780 And that's the important point, you only get the information that is 50:12.780 --> 50:14.480 available in those catalogs. 50:15.440 --> 50:21.200 Then, I looked for Angewandte Informatik and Kassel, and not 50:21.200 --> 50:21.880 Mathematik. 50:23.880 --> 50:30.940 And then, this is reduced, just 17,000 pages here, and only 29,600 at 50:30.940 --> 50:31.120 Google. 50:33.120 --> 50:36.600 And it had been 41,000 in 2007. 50:36.600 --> 50:44.100 But I don't, I have no indication on how many of those listed, or 50:44.100 --> 50:48.600 these numbers actually refer to relevant pages, it's at least the 50:48.600 --> 50:50.600 number of hits that they have in the index. 50:51.600 --> 50:55.980 Or if I looked under, this is the third way of looking for, or another 50:55.980 --> 51:00.160 way of looking for information if we are interested in an exact 51:00.160 --> 51:00.980 phrase. 51:02.200 --> 51:07.840 Then, here we see, okay, Angewandte Informatik Kassel, just 117 pages 51:07.840 --> 51:12.300 at Alta Vista, and 31,000 at Google. 51:14.620 --> 51:15.920 This is strange. 51:16.840 --> 51:18.140 This is very strange. 51:19.580 --> 51:19.880 Yeah? 51:20.460 --> 51:26.480 It's really strange, because I did that last night, I looked for this 51:26.480 --> 51:32.550 one, and now I also look for this. 51:34.790 --> 51:40.930 And definitely every page that has a listing of, which contains 51:40.930 --> 51:48.750 Angewandte Informatik Kassel is containing Angewandte and Informatik 51:48.750 --> 51:49.790 and Kassel. 51:50.810 --> 51:57.490 And we got 29,600 hits at Google, but for the string Angewandte 51:57.490 --> 52:01.470 Informatik Kassel, which should be a subset of the documents, we got 52:01.470 --> 52:03.090 31,300 at Google. 52:06.360 --> 52:07.060 This is strange. 52:07.640 --> 52:09.020 So something must be wrong there. 52:10.000 --> 52:11.080 But this happens. 52:11.920 --> 52:12.460 Yes? 52:17.110 --> 52:17.710 Okay. 52:18.490 --> 52:18.950 Maybe. 52:19.490 --> 52:20.070 You're right. 52:20.910 --> 52:23.610 But, yes. 52:24.010 --> 52:24.470 You're right. 52:24.930 --> 52:25.270 Thanks. 52:25.990 --> 52:26.510 You're right. 52:27.030 --> 52:27.970 This can happen. 52:27.970 --> 52:33.070 So, definitely I have this part here, so maybe that some of those here 52:33.070 --> 52:37.630 contain Mathematik, you're right, so my conclusion was wrong. 52:38.210 --> 52:40.790 This is still adequate, may well be, you have another question. 52:46.120 --> 52:48.220 They are very strange, yes. 52:49.160 --> 52:50.220 But things like that happen. 52:51.320 --> 52:58.560 And I do this every time I teach this course, and also a few other 52:58.560 --> 53:03.900 test queries that I always perform, and do that at different search 53:03.900 --> 53:08.940 engines, and the results are very different, and sometimes I have very 53:08.940 --> 53:15.440 strange results, which indicate that certain things, well, indicate 53:15.440 --> 53:20.760 that these algorithms are not always executed in an exact way. 53:21.580 --> 53:23.980 Some things are, in some way, erratic. 53:24.980 --> 53:29.160 It's always depending where your query actually is executed. 53:29.160 --> 53:32.760 And certainly, it's always the case that if you execute these queries 53:32.760 --> 53:39.020 here in Germany, or if you are here, or when you execute that query at 53:39.020 --> 53:43.320 some other location, when you connect to the network from a different 53:43.320 --> 53:47.280 location, you get different results, because you will be located to 53:47.280 --> 53:51.600 different catalogs, and they have different content in there. 53:51.780 --> 53:52.040 Yes. 54:06.470 --> 54:07.030 Maybe. 54:07.730 --> 54:08.010 Yes. 54:08.010 --> 54:08.130 Yes. 54:08.210 --> 54:10.330 But I think, I did not check that. 54:10.990 --> 54:14.830 I just put it in there last night, just that query. 54:15.270 --> 54:18.150 I could have checked for the advanced search in Google, and there you 54:18.150 --> 54:20.750 can search exactly for the phrase. 54:21.250 --> 54:26.110 I did not do that explicitly, so you may check whether you get similar 54:26.110 --> 54:26.850 results or not. 54:27.310 --> 54:31.290 But I just, like this observation, nevertheless, is very valid. 54:31.590 --> 54:36.270 So I definitely, thanks for that remark, definitely like the 54:36.270 --> 54:40.350 conclusion here that this was not correct, was a false observation. 54:40.950 --> 54:47.350 So it definitely may be that it's just the difference, that this extra 54:47.350 --> 54:53.410 term, not Mathematik, is reducing the number of pages, it should 54:53.410 --> 54:54.350 reduce it, definitely. 54:55.150 --> 54:55.390 Okay. 54:55.990 --> 54:59.910 I just wanted to indicate to you that those large numbers, like, 55:00.210 --> 55:03.690 anyway, these large, these numbers are much too large. 55:04.090 --> 55:06.230 What kind of information do we actually get from that? 55:06.230 --> 55:11.990 If I have 33 million or 88 million listings, I never look at all 55:11.990 --> 55:12.270 these. 55:13.550 --> 55:20.530 And if you go, I did not do that, but if you ask the same queries to 55:20.530 --> 55:25.250 MetaCrawler, then you will get much smaller results. 55:26.050 --> 55:31.450 Because MetaCrawler is looking at, or is sending a query to a list of 55:31.450 --> 55:36.410 search engines, and is then extracting the relevant information from 55:36.410 --> 55:38.550 the responses of these different search engines. 55:39.670 --> 55:43.950 And in that way, only providing to you a subset of the relevant 55:43.950 --> 55:49.850 document, of the documents that are sent to you as a response from the 55:49.850 --> 55:51.170 individual search engines. 55:51.830 --> 55:55.550 And in that way, they always present to you a smaller list of 55:55.550 --> 55:58.990 documents, but it should be those that are more relevant. 56:00.230 --> 56:01.990 So everybody should use MetaCrawler. 56:01.990 --> 56:08.870 I don't do it, but one could do it, and then you should get more 56:08.870 --> 56:09.850 relevant documents. 56:11.790 --> 56:18.450 And documents, they don't provide you with millions of hits, or at 56:18.450 --> 56:24.570 least don't tell you they have that many relevant documents there. 56:25.050 --> 56:25.230 Okay. 56:26.250 --> 56:29.750 So, I just wanted to show you that it's a difficult topic to talk 56:29.750 --> 56:32.110 about, how we can actually retrieve information. 56:32.670 --> 56:36.290 Another point is, I said we would like to look for similar words. 56:36.770 --> 56:41.930 Now what does this actually mean, to look for similar words? 56:44.490 --> 56:52.050 So we look for something like Hausaufgabe, or Hausarbeit, or 56:52.050 --> 56:55.070 Hausaufgabe, or Heimarbeit. 56:55.630 --> 57:01.350 Very similar words, you could say at least, like here, Hausaufgabe and 57:01.350 --> 57:02.930 Hausaufgabe, almost the same. 57:04.510 --> 57:09.530 But for a search engine which is analyzing those words, very 57:09.530 --> 57:09.890 different. 57:10.730 --> 57:12.850 We immediately see it's the same meaning. 57:13.310 --> 57:14.910 But how can a search engine do that? 57:15.030 --> 57:18.910 Or if we look for Stadt, we should also look for maybe for documents 57:18.910 --> 57:19.890 containing Städte. 57:20.270 --> 57:23.650 What about this, if there's Stadt with double T and not DT? 57:24.430 --> 57:28.510 Simple misspelling, completely different meaning, maybe you are also 57:28.510 --> 57:30.550 interested in something like that, or maybe not. 57:31.230 --> 57:36.450 Or if you look at the typical misspellings of Karlsruhe, very similar, 57:37.390 --> 57:38.990 but how do you measure that similarity? 57:41.470 --> 57:48.110 So one computer science way of doing that is just to look at the two 57:48.110 --> 57:51.470 words, so here we have a word, there we have a word. 57:51.470 --> 57:57.610 We just compare the different symbols, and if we have a difference, if 57:57.610 --> 58:01.370 here there's an A and there's a B, then we would say that's a 58:01.370 --> 58:04.430 difference, we count the number of positions where certain words are 58:04.430 --> 58:08.890 differing, and then we have the Hemming distance of two words. 58:09.630 --> 58:16.490 Standard notion from coding theory, we know if we talk about faults in 58:16.490 --> 58:20.290 codes, we talk about the Hemming distance, and we can characterize the 58:20.290 --> 58:27.210 ability to tolerate certain faults by just looking at the Hemming 58:27.210 --> 58:33.650 distance in those code words, but here we talk about similarity of 58:33.650 --> 58:33.850 words. 58:34.590 --> 58:38.490 So if we look at the Hemming distance of Hausarbeit and Heimarbeit, 58:39.030 --> 58:45.190 the Hemming distance is three, because here A-U-S is just replaced 58:45.190 --> 58:49.210 with E-I-M, so Hemming distance is three. 58:49.810 --> 58:55.350 If we look at Karlsruhe and Karlsruhe, the R here is missing. 58:56.430 --> 59:01.610 But that means that all these positions have mismatches. 59:02.110 --> 59:05.190 The R is missing, so instead of the R, we have an L. 59:05.530 --> 59:07.530 Instead of the L, we have an F, and so on. 59:08.250 --> 59:13.510 So a very large Hemming distance, but they are very similar, and so 59:13.510 --> 59:17.550 this should be something which we should also consider, and that's why 59:17.550 --> 59:22.290 we look at the editing distance, which is the number of editing 59:22.290 --> 59:27.270 operations that are needed to get from one word to the other word. 59:28.170 --> 59:31.790 So if we type something, how do we actually get from one word to the 59:31.790 --> 59:31.970 other? 59:31.970 --> 59:35.170 So how many deletions do we have to make? 59:35.470 --> 59:37.310 How many insertions of symbols? 59:37.750 --> 59:41.090 How many symbols have to be replaced or switched? 59:41.810 --> 59:43.930 Sometimes we just switch two symbols. 59:46.230 --> 59:49.390 Now the question is, what are the operations that are available to us? 59:50.250 --> 59:55.530 If I can just delete and insert, I have more operations than if I 59:55.530 --> 59:58.510 would be able to replace or switch something. 59:58.910 --> 01:00:04.390 And so we have to look at the allowed operations, and then we count 01:00:04.390 --> 01:00:08.110 the number of operations that we actually have to use in order to 01:00:08.110 --> 01:00:10.030 transform one word into the other. 01:00:10.690 --> 01:00:13.430 And so if we look at the editing distance between Hausarbeit and 01:00:13.430 --> 01:00:17.890 Heimarbeit, it's the same as before, at least if we assume that we 01:00:17.890 --> 01:00:22.970 have replacements as operations, so one replacement is one operation, 01:00:23.490 --> 01:00:28.870 then we can replace A-U-S with E-I-M, and we have an editing distance 01:00:28.870 --> 01:00:29.450 of three. 01:00:29.850 --> 01:00:33.970 If we would have just insertions and deletions, the distance would be 01:00:33.970 --> 01:00:38.230 six, because we would have to delete three symbols and insert three 01:00:38.230 --> 01:00:38.550 symbols. 01:00:41.690 --> 01:00:45.010 So it could also be just six. 01:00:45.510 --> 01:00:50.390 If we look at Karlsruhe and Kalsruhe, then we would have to insert, or 01:00:50.390 --> 01:00:55.690 to get from that one to that one, we would have to delete one symbol 01:00:55.690 --> 01:00:57.570 and add one symbol. 01:00:58.630 --> 01:00:59.650 Editing distance of two. 01:01:00.430 --> 01:01:05.090 Definitely those two words are much closer, much more similar than 01:01:05.090 --> 01:01:05.990 Hausarbeit and Heimarbeit. 01:01:06.990 --> 01:01:12.190 Okay, so these are distances that one could look at, and now the 01:01:12.190 --> 01:01:17.490 question is how can we actually do that, or use that, how can we 01:01:17.490 --> 01:01:19.250 determine the editing distance. 01:01:19.250 --> 01:01:22.130 Obviously, it's very simple to determine the editing, the Hamming 01:01:22.130 --> 01:01:27.510 distance, we just scan the word and check for differences, but it is 01:01:27.510 --> 01:01:30.750 more difficult to determine the editing distance. 01:01:30.850 --> 01:01:31.790 How can we do that? 01:01:31.990 --> 01:01:38.890 So, Hamming distance is obvious, and for the editing distance, it's a 01:01:38.890 --> 01:01:39.690 bit more difficult. 01:01:39.690 --> 01:01:48.690 So, if we have two words, how can we determine how different they are? 01:01:49.570 --> 01:01:56.010 So, let me draw that in a different way, yeah, so, certainly a simple 01:01:56.010 --> 01:02:00.770 observation is that if they have different lengths, then we know that, 01:02:00.890 --> 01:02:05.410 well, we have at least to add certain, or to either to insert some, if 01:02:05.410 --> 01:02:10.290 we go from that, from the lower word to the upper word, there, we 01:02:10.290 --> 01:02:14.670 would have to insert certain extra symbols, at least that, but that 01:02:14.670 --> 01:02:19.250 certainly is just a very bad estimate. 01:02:20.130 --> 01:02:29.390 The exact thing is to say, okay, is the size of U, this is the word U, 01:02:30.090 --> 01:02:34.970 this is V, we look at the difference between those two words, how can 01:02:34.970 --> 01:02:37.370 we get from U to V, or from V to U? 01:02:38.950 --> 01:02:46.290 We can just, well, delete all the symbols of U, insert all the symbols 01:02:46.290 --> 01:02:46.710 of V. 01:02:47.890 --> 01:02:53.590 But then we have done unnecessary work, because it may be that we have 01:02:53.590 --> 01:02:57.350 a certain symbol here, maybe an A, which is also occurring here. 01:02:58.150 --> 01:03:02.370 Maybe it's followed by a B, and that B is also there, and then it's 01:03:02.370 --> 01:03:07.030 followed by a C, and that C is occurring somewhere there, and then 01:03:07.030 --> 01:03:09.230 there is a D, and the D is there. 01:03:11.690 --> 01:03:17.510 Then certainly it would be unreasonable to delete A, B, C, D, and 01:03:17.510 --> 01:03:18.210 insert it again. 01:03:20.010 --> 01:03:26.270 So if we delete all the words, all the symbols of U, and insert all 01:03:26.270 --> 01:03:31.570 the symbols of V, we would have deleted all the symbols that are 01:03:31.570 --> 01:03:35.670 occurring in both words in the same sequence, and we would have 01:03:35.670 --> 01:03:36.970 inserted them again. 01:03:37.430 --> 01:03:42.550 That means we would have twice done something with symbols which is 01:03:42.550 --> 01:03:48.510 unnecessary, and W here is the longest common subsequence of U and V. 01:03:49.010 --> 01:03:55.130 So it's the longest sequence of symbols that are occurring in both 01:03:55.130 --> 01:03:58.810 words in exactly this sequence, the longest common subsequence. 01:03:59.530 --> 01:04:02.550 And so in order to determine the editing distance, what you have to do 01:04:02.550 --> 01:04:06.410 is just determine the longest common subsequence. 01:04:08.050 --> 01:04:15.250 But this is not that simple, it can be done, certainly I will show you 01:04:15.250 --> 01:04:19.570 an example, or the algorithm in a moment, how we actually do that, but 01:04:19.570 --> 01:04:24.330 it's not as simple as just computing which obviously is done in linear 01:04:24.330 --> 01:04:26.490 time, linear in the size of the words. 01:04:28.190 --> 01:04:32.170 So editing distance is something which is more interesting, I said 01:04:32.170 --> 01:04:36.090 your proof is exercise, I just proved it to you by the, well this here 01:04:36.090 --> 01:04:39.930 is true and also the other one, so this is not very difficult to 01:04:39.930 --> 01:04:41.250 understand. 01:04:42.850 --> 01:04:47.910 And what the common subsequence is, is obvious here, formally it means 01:04:47.910 --> 01:04:56.530 we have a certain, like we have our word U, and we have a word V, U 01:04:56.530 --> 01:05:06.710 and V, and we have some U0 here, we have a V0 there, and we have a W1 01:05:06.710 --> 01:05:14.110 there, we have a W1 there, and then we have a U1 and a V1 and so on, 01:05:14.610 --> 01:05:21.410 so we have these, there somewhere a WK, and we have a UK, and here 01:05:21.410 --> 01:05:25.310 also we have somewhere a WK, and we have a VK. 01:05:25.750 --> 01:05:33.510 So we have these words, W1 to WK, occurring within the word U and 01:05:33.510 --> 01:05:39.070 occurring within the word V, and it is the largest, or it is, first of 01:05:39.070 --> 01:05:42.670 all it is a common subsequence, occurring in both words, and then we 01:05:42.670 --> 01:05:46.790 are looking for the largest of those subsequences which are occurring 01:05:46.790 --> 01:05:49.690 in both words, and we have to determine that. 01:05:49.790 --> 01:05:55.070 This is just the formal definition of a common subsequence, and now we 01:05:55.070 --> 01:05:57.210 should look at how we can actually do that. 01:05:59.450 --> 01:06:04.350 You could actually utilize such a thing, like similarity, by saying, 01:06:04.490 --> 01:06:10.050 okay, if I send a query to a search engine, that search engine should 01:06:10.050 --> 01:06:15.410 also look for all words that are at editing distance at most two. 01:06:16.310 --> 01:06:21.730 It means just the difference is just inserting one or two symbols, or 01:06:21.730 --> 01:06:24.830 inserting one, deleting one, certainly you have to say what kind of 01:06:24.830 --> 01:06:30.550 operations you allow here, if it's insert, delete, or replacement, or 01:06:30.550 --> 01:06:30.910 switching. 01:06:31.250 --> 01:06:35.550 So this has to be specified, then you can search for something which 01:06:35.550 --> 01:06:39.890 is similar to the words that you actually have input as a query. 01:06:41.550 --> 01:06:46.390 Okay, and let's now look at how we can compute the editing distance. 01:06:48.930 --> 01:06:52.810 Hello, welcome to the final part of this lecture. 01:06:55.210 --> 01:07:00.670 Okay, so here it is called the so-called Lievenstein distance, it's 01:07:00.670 --> 01:07:04.250 known under very different names, it's just the editing distance. 01:07:04.730 --> 01:07:10.250 But Lievenstein has designed this algorithm, many people have designed 01:07:10.250 --> 01:07:14.730 this algorithm, Hirschberg is also one which is sometimes called it as 01:07:14.730 --> 01:07:16.750 somebody who is looking at that. 01:07:17.230 --> 01:07:23.230 Here the special thing is that we look at three operations, we look at 01:07:23.230 --> 01:07:25.910 insertions, deletions, and replacements. 01:07:26.570 --> 01:07:28.990 Three different operations that you allow for editing. 01:07:28.990 --> 01:07:38.590 And then we would like to see what the distance is of two words, here 01:07:38.590 --> 01:07:39.990 we call them S and T. 01:07:41.860 --> 01:07:44.030 So we have S and we have T. 01:07:44.750 --> 01:07:51.590 Now this word has, let's assume these are N, no M here I said, so M 01:07:51.590 --> 01:07:55.390 symbols here we have N symbols, one to N. 01:07:56.370 --> 01:07:59.590 And now the approach is a dynamic programming approach. 01:08:00.190 --> 01:08:04.050 You know what dynamic programming approach means, it's a standard 01:08:04.050 --> 01:08:08.590 approach to address certain problems. 01:08:09.010 --> 01:08:13.530 We first of all look at the small problems, solve those small 01:08:13.530 --> 01:08:19.130 problems, and then address larger, so we solve small problems, list of 01:08:19.130 --> 01:08:24.390 small problems, then would like to solve larger problems by just 01:08:24.390 --> 01:08:29.630 combining information from these smaller problems. 01:08:30.270 --> 01:08:34.850 And so this is not divide and conquer, but it's dynamic programming, 01:08:35.350 --> 01:08:40.250 we just use the information from small problems in order to get the 01:08:40.250 --> 01:08:41.910 solution for the larger problems. 01:08:42.990 --> 01:08:47.730 Usually we do that in a tabular approach, that we know that's why we, 01:08:48.170 --> 01:08:53.390 usually we fill some kind of table, and that's the standard name for 01:08:53.390 --> 01:08:54.010 dynamic programming. 01:08:54.710 --> 01:08:56.170 Now what are we doing here? 01:08:57.350 --> 01:09:00.410 What is the dynamic programming approach in this sense? 01:09:01.290 --> 01:09:03.330 What is the simple problem? 01:09:03.790 --> 01:09:11.930 The simple problem would be to look at just the first symbol of S, and 01:09:11.930 --> 01:09:17.970 the first symbol of T, and look how much information, or what kind of 01:09:17.970 --> 01:09:23.450 operations are necessary to get from the first symbol of S to the 01:09:23.450 --> 01:09:24.470 first symbol of T. 01:09:25.190 --> 01:09:28.430 If it's the same, we don't have to do anything. 01:09:29.430 --> 01:09:33.870 If it's different, we should have to replace something. 01:09:34.620 --> 01:09:39.370 Or maybe we have to delete something, or insert something. 01:09:40.790 --> 01:09:42.530 These are different operations. 01:09:43.830 --> 01:09:49.910 And then we look essentially, well if we have two symbols of S, how 01:09:49.910 --> 01:09:53.230 can we get from two symbols of S to one symbol of T. 01:09:55.010 --> 01:09:57.390 We have three, and so on. 01:09:57.450 --> 01:10:03.190 Or more general, if we have all the symbols from 1 to i, this 01:10:03.190 --> 01:10:09.870 substring, and a substring from 1 to j and T, how many operations are 01:10:09.870 --> 01:10:18.950 necessary to get from this substring here, S1 to Si, to a substring T1 01:10:18.950 --> 01:10:19.550 to Tj. 01:10:22.200 --> 01:10:25.110 This can be done by looking at this small information. 01:10:25.450 --> 01:10:26.950 So we build up a table. 01:10:28.470 --> 01:10:32.350 And this table essentially looks like this. 01:10:32.350 --> 01:10:43.970 We have here our word, and we have here essentially S, 1, 2, 3, and so 01:10:43.970 --> 01:10:44.230 on. 01:10:44.310 --> 01:10:47.290 And we have T, no, the other way around. 01:10:47.990 --> 01:10:54.290 This usually T is up there, S is here, S, 1, 2, 3, and so on. 01:10:55.090 --> 01:10:59.490 And so if we have assumed we have here just dot dot dot, and here we 01:10:59.490 --> 01:11:03.290 have an i, and up here we have j. 01:11:05.310 --> 01:11:12.530 Now we would like to fill in this field here, the field i, j, and we 01:11:12.530 --> 01:11:16.810 would like to get there the value Dij. 01:11:18.250 --> 01:11:22.830 How can I get Dij from the information that is already in the table? 01:11:22.830 --> 01:11:32.190 I assume I have started here, and so I assume that I have information 01:11:32.190 --> 01:11:37.690 in this field here, which is i, j, minus 1. 01:11:38.330 --> 01:11:42.690 I have information in this field, which is i minus, like the distance, 01:11:43.590 --> 01:11:49.910 I'm referring to transforming the string S up to i minus 1, into T up 01:11:49.910 --> 01:11:50.450 to j. 01:11:51.140 --> 01:11:55.830 And here I have i minus 1, j minus 1. 01:11:56.710 --> 01:12:00.890 And now we have to, like this is exactly the information I need in 01:12:00.890 --> 01:12:05.350 order to find out what the distance, or what the number of operations 01:12:05.350 --> 01:12:14.530 is that I need to get from S1 to Si, to T1 to Tj. 01:12:16.280 --> 01:12:17.750 So how can we use that? 01:12:18.870 --> 01:12:28.550 So, if I look at Di minus 1j, Di minus 1j means from S up to the 01:12:28.550 --> 01:12:38.630 position i minus 1, to j, i minus 1 is this one here, I have a shorter 01:12:38.630 --> 01:12:47.620 sequence, okay, if I would like to use that number I know that I would 01:12:47.620 --> 01:12:52.980 have to delete the symbol Si in order to have exactly the distance 01:12:52.980 --> 01:12:56.760 that I had for S1 to Si minus 1 to get to j. 01:12:57.180 --> 01:12:59.380 That means I would have to delete one symbol. 01:13:00.240 --> 01:13:03.560 That means the number of operations is the number of operations I have 01:13:03.560 --> 01:13:12.180 to get from S1 to Si minus 1, one symbol to the left of that, and 01:13:12.180 --> 01:13:14.020 transform that into T1 to Tj. 01:13:14.020 --> 01:13:18.360 So if it's just a deletion, I would have Di minus 1j plus 1. 01:13:19.380 --> 01:13:26.320 I could look at the same row here, and look at what would happen if I 01:13:26.320 --> 01:13:32.200 look for the distance, the number of operations I need to get from S1 01:13:32.200 --> 01:13:34.900 to Si to T1 to Tj minus 1. 01:13:35.520 --> 01:13:40.780 If that is the same as going from i to j, it means I have to insert 01:13:40.780 --> 01:13:41.260 something. 01:13:41.380 --> 01:13:47.320 I have to insert the symbol Tj, another operation. 01:13:47.660 --> 01:13:50.160 So that would mean this distance plus 1. 01:13:51.120 --> 01:14:02.480 Now if I look at this entry here, I have to compare the symbol Si and 01:14:02.480 --> 01:14:03.080 Tj. 01:14:03.080 --> 01:14:06.740 Si and Tj. 01:14:07.180 --> 01:14:13.360 If Si and Tj are identical, I don't have to do anything. 01:14:13.620 --> 01:14:20.140 I have the same distance as I had for transforming S1 to Si minus 1 to 01:14:20.140 --> 01:14:22.400 T1 to Tj minus 1. 01:14:23.100 --> 01:14:26.140 If they are different, I just have to replace the symbol. 01:14:27.030 --> 01:14:35.800 And so, these are the possibilities for getting the distance, or the 01:14:35.800 --> 01:14:40.940 number of operations, that I have to execute in order to get from S1 01:14:40.940 --> 01:14:42.900 to Si to T1 to Tj. 01:14:43.860 --> 01:14:48.120 And I certainly take the minimum of that, because I don't want to 01:14:48.120 --> 01:14:49.580 execute extra operations. 01:14:50.060 --> 01:14:52.820 I just take the minimum of the possible choices. 01:14:52.820 --> 01:14:59.860 And so, by just knowing those three entries, I can fill in the 01:14:59.860 --> 01:15:01.860 adequate information there. 01:15:03.020 --> 01:15:08.700 That means I can start here, and then enter those values there. 01:15:09.040 --> 01:15:09.980 This is very simple. 01:15:10.800 --> 01:15:19.200 How I can actually generate the, like from nothing, the term T1, T2, 01:15:19.360 --> 01:15:20.400 T3, and so on. 01:15:21.080 --> 01:15:21.760 Very simple. 01:15:22.000 --> 01:15:25.220 So this is just 1, 2, 3, and so on. 01:15:25.340 --> 01:15:29.460 Here I have 1, 2, 3, 4, and so on. 01:15:30.180 --> 01:15:32.080 And then, this is simple. 01:15:33.200 --> 01:15:36.720 And so, then I can fill in that field, I can fill in that one, I can 01:15:36.720 --> 01:15:37.560 fill in that one. 01:15:38.040 --> 01:15:39.360 Very simple operation. 01:15:40.300 --> 01:15:44.140 It's just a scanning of that table. 01:15:44.580 --> 01:15:48.520 At every table, at every entry, I just have to compare those three 01:15:48.520 --> 01:15:49.000 values. 01:15:49.000 --> 01:15:55.140 And so, definitely this is just an operation which takes time, n times 01:15:55.140 --> 01:15:55.360 n. 01:15:56.500 --> 01:16:00.220 I have to look at all the different fields in there. 01:16:00.980 --> 01:16:05.660 And so, this is a quadratic, or you could say, just the product of the 01:16:05.660 --> 01:16:06.920 length of those two terms. 01:16:07.520 --> 01:16:13.460 And in that way, I have information on how many operations I have to 01:16:13.460 --> 01:16:16.700 execute in order to get from S to T. 01:16:17.700 --> 01:16:23.080 Now if we do that, for a simple example, here you see exactly again 01:16:23.080 --> 01:16:26.760 these four possibilities that I just listed. 01:16:27.620 --> 01:16:34.760 The initial thing would be if we have nothing, the empty word, how can 01:16:34.760 --> 01:16:38.580 I generate from the empty word, the word Saturday? 01:16:39.220 --> 01:16:43.080 I just have to enter those symbols, insertions. 01:16:43.840 --> 01:16:50.540 How can I, again here, how can I get from zero to that word, again 01:16:50.540 --> 01:16:51.340 those values. 01:16:51.960 --> 01:16:57.360 And then here, from S to S, certainly this would be a zero, this is 01:16:57.360 --> 01:16:59.480 the smallest value, you have the same symbol. 01:16:59.480 --> 01:17:10.680 So, if we have S to A, now here we have, this would be one, because we 01:17:10.680 --> 01:17:17.560 just have to insert one symbol, and so on. 01:17:17.560 --> 01:17:21.400 I don't want to go through all these different fields here, I will 01:17:21.400 --> 01:17:23.960 just show you what happens here. 01:17:23.960 --> 01:17:31.520 This is the complete table filled in using always, or computing 01:17:31.520 --> 01:17:36.120 always, the minimum of those values that have to be compared. 01:17:36.120 --> 01:17:45.700 And so we get here the values, and we also get these links which just 01:17:45.700 --> 01:17:50.280 indicate how we have, or which term actually is taken, which operation 01:17:50.280 --> 01:17:58.720 has been taken in the, like going from this top left to the bottom 01:17:58.720 --> 01:18:01.460 right entry. 01:18:01.460 --> 01:18:07.380 So, in this way we see how these are generated, and then certainly to 01:18:07.380 --> 01:18:13.640 get actually the distance from getting the editing distance between 01:18:13.640 --> 01:18:19.920 Sunday and Saturday, we just have to look for the smallest entry here, 01:18:20.220 --> 01:18:23.980 like this is the final value indicating three. 01:18:23.980 --> 01:18:31.720 And so, if we now follow that line here, we finally get to, or see how 01:18:31.720 --> 01:18:33.280 these operations are actually executed. 01:18:34.640 --> 01:18:42.980 So this is indicating what we have to do to get from one word to 01:18:42.980 --> 01:18:48.920 another one, and how we can execute, or how we can calculate the 01:18:48.920 --> 01:18:50.540 editing distance of two words. 01:18:50.780 --> 01:18:55.020 Using, or assuming that we just have deletion, insertion, and 01:18:55.020 --> 01:18:55.460 replacement. 01:18:56.020 --> 01:18:56.580 You have a question? 01:18:56.580 --> 01:18:58.620 Is there a reason there's a line in between? 01:19:05.650 --> 01:19:06.590 Yeah, it's just a bug. 01:19:07.930 --> 01:19:09.950 There should be a line in there. 01:19:11.390 --> 01:19:11.550 Yeah. 01:19:13.630 --> 01:19:14.090 Okay. 01:19:14.370 --> 01:19:19.610 I think it's, so this is just showing you the line following the 01:19:19.610 --> 01:19:25.970 smallest values there, and so we have the editing distance indicated 01:19:25.970 --> 01:19:26.390 in there. 01:19:28.030 --> 01:19:28.550 Okay. 01:19:28.890 --> 01:19:32.030 We can use pseudocode for that. 01:19:32.250 --> 01:19:34.410 I don't want to go into the details there. 01:19:34.490 --> 01:19:38.590 This is just this calculation which I told you about. 01:19:38.910 --> 01:19:41.390 We don't have to go into the details of that algorithm. 01:19:42.910 --> 01:19:46.110 I, in fact, you are all capable of transforming something which I have 01:19:46.110 --> 01:19:49.750 explained to you just now into code of a program. 01:19:49.750 --> 01:19:56.010 This is not that interesting, really, to write a program if we know 01:19:56.010 --> 01:19:57.510 what the algorithm actually is about. 01:19:58.870 --> 01:19:59.190 Okay. 01:19:59.730 --> 01:20:04.090 So the important point, certainly, is that it's, the complexity is 01:20:04.090 --> 01:20:07.210 just product of the two words that we have there. 01:20:08.350 --> 01:20:16.990 And then we would like to now look for documents in, no, look for 01:20:16.990 --> 01:20:18.530 words in documents. 01:20:18.530 --> 01:20:23.630 I would like to follow now this assumption one, that we would like to 01:20:23.630 --> 01:20:27.670 do a full text search, look for the occurrence of words in documents, 01:20:27.990 --> 01:20:32.630 and for that we have to find out how we can actually do that. 01:20:33.110 --> 01:20:36.630 So the input for that would be a document and a word. 01:20:36.790 --> 01:20:39.890 We would like to check, does this word occur in that document? 01:20:39.890 --> 01:20:45.490 We assume that the document has definitely a larger length than the 01:20:45.490 --> 01:20:48.270 word, otherwise we wouldn't have to look for that. 01:20:49.210 --> 01:20:54.770 And what we would like to get are all the positions where W starts in 01:20:54.770 --> 01:20:55.350 D. 01:20:55.970 --> 01:21:01.510 So if we have our string here, our very long document written as a 01:21:01.510 --> 01:21:07.410 sequence of symbols, then if W does occur there, we would like to get 01:21:07.410 --> 01:21:08.090 that position. 01:21:08.290 --> 01:21:13.090 Or maybe if it's occurring several times, we might also want to get 01:21:13.090 --> 01:21:14.070 that position. 01:21:14.450 --> 01:21:20.330 So maybe we would like to get all the positions where a word occurs 01:21:20.330 --> 01:21:20.990 within a document. 01:21:21.270 --> 01:21:27.250 As I told you, you might be interested in finding out how often a term 01:21:27.250 --> 01:21:30.490 actually is appearing in a document. 01:21:30.490 --> 01:21:34.490 For that we need the number of occurrences, not just does it occur. 01:21:35.290 --> 01:21:39.010 This would be the initial thing we would be interested in. 01:21:39.750 --> 01:21:44.910 So what we would have to look at is something like, define something 01:21:44.910 --> 01:21:48.290 like a finite automaton which is capable of finding out whether the 01:21:48.290 --> 01:21:51.650 word W occurs within some document. 01:21:52.250 --> 01:21:58.250 Simplified here, writing just the asterisk W and asterisk, we check 01:21:58.250 --> 01:22:03.890 whether D is, well this is formalism to say D is an invert of the 01:22:03.890 --> 01:22:04.970 language of that automaton. 01:22:05.890 --> 01:22:08.450 So we could just specify the automaton very simply. 01:22:09.030 --> 01:22:13.970 We just write a non-deterministic automaton having like this starting 01:22:13.970 --> 01:22:18.930 state here, and then if we look for uni, we would just write those 01:22:18.930 --> 01:22:23.410 finite automaton in this way, and that's it. 01:22:23.410 --> 01:22:26.930 Just implement that and you can execute the query. 01:22:27.530 --> 01:22:32.190 Now this would take a bit of time, you would need a deterministic 01:22:32.190 --> 01:22:33.030 version of that. 01:22:33.330 --> 01:22:34.910 We can write that as a program. 01:22:35.850 --> 01:22:37.430 So how do we write that as a program? 01:22:38.290 --> 01:22:46.070 We would just for, well this is written now in a Pascal-like or not 01:22:46.070 --> 01:22:52.030 Java -like version, but it's easily readable I think. 01:22:52.030 --> 01:23:01.070 So we just go into a loop from 0 to 1 per N minus M, so certainly the 01:23:01.070 --> 01:23:10.190 rightmost position could be N minus M, because we look for complete 01:23:10.190 --> 01:23:11.330 occurrences of the word. 01:23:12.530 --> 01:23:17.470 That's why we only have to look for, let me rewrite that here, we look 01:23:17.470 --> 01:23:22.710 at possible occurrences, so this would be one position I that we look 01:23:22.710 --> 01:23:27.210 at, and then we would like to check whether starting from that 01:23:27.210 --> 01:23:34.770 position I, we actually have at the positions I plus 1 to I plus M 01:23:34.770 --> 01:23:37.810 exactly our word W in there. 01:23:37.810 --> 01:23:48.010 So J is set to 1, and then while we scan through that word, and while 01:23:48.010 --> 01:23:55.970 the document is exact or has the same symbols as W at those locations, 01:23:57.830 --> 01:24:05.650 we increase the value of J, and if after we exit that loop, J is 01:24:05.650 --> 01:24:09.810 larger than M, it means that all the symbols actually match, and we 01:24:09.810 --> 01:24:14.850 have a match at position I plus 1, because we looked at positions W1, 01:24:15.270 --> 01:24:22.190 we looked at the symbols W1 to WM at positions I plus 1 to I plus M. 01:24:22.770 --> 01:24:24.410 So this is a very simple algorithm. 01:24:25.290 --> 01:24:25.610 Trivial. 01:24:26.310 --> 01:24:26.790 That's it. 01:24:27.230 --> 01:24:27.730 Pattern matching. 01:24:28.370 --> 01:24:31.590 But that now has to be analyzed. 01:24:32.530 --> 01:24:37.290 How much time does that actually need to execute this algorithm? 01:24:37.770 --> 01:24:41.810 We have a loop there, this is one loop, this is another loop, this 01:24:41.810 --> 01:24:47.670 loop is running from 0 to N minus M, if M is a constant or a small 01:24:47.670 --> 01:24:51.950 value, it's approximately N. 01:24:51.950 --> 01:24:56.290 Then here we have at every position, what we do here actually, is at 01:24:56.290 --> 01:25:03.690 every position from I to N minus M, we might scan through almost all 01:25:03.690 --> 01:25:08.830 the symbols of W, so the upper bound for that would be N times M. 01:25:09.910 --> 01:25:11.250 Quite a long time. 01:25:12.790 --> 01:25:16.670 The point is, if we have, for example, come to such a position, and 01:25:16.670 --> 01:25:19.210 then notice, well, there's a mismatch. 01:25:19.930 --> 01:25:24.890 Here's some kind of mismatch, some X, which does not occur in our 01:25:24.890 --> 01:25:25.290 word. 01:25:26.390 --> 01:25:31.470 We have scanned through this prefix of the word, and notice these 01:25:31.470 --> 01:25:33.430 symbols are occurring in the document. 01:25:34.810 --> 01:25:39.030 And now this is information one should not lose, because we have this 01:25:39.030 --> 01:25:42.750 information, and then we should exploit that. 01:25:42.750 --> 01:25:47.610 And to exploit that is something which Knuth Morris Pratt did a long 01:25:47.610 --> 01:25:51.630 time ago, when people looked at these pattern matching algorithms. 01:25:52.850 --> 01:25:57.630 So what we actually notice is we have been at some position, so this 01:25:57.630 --> 01:26:04.170 was I, this is position I plus 1, and we notice a mismatch. 01:26:04.230 --> 01:26:05.090 Here's a mismatch. 01:26:08.130 --> 01:26:17.430 And if we have a mismatch, we should not just move the word, the 01:26:17.430 --> 01:26:21.210 potential pattern here, one position to the right, but we should 01:26:21.210 --> 01:26:24.450 exploit the knowledge that we have about this prefix. 01:26:26.250 --> 01:26:27.510 So we should look at the structure. 01:26:28.070 --> 01:26:33.630 If we know that the first symbol here is not occurring at all in the 01:26:33.630 --> 01:26:37.670 remaining positions here, we can immediately shift it many positions 01:26:37.670 --> 01:26:38.170 to the right. 01:26:39.090 --> 01:26:49.590 So what we should do is we find out how many symbols at the prefix of 01:26:49.590 --> 01:26:59.490 our pattern, how many of these symbols occur to the left of the symbol 01:26:59.490 --> 01:27:02.010 WJ in our pattern. 01:27:02.770 --> 01:27:11.810 So if those symbols here reoccur at this position, then we know we can 01:27:11.810 --> 01:27:19.250 shift the pattern exactly by that distance. 01:27:19.250 --> 01:27:24.670 And we would like to optimize that distance, shift the pattern as far 01:27:24.670 --> 01:27:28.970 as possible to the right, but certainly not too far, because certainly 01:27:28.970 --> 01:27:31.930 this could be a potential new starting position. 01:27:32.530 --> 01:27:37.710 So we would like to indicate the next possible starting position of 01:27:37.710 --> 01:27:41.050 the pattern and shift it exactly that much. 01:27:41.050 --> 01:27:49.630 But that also means we don't have to look again at those locations 01:27:49.630 --> 01:27:55.210 that we have already scanned, because we will shift the pattern as far 01:27:55.210 --> 01:28:01.270 to the right as reasonable, exploiting the information that what is to 01:28:01.270 --> 01:28:09.910 the left of the WJ is exactly, or is the same as before, but the 01:28:09.910 --> 01:28:14.790 symbol that is at this location here, so the symbol that was there, 01:28:15.350 --> 01:28:17.370 certainly should be different from WJ. 01:28:19.030 --> 01:28:24.350 And then we can optimize the performance of the algorithm, and that's 01:28:24.350 --> 01:28:27.770 the Knuth-Morris-Pratt algorithm which runs in linear time, and not in 01:28:27.770 --> 01:28:32.650 time, like in time order of N, because we only scan every symbol here 01:28:32.650 --> 01:28:37.830 once, we only increase those values, and we can shift larger distances 01:28:37.830 --> 01:28:41.810 and then can improve the efficiency of the algorithm. 01:28:42.210 --> 01:28:43.730 Okay, that's it for today.