WEBVTT

00:00.860 --> 00:02.060
Okay, good morning.

00:02.240 --> 00:04.980
Welcome to another session of Algorithms for Internet Applications.

00:06.440 --> 00:09.800
Just five minutes delayed today, because now we know how to deal with

00:09.800 --> 00:10.640
the technical problems.

00:12.880 --> 00:13.420
But...

00:13.420 --> 00:13.780
Okay.

00:14.260 --> 00:18.500
Last time we looked at, again, last time at Internet technology, we

00:18.500 --> 00:22.320
looked at some aspects of the TCP protocol.

00:23.040 --> 00:25.000
I showed you the...

00:27.680 --> 00:30.100
header for TCP, right?

00:30.200 --> 00:30.720
That was it.

00:30.800 --> 00:37.840
I told you something about the logical connections, about ports and

00:37.840 --> 00:43.640
sockets, and all the different aspects of the header fields.

00:44.160 --> 00:48.480
We talked about the connection management, and in particular talked

00:48.480 --> 00:52.300
about the flow control, which is one of the major tasks of TCP.

00:53.160 --> 00:55.880
And that was more or less it.

00:56.180 --> 01:04.160
I mentioned that TCP has problems if we look at specific applications

01:04.160 --> 01:08.020
where it is important to have a sustainable bandwidth, where it's not

01:08.020 --> 01:14.320
that essential if some of the datagrams are lost, because in audio

01:14.320 --> 01:20.200
transmission, for example, that would just be a small mistake in the

01:20.200 --> 01:26.300
audio signal, but it's important to maintain a certain frequency of

01:26.300 --> 01:26.640
data.

01:26.900 --> 01:30.200
And so for that, TCP is not that reasonable.

01:30.520 --> 01:31.780
So for that, we have UDP.

01:32.720 --> 01:37.420
And then I briefly showed you this slide on ATM, where the most

01:37.420 --> 01:42.700
essential point is that that is a protocol where the quality of

01:42.700 --> 01:48.140
service is an important aspect that we can have guaranteed quality

01:48.140 --> 01:50.980
there for different service classes.

01:52.540 --> 01:56.400
And that was the last slide of the last lecture.

01:57.200 --> 02:02.620
And so now I would like to come to the next chapter, where we talk

02:02.620 --> 02:08.420
about something which is more using the Internet, using services on

02:08.420 --> 02:13.700
the Internet, and in particular one point or one topic which is very

02:13.700 --> 02:16.880
relevant for the Internet, as you all know, is dealing with

02:16.880 --> 02:17.440
information.

02:17.440 --> 02:22.620
Lots of things have evolved there, and we know that there is, well,

02:22.820 --> 02:25.740
here I say there are currently about 300 million web searches per day.

02:25.860 --> 02:29.020
Probably this is much larger.

02:29.060 --> 02:32.520
Meanwhile, funny, all of a sudden I have a black pen.

02:33.000 --> 02:35.860
Don't know why the pen switched to black.

02:35.960 --> 02:41.580
I did not choose that.

02:41.740 --> 02:44.320
So I would take red again.

02:44.320 --> 02:44.700
Okay.

02:46.840 --> 02:51.120
So definitely there might be more than that, but it's just, the

02:51.120 --> 02:54.540
important point is that there are millions and millions of web

02:54.540 --> 02:56.900
searches per day, and so this is something where we really have to

02:56.900 --> 03:00.780
look at algorithms, how things like that actually are supported, how

03:00.780 --> 03:03.360
we can get information.

03:04.780 --> 03:08.260
Searching for information is definitely one of the most popular

03:08.260 --> 03:08.720
applications.

03:08.860 --> 03:09.480
We all do it.

03:09.520 --> 03:10.720
We all search for information.

03:10.720 --> 03:16.680
Very often we don't type in the address of a website, but type it in

03:16.680 --> 03:23.440
the search field, and then just go to the appropriate location using a

03:23.440 --> 03:26.520
web service, a web search service.

03:27.180 --> 03:30.760
And so what we have to look at briefly is what search engines are

03:30.760 --> 03:34.540
about, how they operate, what some essential aspects of these search

03:34.540 --> 03:35.180
engines are.

03:35.500 --> 03:40.720
We should look at some basics of information retrieval, and it's

03:40.720 --> 03:45.200
always a problem that you have, there are different points in your

03:45.200 --> 03:50.560
courses that you are taking here in your programs of study where you

03:50.560 --> 03:55.560
might have already looked at topics related to this, so for example,

03:56.020 --> 04:00.840
if we talk about retrieving information, then we very often look for

04:00.840 --> 04:07.080
certain words in some documents, so if we would look for information

04:07.080 --> 04:10.380
retrieval and would like to get this document, which I've just

04:10.380 --> 04:13.580
presented to you, it means we would have to look for exactly the

04:13.580 --> 04:17.200
occurrence of that word in that document, so that means we would have

04:17.200 --> 04:19.980
to do some kind of pattern matching in texts.

04:21.120 --> 04:24.040
And this would be something which would take a long time because we

04:24.040 --> 04:25.800
would have to look through all the different documents.

04:26.020 --> 04:27.040
Certainly we don't do that.

04:27.560 --> 04:31.240
And so what we usually do is, or not we, but the search engines do is

04:31.240 --> 04:36.940
they create a huge index where we can actually jump immediately to the

04:36.940 --> 04:37.860
relevant documents.

04:37.860 --> 04:41.860
That means we don't search in documents, but search in catalogs and

04:41.860 --> 04:47.760
indexes where all the information is structurally available.

04:49.340 --> 04:53.940
Then the search engine definitely has to analyze search phrases.

04:54.340 --> 04:57.820
We formulate some queries in some way, and they have to be interpreted

04:57.820 --> 04:58.820
in a reasonable way.

04:59.380 --> 05:00.780
We will look at that briefly.

05:00.980 --> 05:03.340
We have to measure the relevance of the retrieved documents.

05:03.500 --> 05:05.600
We don't want to get all kinds of documents.

05:05.600 --> 05:09.500
And we will look at that problem for a moment.

05:10.620 --> 05:17.080
And then, there definitely is quite a large range of search engines

05:17.080 --> 05:17.760
available.

05:19.160 --> 05:22.980
And, well, most of you probably know at least one.

05:23.260 --> 05:25.520
Namely, you all know...

05:26.400 --> 05:27.920
Did I list it here?

05:27.980 --> 05:28.840
Yeah, I listed Google.

05:30.020 --> 05:33.660
So Google is one of many, many, many search engines.

05:33.660 --> 05:36.480
And it certainly is one of the major ones.

05:37.020 --> 05:38.640
Some appear in a different...

05:38.640 --> 05:44.660
There's still quite a range of different search engines available.

05:45.540 --> 05:49.140
So here I have some old list.

05:49.500 --> 05:53.700
OLL, Netfine, Excite, Google, certainly, Hotbot, Infoseek, Lycos,

05:53.800 --> 05:57.900
Webcrawler, Yahoo, Metacrawler, and so on, and so on.

05:58.000 --> 05:59.400
Lots of search engines.

05:59.580 --> 06:00.880
They all have different aspects.

06:00.880 --> 06:05.000
Somehow, we use almost only one.

06:06.560 --> 06:08.940
But this is another problem.

06:11.260 --> 06:14.880
So, at this website that I mentioned here...

06:17.340 --> 06:21.340
Actually, I think it's not important to go to the website now.

06:21.960 --> 06:28.440
That website, you get all kinds of information on functionalities of

06:28.440 --> 06:31.460
search engines.

06:31.600 --> 06:34.880
And in particular, what you get there is information

06:37.940 --> 06:42.380
on how you actually should design your document.

06:42.580 --> 06:44.600
So if you write a document...

06:44.600 --> 06:47.100
This was supposed to come from Google.

06:47.900 --> 06:52.060
So if this is a document, you have several documents, and you have

06:52.060 --> 06:55.620
certain important information in there, and you would like to make

06:55.620 --> 07:01.400
sure that if you put a query to Google, then the result should be a

07:01.400 --> 07:06.680
list, and the top documents should be exactly your documents.

07:07.240 --> 07:14.660
Whenever it is information that was looked for, which is relevant for

07:14.660 --> 07:15.560
your documents.

07:16.320 --> 07:22.200
So, if you are designing the webpages of a certain company, or of your

07:22.200 --> 07:26.720
own company, or you have certain interests, that your information is

07:26.720 --> 07:32.040
available to the relevant users as a response to a query, you must

07:32.040 --> 07:36.260
make sure that your website is listed as the top rank.

07:37.080 --> 07:40.960
And so, in order to know how to do that, you have to know how actually

07:40.960 --> 07:47.540
the search engines classify webpages, websites, documents, how they

07:47.540 --> 07:52.320
are ranked, and how you can make sure that you don't end up somewhere

07:52.320 --> 07:56.180
down there, where you never look at, but that you can jump up to some

07:56.180 --> 07:57.160
places over there.

07:57.680 --> 08:03.340
This has to be done in a way that is justified, and not considered to

08:03.340 --> 08:10.100
be website or some kind of spamming, that you have unjustified

08:10.100 --> 08:14.220
information in there, and in that way try to get to the top rank.

08:14.220 --> 08:19.400
We know that if we look at the webpage that we get as a result to a

08:19.400 --> 08:25.880
query, there are always some elements at the top listing, which are

08:25.880 --> 08:26.760
paid entries.

08:27.260 --> 08:29.900
This is something which has not been there in the beginning of the

08:29.900 --> 08:33.140
search engines, but certainly popped up because the companies would

08:33.140 --> 08:40.720
like to make money, and so they get payment from companies who would

08:40.720 --> 08:45.520
like to be always listed as the top entries, and if you look more

08:45.520 --> 08:49.980
closely, you will notice that certain sources of information are

08:49.980 --> 08:54.140
always in the top rank, at least with Google, like for example

08:54.140 --> 08:58.540
Wikipedia is always in the top ranks, because it's owned by Google,

08:58.740 --> 09:01.260
and so they always make sure that their information is on the top.

09:02.500 --> 09:07.280
So this is all stuff about...

09:08.000 --> 09:12.540
when we talk about searching for information, we have to know how you

09:12.540 --> 09:16.600
can actually locate information, and then how you can present that

09:16.600 --> 09:17.120
information.

09:17.800 --> 09:21.160
And so, you are shaking your head in the background there.

09:21.580 --> 09:22.320
What's wrong?

09:23.960 --> 09:24.560
Pardon?

09:26.120 --> 09:27.700
As far as I know, yes.

09:31.760 --> 09:36.880
That's what I heard some time ago, that they are very closely related

09:36.880 --> 09:37.300
to Google.

09:39.300 --> 09:45.140
So it has not been founded by Google, but they are at least very

09:45.140 --> 09:46.360
closely connected to Google.

09:49.800 --> 09:52.480
So Google owns many, many different services.

09:53.080 --> 09:53.740
They are very powerful.

09:54.880 --> 09:57.180
And they really provide perfect services.

09:59.960 --> 10:05.780
What I wanted to tell you is that at this website, which changed its

10:05.780 --> 10:11.040
appearance significantly in recent years, so yesterday I just wanted

10:11.040 --> 10:14.520
to briefly update the information I have in my slides here on this

10:14.520 --> 10:18.000
topic, and I noticed that all the nice sites where I had those

10:18.000 --> 10:20.580
information have disappeared somewhere.

10:20.760 --> 10:21.580
I don't know why.

10:21.940 --> 10:27.260
It's more difficult to get exact information on certain web search

10:27.260 --> 10:27.900
statistics.

10:28.800 --> 10:30.760
Then I noticed a few things again.

10:30.760 --> 10:38.160
So this URL that I listed here now has a list of tips on links to

10:38.160 --> 10:44.440
information where you get all kinds of things about search engines,

10:44.600 --> 10:47.240
facts and funds, status reports, resources, and so on.

10:47.340 --> 10:52.800
And here the point of view of this website is always information for

10:52.800 --> 10:56.740
the designer of websites, what they should consider when they design

10:56.740 --> 11:02.180
websites in order to make sure that they are adequately listed in

11:02.180 --> 11:04.600
search engine rankings.

11:04.800 --> 11:06.440
So this is an important thing.

11:07.040 --> 11:11.260
It's not sufficient to just produce information and make sure it can

11:11.260 --> 11:15.800
be found, but you have to make sure that it is presented in the right

11:15.800 --> 11:19.180
way, that it's made available and visible to the persons that you

11:19.180 --> 11:21.480
think are the relevant target audience.

11:21.480 --> 11:28.580
Okay, so this is what we will at least look at to some extent.

11:29.060 --> 11:34.000
I cannot present you all the different algorithms that are around

11:34.000 --> 11:37.460
there, but we have to briefly classify what's going on there.

11:37.900 --> 11:41.400
So first of all, what is it that we talk about when we talk about

11:41.400 --> 11:42.120
search engines?

11:42.660 --> 11:45.300
Most of you use them, you know what they actually do.

11:45.760 --> 11:49.580
They constantly visit websites on the Internet in order to create

11:49.580 --> 11:50.840
catalogs of web pages.

11:50.840 --> 11:58.120
So the search engines are usually created automatically by some

11:58.120 --> 12:06.080
program which is visiting the web, and so this is done without human

12:06.080 --> 12:06.700
interference.

12:07.100 --> 12:10.340
You don't have to manually look at the results and then put it in some

12:10.340 --> 12:14.160
catalog, but the search engines do that automatically.

12:14.740 --> 12:18.440
Then there are directories, not catalogs, but directories.

12:18.440 --> 12:21.260
This is just a classification.

12:21.740 --> 12:27.860
Directories are actually manually created catalogs of web pages.

12:28.040 --> 12:32.140
That means somebody has looked at those resources that are listed

12:32.140 --> 12:34.920
there and classified them and made some quality check.

12:35.620 --> 12:42.640
One of the major original examples is Yahoo, where Yahoo nowadays is

12:42.640 --> 12:46.680
not just a directory, but also a directory extended with catalogs.

12:46.680 --> 12:50.540
That means it is manually created content plus additional content.

12:50.900 --> 12:56.540
Another example of that was WebDE.

12:58.420 --> 12:59.720
So this was...

13:00.540 --> 13:02.740
they were organizing the Internet, they said.

13:03.240 --> 13:10.260
So they had classified information, organized information, and quality

13:10.260 --> 13:13.360
checks on the links that are actually available there.

13:13.820 --> 13:17.740
And as a provider of information, you can submit information, you can

13:17.740 --> 13:21.460
submit websites to be listed in these directories.

13:21.580 --> 13:25.160
So this is something like the official catalog of information that is

13:25.160 --> 13:26.960
in some way quality checked.

13:27.260 --> 13:32.920
Whereas the catalogs of search engines are not quality checked, are

13:32.920 --> 13:38.380
just all the information you have or that you get access to is

13:38.380 --> 13:41.440
actually listed in those catalogs.

13:41.920 --> 13:44.880
And then certainly there are the hybrid search engines, which combine

13:44.880 --> 13:45.280
both.

13:45.540 --> 13:49.220
Where Yahoo again is a good example because they have search engines

13:49.220 --> 13:53.760
which automatically create catalogs, but also have some more organized

13:53.760 --> 13:55.700
and quality checked directories.

13:56.680 --> 13:59.060
So how do these search engines work?

13:59.160 --> 14:02.300
They have, as I said, they visit the major...

14:02.920 --> 14:08.300
or they visit the websites, the pages on all the websites regularly.

14:08.860 --> 14:12.700
This is done by programs called spiders or crawlers.

14:12.700 --> 14:16.100
That means we have here the internet and now you could think, well,

14:16.200 --> 14:19.260
this program is actually...

14:19.260 --> 14:25.020
this spider is actually visiting all these different nodes in this

14:25.020 --> 14:27.920
building or in this web of information.

14:28.520 --> 14:32.640
And so you could think as if a program would visit all these different

14:32.640 --> 14:32.960
nodes.

14:33.280 --> 14:34.380
One could do it that way.

14:34.460 --> 14:37.340
One could use mobile code for that, but we know we don't have to do

14:37.340 --> 14:37.600
that.

14:37.880 --> 14:44.280
We can just access all the websites and... but...

14:44.280 --> 14:50.500
by just entering all the different or checking all the different URLs

14:50.500 --> 14:53.500
for the website or the addresses.

14:54.840 --> 15:00.820
But it's obvious for every check of the website, we have to execute

15:00.820 --> 15:07.700
the HTTP protocol and access or communicate with the web server at the

15:07.700 --> 15:09.740
site where we would like to get some information.

15:09.740 --> 15:11.980
So we have to visit the page.

15:12.060 --> 15:14.600
That means retrieve the information from there.

15:15.080 --> 15:16.360
You have to read the page.

15:17.080 --> 15:19.860
And then in the page, you might follow other links.

15:20.440 --> 15:25.360
And then these links to these other pages may be within that site or

15:25.360 --> 15:28.500
at other sites will also be followed in that way.

15:29.600 --> 15:33.020
In this way, these spiders are crawling the web because they just

15:33.020 --> 15:36.740
follow all the links that they can actually access.

15:37.720 --> 15:40.220
And in this way, they get more and more information.

15:40.920 --> 15:44.400
And this is just one point that you have to discover information on

15:44.400 --> 15:44.760
the web.

15:45.120 --> 15:48.080
And then you have to make sure that the information that you list in

15:48.080 --> 15:52.140
your index or in your catalog actually is up to date.

15:52.240 --> 15:58.380
So you have to revisit the sites on a regular basis every month or two

15:58.380 --> 16:01.760
or maybe every three weeks, every five weeks, every eight weeks.

16:02.260 --> 16:07.680
This revisiting interval will depend on the frequency of change that

16:07.680 --> 16:08.920
you actually observe.

16:09.320 --> 16:12.320
So you are just visiting a certain web page.

16:12.400 --> 16:15.360
This is the time you visit that at regular intervals.

16:15.560 --> 16:18.680
If there is no change, then you increase the intervals.

16:19.180 --> 16:22.560
If there are more changes, then you have to decrease the intervals and

16:22.560 --> 16:28.200
visit it more often in order to have always updated current contents

16:28.200 --> 16:28.460
there.

16:31.120 --> 16:34.000
So we know how many websites there are.

16:34.020 --> 16:34.680
Quite a few.

16:35.880 --> 16:43.060
So Google, for example, some five, six years ago, had something like

16:43.060 --> 16:53.980
eight billion, that means ten to the nine, websites in its catalog.

16:56.280 --> 17:00.300
We will come back to that probably a bit later, but if we just make a

17:00.300 --> 17:04.340
simple calculation what that would mean if you have to revisit eight

17:04.340 --> 17:08.920
billion websites every day or every three weeks.

17:09.140 --> 17:10.720
Just every three weeks.

17:10.980 --> 17:14.420
What that means for the number of websites you have to visit per day

17:14.420 --> 17:18.300
and you know how long it takes to visit a server.

17:18.440 --> 17:22.500
If you look at the time it takes to execute a ping operation.

17:23.200 --> 17:28.880
A ping operation, like if you just want to go from one server to the

17:28.880 --> 17:31.460
other, just communicate.

17:33.160 --> 17:35.460
You just have to...

17:38.360 --> 17:40.280
You are counting the people here.

17:40.400 --> 17:40.820
What are you doing?

17:41.500 --> 17:41.620
No?

17:43.920 --> 17:44.540
Okay.

17:45.020 --> 17:51.340
So it's a huge number of websites that you have to visit and you know

17:51.340 --> 17:55.760
how long it takes to actually visit an individual site, how long it

17:55.760 --> 18:01.500
takes to access a webpage, and then you can simply calculate how much

18:01.500 --> 18:06.220
time you have to spend to visit all these websites or how much

18:06.220 --> 18:10.980
computing power you have to provide in order to support something like

18:10.980 --> 18:20.120
eight billion websites that always have to be up to date or content

18:20.120 --> 18:22.820
should not be older than at most three weeks.

18:23.680 --> 18:29.340
You always expect that it is the current information and then how much

18:29.340 --> 18:33.040
computing power you would have to provide in order to be able to do

18:33.040 --> 18:33.180
that.

18:33.240 --> 18:34.980
I don't want to go into details here.

18:35.280 --> 18:35.920
I'll do that later.

18:37.560 --> 18:38.960
So that's the spider.

18:39.240 --> 18:44.640
The spider is just checking the information and then the index is

18:44.640 --> 18:48.960
built, this catalog, and we know what an index is.

18:49.060 --> 18:53.920
If we have a book, at the end we have some listing and we have all

18:53.920 --> 19:00.060
kinds of words like some word like web or something and then we have

19:00.060 --> 19:03.980
here a listing of all the locations where this word actually is

19:03.980 --> 19:04.340
occurring.

19:04.500 --> 19:07.840
That essentially is an index, as you know it from every textbook,

19:08.480 --> 19:12.940
where you have an index at the end in order to retrieve very quickly

19:12.940 --> 19:18.780
the relevant locations where a certain word that you are interested in

19:18.780 --> 19:19.740
is actually occurring.

19:20.340 --> 19:27.580
So this is what has to be built and if you have 8 billion webpages,

19:27.940 --> 19:32.820
you have many, many words that might occur there.

19:33.860 --> 19:40.820
Certainly the number of words that are currently looked at is not that

19:40.820 --> 19:41.360
large.

19:41.660 --> 19:45.720
That's, by the way, an interesting information provided on the Search

19:45.720 --> 19:47.700
Engine Watch website.

19:47.940 --> 19:55.800
You can look up the most frequent search terms of today, yesterday, or

19:55.800 --> 19:59.720
the last week or things like that and in that way see what are the

19:59.720 --> 20:01.400
most common search queries.

20:01.940 --> 20:07.240
So you have to make sure that search queries are supported, are

20:07.240 --> 20:11.980
executed very fast, and so you need efficient data structures and

20:11.980 --> 20:14.020
access methods for such an index.

20:14.160 --> 20:22.360
To build up an index is a very complex and challenging task and it

20:22.360 --> 20:26.760
needs a lot of computing power to actually execute all the queries.

20:27.320 --> 20:30.480
And this is done, this executing the queries is done by the Search

20:30.480 --> 20:34.740
Engine software which has to analyze your query if it's just one word.

20:34.800 --> 20:38.240
It's simple, but if you have a sequence of words and maybe even

20:38.240 --> 20:43.880
complex search query, then this has to be analyzed adequately.

20:44.200 --> 20:45.580
This is the smallest task.

20:46.060 --> 20:49.360
Then you have to search the index for documents matching the query.

20:50.580 --> 20:55.400
The time for that depends on the efficiency of your data structures

20:55.400 --> 20:55.760
there.

20:56.720 --> 21:01.560
And then the software has to rank the matching documents in order of

21:01.560 --> 21:01.920
relevance.

21:01.980 --> 21:07.700
So you have to know something about relevance of the document for a

21:07.700 --> 21:08.360
certain query.

21:09.800 --> 21:16.020
Now, let us briefly look at what kind of measurements we would have to

21:16.020 --> 21:18.560
talk about the quality of information retrieval.

21:19.360 --> 21:24.640
So, information retrieval in general, which is much older than all the

21:24.640 --> 21:33.380
Search Engine activities, information retrieval is a very old subject.

21:34.320 --> 21:42.500
And there are two standard measures which are assessing the quality of

21:42.500 --> 21:43.520
information retrieval.

21:43.720 --> 21:45.960
One is called recall and the other is called precision.

21:45.960 --> 21:51.660
So recall means, assume you have a certain database of documents.

21:51.760 --> 21:53.600
So this is all the documents you have.

21:53.680 --> 21:55.540
Now you ask for a certain document.

21:55.680 --> 22:01.060
You ask for documents containing, let's say, words about the Karlsruhe

22:01.060 --> 22:02.120
Institute of Technology.

22:03.680 --> 22:06.400
Some documents will contain information on that.

22:06.540 --> 22:08.320
Some won't contain that information.

22:08.440 --> 22:15.300
So you can split up your database into your collection of documents

22:15.300 --> 22:18.300
into at least two subsets.

22:19.140 --> 22:22.780
One which is irrelevant, one which contains the relevant documents.

22:23.420 --> 22:27.400
Now this assumes that we can exactly say this document is relevant,

22:27.720 --> 22:28.760
that one is not relevant.

22:29.280 --> 22:34.220
Very often we don't have such a 0-1 decision, but we have a degree of

22:34.220 --> 22:34.700
relevance.

22:34.920 --> 22:39.580
But here I simplify that and assume that we say this is relevant and

22:39.580 --> 22:40.400
that is not relevant.

22:41.160 --> 22:45.200
And now you get, as a result of your query, you get a certain

22:45.200 --> 22:45.760
response.

22:45.940 --> 22:47.620
You get a certain number of documents.

22:48.580 --> 22:53.900
And the quality of that query, of that response to a query, can be

22:53.900 --> 22:55.520
measured in two ways.

22:56.160 --> 23:01.120
One is, well, you retrieved a certain number of documents and some of

23:01.120 --> 23:01.780
them are relevant.

23:03.320 --> 23:08.180
And you know in your database you may have more relevant documents.

23:08.400 --> 23:12.340
So you look at how many of those relevant documents are actually

23:12.340 --> 23:12.920
recorded.

23:12.920 --> 23:21.580
This is about the number of relevant retrieved documents in relation

23:21.580 --> 23:23.360
to all the relevant documents.

23:23.540 --> 23:27.840
How many of those relevant documents did you actually get in the

23:27.840 --> 23:28.860
response to your query?

23:30.920 --> 23:35.360
Another point is, how precise is the response to your query?

23:36.560 --> 23:42.040
How precisely did your search engine actually check whether the

23:42.040 --> 23:44.720
documents are relevant or not?

23:45.300 --> 23:49.040
And so what you now look at is, you have a certain number of retrieved

23:49.040 --> 23:49.440
documents.

23:49.680 --> 23:52.540
Here, this part of your documents is relevant.

23:53.080 --> 23:56.320
But you may also get other documents which are not relevant.

23:57.440 --> 24:04.320
And so you look at the number of, or the fraction of relevant

24:04.320 --> 24:09.640
retrieved documents with respect to the number of retrieved documents

24:09.640 --> 24:10.740
that you got.

24:10.940 --> 24:17.420
So here you look at how much irrelevant documents there actually are.

24:17.920 --> 24:25.140
Or you say, what is the quality of the response with respect to the

24:25.140 --> 24:26.800
percentage of relevant documents.

24:27.420 --> 24:32.840
And certainly, this is important to look at.

24:33.440 --> 24:37.440
And the problem is that there can be different strategies.

24:37.440 --> 24:41.160
You could say, well, I would like to provide a service which is always

24:41.160 --> 24:41.640
relevant.

24:42.100 --> 24:47.840
So I only return very few documents where I'm certain these documents

24:47.840 --> 24:49.060
are relevant.

24:49.820 --> 24:51.920
But then the recall will be small.

24:52.060 --> 24:56.160
If there is a huge number of documents which might be relevant, then

24:56.160 --> 25:03.440
if you are lazy, you just return one document which is relevant.

25:05.340 --> 25:10.580
And then you have a very precise response to the query because

25:10.580 --> 25:13.580
everything you return is relevant.

25:14.860 --> 25:21.180
But if you say, okay, I would like to have also a high recall, you

25:21.180 --> 25:24.100
could just, well, you could return all the documents.

25:24.720 --> 25:28.620
Then you have a very high recall because you have provided all the

25:28.620 --> 25:31.960
relevant documents, but it's not the task of the user to actually

25:31.960 --> 25:36.820
search through that huge number of documents to find out which ones

25:36.820 --> 25:38.300
are relevant and which ones are not.

25:38.960 --> 25:45.660
You can have a high recall but a very small precision and the task or

25:45.660 --> 25:48.860
challenge is to have high recall and high precision.

25:50.120 --> 25:55.100
And now since the decision on whether a document is relevant or not is

25:55.100 --> 26:03.060
not a simple 0-1 decision, you have to look at that more closely.

26:03.160 --> 26:05.160
We will do that a bit later.

26:05.500 --> 26:11.340
So you can easily achieve high recall or high precision but if you

26:11.340 --> 26:18.280
look at both criteria then you are closer to getting something which

26:18.280 --> 26:22.480
is measuring the real quality of your search engine.

26:23.200 --> 26:27.900
Now, let's briefly look at this notion of relevance.

26:28.420 --> 26:31.640
When would we say that a document is relevant for a query?

26:32.380 --> 26:38.000
So if we get a link to a document and we look at that document, then

26:38.000 --> 26:41.480
we have looked for a certain term, a search term, and then we

26:41.480 --> 26:46.840
certainly assume that there should be a match of that term.

26:46.980 --> 26:51.020
So this term that we looked at should appear in the document.

26:52.720 --> 26:55.860
And certainly it's nicer if it appears many times.

26:57.020 --> 26:59.100
So a number of query terms with matches.

26:59.460 --> 27:07.620
Or maybe we have a list of terms not just one term but some list of k

27:07.620 --> 27:08.680
query terms.

27:09.440 --> 27:13.820
And certainly you would like to see as many as possible of those terms

27:13.820 --> 27:17.560
in your documents that are presented to you as being relevant.

27:18.200 --> 27:21.680
So the number of query terms with matches certainly is an important

27:21.680 --> 27:21.760
point.

27:22.500 --> 27:24.660
But then also the number of matches.

27:24.740 --> 27:28.260
If you have one word which is appearing several times, the document

27:28.260 --> 27:32.180
probably will be more relevant than a document where this term appears

27:32.180 --> 27:32.860
only once.

27:34.260 --> 27:40.440
Another point is where do we actually notice those terms?

27:41.020 --> 27:46.720
If in the first line of the document we see one or several of these

27:46.720 --> 27:48.340
query terms, we are happy.

27:48.460 --> 27:49.960
It must be a very relevant document.

27:50.920 --> 27:54.080
This is an indication of relevance for a term.

27:54.140 --> 28:01.380
If it appears in the first lines of a document, it should be more

28:02.320 --> 28:06.100
relevant than terms which just appear somewhere in the end.

28:08.380 --> 28:12.800
So... or you could say if at the end you have the conclusion of a

28:12.800 --> 28:16.840
paper or something so maybe the terms appearing there could again be

28:16.840 --> 28:21.480
relevant but something which is just in the middle somewhere will not

28:21.480 --> 28:22.160
be that relevant.

28:22.300 --> 28:25.540
So this all are indications of relevance.

28:25.660 --> 28:29.640
The location, the number of matches, the number of query terms which

28:29.640 --> 28:37.540
actually match and then certainly the quality of the matches.

28:38.100 --> 28:46.780
If you look for a certain term like match and you also get a link

28:46.780 --> 28:52.400
where you have a word like this well, you would not really think that

28:52.400 --> 28:53.040
that is relevant.

28:53.860 --> 28:57.020
But it's just very close to the term that you looked for.

28:57.120 --> 29:01.700
Just one misspelled letter there.

29:01.860 --> 29:05.340
So you have one additional letter very close to the term you actually

29:05.340 --> 29:10.080
looked for and sometimes you are very interested in actually getting

29:10.080 --> 29:14.520
hits for words that are very similar to the word that you are actually

29:14.520 --> 29:15.240
interested in.

29:16.040 --> 29:21.820
And so the question whether you are only looking for complete matches

29:21.820 --> 29:27.860
or also for partial matches is important because if you allow for

29:27.860 --> 29:33.040
looking for partial matches then you get more documents back.

29:33.760 --> 29:38.060
Maybe you have not completely specified the term that you are actually

29:38.060 --> 29:41.400
interested in and that way you get the really relevant documents.

29:42.240 --> 29:46.600
Then you might have misspelled your query.

29:47.060 --> 29:51.800
You notice when you put queries to Google and you misspelled the

29:51.800 --> 29:58.080
search term usually Google suggests certain other words which might be

29:58.080 --> 30:00.600
the intended query term.

30:00.960 --> 30:04.360
Then they ask isn't that the actual query term that you looked for?

30:05.200 --> 30:08.320
So this is something looking or considering misspellings.

30:08.640 --> 30:14.300
This all has to be done by the search engine software.

30:14.800 --> 30:19.400
Then there may be explicit information on relevance.

30:21.340 --> 30:25.380
Explicit information, direct information on relevance may be that you

30:25.380 --> 30:29.460
have a certain header of your document which is not visible directly

30:30.180 --> 30:34.480
in the web browser but is information contained in the file.

30:34.640 --> 30:37.520
You know that you have meta tags in your documents and you can

30:37.520 --> 30:41.780
explicitly specify their keywords and things like that and in that way

30:41.780 --> 30:49.880
enter certain keywords that are important for search engines to

30:49.880 --> 30:57.460
evaluate such that queries will also be linked to that document even

30:57.460 --> 31:00.900
if a certain term does not appear directly in that document.

31:01.760 --> 31:07.820
So this might be important if for example you are having a certain

31:08.580 --> 31:13.440
term and this term is also known under different names.

31:13.540 --> 31:17.360
You have synonyms for that and you could just put certain synonyms for

31:17.360 --> 31:23.080
important words into your meta tags and so in this way you could list

31:23.080 --> 31:29.580
here many different terms and in that way enhance the probability that

31:29.580 --> 31:34.440
your document actually will get listed as the result of a query.

31:34.440 --> 31:39.480
So this explicit information in the meta tags is important and

31:39.480 --> 31:44.720
obviously the knowledge of the method of evaluation will influence the

31:44.720 --> 31:47.340
way you present your document.

31:48.520 --> 31:53.680
And also these statements on relevance are not unique.

31:53.860 --> 31:55.500
They depend on the method of evaluation.

31:55.940 --> 32:02.040
How you actually combine all these different aspects into some rank.

32:02.040 --> 32:03.000
There are others.

32:03.400 --> 32:10.240
I did not mention all the things but I should at least indicate it

32:10.240 --> 32:11.060
briefly.

32:11.700 --> 32:16.960
If you have a document and there are many more documents which are

32:16.960 --> 32:22.960
linking to that page then usually this is also considered to be an

32:22.960 --> 32:23.980
indication of relevance.

32:24.300 --> 32:27.380
This actually is the major indicator of relevance for Google.

32:28.540 --> 32:36.000
It says well, if a page is actually very popular in the number of

32:36.000 --> 32:40.260
links that are pointing to that page then this must be a very relevant

32:40.260 --> 32:40.640
page.

32:41.340 --> 32:44.140
And if you know that, you know how to set up your web page.

32:44.280 --> 32:46.460
Or how to create links to your page.

32:47.460 --> 32:51.480
There are services available creating links to your page such that you

32:51.480 --> 32:53.820
get a high popularity index.

32:54.640 --> 32:57.700
But this certainly has to be justified.

32:57.700 --> 33:03.820
So this is always this trade-off between or this problem that you

33:03.820 --> 33:04.620
would like to get.

33:05.580 --> 33:09.220
You know how ranking is done so you know what you have to do in order

33:09.220 --> 33:10.960
to get to a higher location.

33:11.680 --> 33:13.140
But it has to be justified.

33:13.300 --> 33:14.520
It has to be an adequate ranking.

33:14.720 --> 33:17.080
It has to do with marketing.

33:17.700 --> 33:20.180
We are not talking about marketing, we are talking about algorithms.

33:20.840 --> 33:26.440
But certainly in marketing people also use algorithms.

33:27.640 --> 33:31.380
Another point which I would like to briefly mention I just told you

33:31.380 --> 33:33.660
about the task of the spiders and so on.

33:33.720 --> 33:34.920
They visit all the web pages.

33:35.680 --> 33:40.380
Now assume you are setting up a very modern web page or website and

33:40.380 --> 33:42.660
all you have there are dynamic contents.

33:42.880 --> 33:48.220
You have certain services which will create contents depending on the

33:48.220 --> 33:51.420
personal choices of the person who is visiting that web page.

33:52.480 --> 33:53.860
That is a problem.

33:54.120 --> 33:59.600
These web pages will never be indexed by a search engine because an

33:59.600 --> 34:03.180
automatic crawler can only notice oh there are certain services

34:03.180 --> 34:10.240
certain scripts that actually can access information but since there

34:10.240 --> 34:14.700
is no person behind that these contents which can be dynamically

34:14.700 --> 34:19.840
adjusted will never be indexed it will never enter the search engines

34:19.840 --> 34:22.480
on the catalogs and the indexes and so on.

34:23.140 --> 34:27.380
And so if you put all your information in a very fancy way using

34:27.380 --> 34:33.460
dynamic techniques for presenting your content and your website this

34:33.460 --> 34:35.840
information will never be available to other places.

34:36.420 --> 34:42.040
So this is you always have to add extra information either in meta

34:42.040 --> 34:48.160
tags or on static web pages which can actually be listed or checked by

34:49.140 --> 34:54.360
search engines, by the spiders and then indexed in or entered into

34:54.360 --> 34:56.320
these catalogs.

34:57.040 --> 35:03.420
So this is a lot of extra information on this slide where I just

35:03.420 --> 35:07.660
wanted to tell you what actually makes a document relevant for a

35:07.660 --> 35:07.920
query.

35:08.900 --> 35:13.180
The next question is, we'll come back to the notion of relevance a bit

35:13.180 --> 35:13.380
later.

35:13.860 --> 35:14.740
What is a query?

35:14.740 --> 35:18.220
When we talk about queries, so what is actually in there?

35:18.620 --> 35:23.680
There are many different ways of actually stating a query.

35:24.600 --> 35:32.820
You can actually put in some natural language or some phrase in normal

35:32.820 --> 35:36.060
language and this will be interpreted.

35:36.240 --> 35:42.540
But you could also just enter a few terms and so the query normally

35:42.540 --> 35:44.300
consists of something like this.

35:44.420 --> 35:46.760
Some people have analyzed all the queries.

35:47.220 --> 35:49.160
2.35 terms in a query.

35:49.580 --> 35:52.260
Don't know how many terms you put in a query when you search for

35:52.260 --> 35:52.620
something.

35:53.880 --> 35:56.920
I think this may increase slightly.

35:57.380 --> 36:01.240
If you type in something again at Google, you get suggestions what you

36:01.240 --> 36:03.420
might actually be interested in.

36:03.920 --> 36:09.980
And then you get certain numbers of terms, maybe two or three, but

36:09.980 --> 36:11.180
usually not more.

36:11.920 --> 36:14.900
So 2.35 actually is quite a large number.

36:15.260 --> 36:20.220
I don't know what your habit is when you ask something in a query.

36:20.600 --> 36:26.500
So let's assume we want to search for documents containing Universität

36:26.500 --> 36:27.060
Karlsruhe.

36:28.000 --> 36:32.440
Nobody knows what that is, but maybe there's still something around

36:32.440 --> 36:35.200
there or the name Algorithmus.

36:35.240 --> 36:36.280
How could we do that?

36:37.180 --> 36:41.660
So now we have to decide what we actually want to do.

36:41.740 --> 36:45.660
We want to search for all documents containing these words.

36:46.560 --> 36:53.860
First of all, we have to notice a document here is essentially just a

36:53.860 --> 36:55.220
sequence of symbols.

36:56.020 --> 37:00.800
So we could have here a very long sequence of symbols.

37:01.120 --> 37:03.360
It's a sequence of symbols over some alphabet.

37:03.860 --> 37:10.060
We know how to talk about languages, about words, and so on.

37:10.240 --> 37:16.520
So we could simply formalize that and say there's a match for a query.

37:17.500 --> 37:21.320
For example, the query A that we have here, Universität Karlsruhe.

37:21.860 --> 37:26.280
If we have a document D, which is an element of this set.

37:26.340 --> 37:27.200
What is that set?

37:27.640 --> 37:33.600
It is a set of words starting with any symbol from this alphabet

37:33.600 --> 37:40.260
sigma, then having the letters Universität blank Karlsruhe, and then

37:40.260 --> 37:42.660
again some sequence of letters.

37:43.240 --> 37:51.660
That means this term here occurs somewhere in some document, in some

37:51.660 --> 37:52.100
word.

37:53.220 --> 37:59.620
Now this should remind you of something we have looked at if you are

37:59.620 --> 38:03.600
students of business engineering or if you are students of other

38:03.600 --> 38:06.660
programs, then you have looked at other courses.

38:07.300 --> 38:08.800
So this is just regular set.

38:09.120 --> 38:14.300
Regular set we know we can analyze using finite automata, so if we

38:14.300 --> 38:19.920
would like to execute such a query, we could just run, or let some

38:19.920 --> 38:24.780
finite automata, some state machine actually analyze all the documents

38:24.780 --> 38:29.680
and find out which documents are acceptable to that finite state

38:29.680 --> 38:29.920
machine.

38:30.880 --> 38:35.200
Then we have actually, this actually is the algorithm to build this

38:35.200 --> 38:41.980
finite state machine which will find out whether a document contains a

38:41.980 --> 38:44.460
certain pattern.

38:45.300 --> 38:48.340
This is one approach that you could look at.

38:48.440 --> 38:54.420
So here, the query corresponds to a regular expression we have, we can

38:54.420 --> 38:59.440
actually find out whether there is a match if we just execute this

38:59.440 --> 39:00.320
finite automaton.

39:01.120 --> 39:04.740
It's not just any finite automaton, we have to do that in a reasonable

39:04.740 --> 39:09.660
way, but definitely we know what kind of system that is that we have

39:09.660 --> 39:10.140
to look at.

39:11.280 --> 39:17.900
And it certainly means every query corresponds to a finite automaton.

39:18.420 --> 39:23.540
That means for every query, before we can execute that on a set of

39:23.540 --> 39:27.340
documents, we have to generate that automaton.

39:27.880 --> 39:30.560
Well, this can be done easily in an automated way.

39:31.840 --> 39:36.280
And we will see how we can actually define or design very efficient

39:36.280 --> 39:39.900
algorithms for pattern matching in documents.

39:40.960 --> 39:48.200
The other assumption is that your document is represented within an

39:48.200 --> 39:48.740
index.

39:49.220 --> 39:52.880
That means you have a data structure which allows for efficient

39:52.880 --> 39:55.660
retrieval of all the relevant words of a document.

39:56.240 --> 40:01.660
And so there, you would not analyze the document, you would just go

40:01.660 --> 40:07.180
into the index, search for the words for University of Karlsruhe, and

40:07.180 --> 40:12.200
then follow the link that is showing you all the different documents,

40:12.400 --> 40:13.900
but this is actually occurring.

40:14.260 --> 40:20.980
But this certainly means we have to analyze the documents before we

40:20.980 --> 40:24.360
actually execute the queries, and this is what I mentioned the search

40:24.360 --> 40:28.000
engines actually do, that they look at all the different websites and

40:28.000 --> 40:29.620
analyze the websites.

40:30.400 --> 40:34.860
But certainly for that they have to find out what is actually the list

40:34.860 --> 40:38.460
of relevant words that might be looked at later on by some query.

40:39.400 --> 40:44.040
So if you are interested in full text search, you actually might have

40:44.040 --> 40:46.780
to go through all those documents.

40:47.520 --> 40:53.380
And you know, if you, for example, search through all the email

40:53.380 --> 40:55.040
messages that you have on your computer.

40:55.380 --> 40:59.760
If you don't have an index, it takes quite some time, because the

40:59.760 --> 41:05.200
standard procedure would be to perform it following assumption one,

41:05.800 --> 41:11.440
that you have actually to build or to execute a query on all the email

41:11.440 --> 41:14.500
messages that you have and search for the occurrence of certain words.

41:14.960 --> 41:20.800
If you have an index on your list of, on your database of email

41:20.800 --> 41:23.380
messages, then it's much faster.

41:23.580 --> 41:27.980
You just have to access the index, but you have to build that index,

41:28.020 --> 41:29.400
and this takes quite a long time.

41:30.700 --> 41:36.000
So this is just following the different approaches to searching for

41:36.000 --> 41:37.040
information in documents.

41:37.780 --> 41:41.480
We will look at both ways of analyzing documents.

41:41.760 --> 41:46.420
I will present to you ways of actually looking for patterns in

41:46.420 --> 41:47.920
documents, so full-text search.

41:48.440 --> 41:52.960
We will also briefly look at how we can actually build up a search

41:52.960 --> 41:56.340
structure for the words within a document.

41:58.120 --> 42:00.720
Now, you remember what a regular expression is?

42:01.740 --> 42:06.420
You know that this is the standard notion.

42:07.080 --> 42:13.680
We have certain symbols that are regular expressions, so the symbol

42:13.680 --> 42:17.860
for the empty set is a regular expression, or the elements of the

42:17.860 --> 42:19.440
alphabet are regular expressions.

42:19.660 --> 42:23.220
And if you have two regular expressions, then you know that you can

42:23.220 --> 42:28.300
combine them with plus, dot, and the star.

42:28.520 --> 42:33.240
So sum, product, and iteration are the three operations that we can

42:33.240 --> 42:38.440
form there, whereas these are essentially only sequences of some

42:38.440 --> 42:44.220
letters or some symbols, and then we name them regular expressions and

42:44.220 --> 42:46.280
we have to interpret them adequately.

42:46.880 --> 42:47.560
You know all that.

42:47.900 --> 42:53.480
Now, certainly we don't want if you write a query, sometimes you have

42:53.480 --> 42:58.560
these notation available and you can write something, for example,

42:59.040 --> 43:04.380
write a question mark after a certain term, which means it might

43:04.380 --> 43:08.260
occur, but it not necessarily occurs there.

43:08.980 --> 43:13.360
Or you say, you can have the empty word there, or you can say, okay, I

43:13.360 --> 43:18.080
just want to specify that some of the letters in between, for example,

43:18.340 --> 43:20.300
A to F, will appear there.

43:20.980 --> 43:25.540
Then you can specify it in this way, which is simpler than specifying

43:25.540 --> 43:27.940
it as a sum of all the individual symbols.

43:28.800 --> 43:32.080
Or you could say, well, I would like to look at all the documents

43:32.080 --> 43:35.000
where a certain term appears at most k times.

43:35.000 --> 43:38.140
This would be something like this.

43:38.600 --> 43:41.800
Or you say, I would like to look for documents where a certain term

43:41.800 --> 43:43.600
appears at least k times.

43:43.940 --> 43:47.300
And you could specify it like that, which would be much more difficult

43:47.300 --> 43:51.800
to specify if you would do it in a different way.

43:51.980 --> 43:57.680
So this is just extensions, and you know that in many queries you can

43:57.680 --> 44:01.960
actually specify search terms like that using this notation from

44:01.960 --> 44:04.420
regular expressions.

44:05.140 --> 44:09.020
So we could, for example, I don't assume that you would do that

44:09.020 --> 44:13.980
actually, but one could specify a search where we look for all kinds

44:13.980 --> 44:18.800
of variants of the word algorithmos, and this would occur at least

44:18.800 --> 44:22.820
five times, in the following way that it should start with any symbol

44:22.820 --> 44:28.100
from sigma, it might be followed by any symbol from sigma, and then it

44:28.100 --> 44:32.920
should either start with a capital or small a, and then have here a

44:32.920 --> 44:37.880
certain word in there, and then we would have to have either the

44:37.880 --> 44:42.540
ending s, or us, or en, or ic, or isch.

44:43.020 --> 44:47.680
All different variants of algorithmos, or algorithmen, or

44:47.680 --> 44:49.380
algorithmisch, or whatever.

44:51.020 --> 44:56.240
And so this here might occur, but does not necessarily occur.

44:56.480 --> 45:02.460
It's a potential ending, and there could be anything following that,

45:03.040 --> 45:06.520
and we would assume it should be there at least five times.

45:07.260 --> 45:12.180
So it means there are five occurrences, at least five occurrences of

45:12.180 --> 45:15.500
such a term in between.

45:16.740 --> 45:23.500
A way of specifying a more complex, or more general query, but this

45:23.500 --> 45:28.620
would be something for computer scientists who would be familiar with

45:28.620 --> 45:32.180
this way of specifying queries, but normally you don't do that if you

45:32.180 --> 45:35.980
have something for everybody, so there we have different ways of

45:35.980 --> 45:37.040
specifying queries.

45:38.920 --> 45:44.860
And so internally, this can be done in this way, but this is usually

45:44.860 --> 45:47.520
presented to the user in a different way.

45:49.460 --> 45:56.760
So normally we have certain Boolean queries where we just search for,

45:57.360 --> 46:03.260
for example, conjunctive or disjunctive combinations of words.

46:03.380 --> 46:08.440
We would say, okay, I list a certain number of words, so for example,

46:08.700 --> 46:12.200
if I would have here these words, what is a regular expression?

46:13.280 --> 46:18.100
This is in a standard way interpreted as if you would search for the

46:18.100 --> 46:20.120
occurrence of any of those words.

46:20.540 --> 46:21.940
At least one of those words.

46:22.440 --> 46:26.100
Where you could say, okay, is and if are not really relevant.

46:26.880 --> 46:33.240
So you would delete those words, but you would assume you have here,

46:33.560 --> 46:35.280
and what also is not that important.

46:35.660 --> 46:39.620
So you would have here a search for at least one of those that are

46:39.620 --> 46:40.380
occurring in a list.

46:40.620 --> 46:44.380
Or you could make that more explicit and say you explicitly write

46:44.380 --> 46:50.340
there a disjunctive sequence of terms, or you combine it with an and,

46:50.460 --> 46:52.060
and then you have a conjunctive search.

46:52.300 --> 46:55.760
Or you could actually have more boolean operations in there, and then

46:55.760 --> 46:56.840
have more complex queries.

46:57.040 --> 47:00.800
Usually if you look at more advanced search inputs, then you can

47:00.800 --> 47:02.500
specify exactly those things.

47:03.540 --> 47:11.420
Now I have made a few just for examples, a few search queries where

47:11.420 --> 47:15.640
you could so where you see what actually happens if you search for

47:15.640 --> 47:16.280
certain words.

47:16.720 --> 47:21.340
Actually I did not only in Google, I looked at this was interesting,

47:21.820 --> 47:25.020
that one of the first search engines was AltaVista.

47:26.320 --> 47:32.720
Still like AltaVista, and so I entered, or I searched at AltaVista,

47:33.680 --> 47:40.180
and actually what is happening is that the search engine of AltaVista

47:40.180 --> 47:42.540
now is the search engine used by Yahoo.

47:43.760 --> 47:49.680
So it's still presented under the name of AltaVista, but if you ask a

47:49.680 --> 47:54.180
query there, you get a link which is just a Yahoo link.

47:55.680 --> 47:59.520
And now I think this is interesting.

47:59.700 --> 48:05.280
I updated that last night, and so this is different every year.

48:06.100 --> 48:10.100
I have for comparison, I just left there the indicator of the year

48:10.100 --> 48:10.880
2007.

48:11.740 --> 48:18.660
I could have updated that from the data I had last year, but I think

48:18.660 --> 48:19.340
it's...

48:19.940 --> 48:23.420
it tells the story that I wanted to present.

48:24.280 --> 48:29.420
So, first of all, here is a query which could be simplified without

48:29.420 --> 48:34.560
listing all the or's in there, but here I wanted to just indicate I'm

48:34.560 --> 48:38.060
interested in one of the words that are listed here Angewandte

48:38.060 --> 48:40.040
Informatik Universität Kassel.

48:40.720 --> 48:46.820
And you notice that at AltaVista you had 33 million pages that are

48:46.820 --> 48:47.100
listed.

48:47.640 --> 48:49.860
At Google you have 199 million.

48:50.840 --> 48:51.520
Perfect.

48:51.660 --> 48:55.120
And now we can check all these pages and find out which are relevant

48:55.120 --> 48:56.060
and which are not relevant.

48:57.420 --> 48:59.640
Probably most of them will be irrelevant.

49:01.900 --> 49:04.060
2007 I had 88 million.

49:04.520 --> 49:06.120
So something in between.

49:08.580 --> 49:14.360
I had not listed here whether it was Google or Yahoo search.

49:15.020 --> 49:16.300
Like these 88 million.

49:16.700 --> 49:19.220
But just to show you that there are differences in there.

49:19.880 --> 49:23.940
Then if I look for all the words in...

49:23.940 --> 49:25.840
all these four words should occur.

49:26.440 --> 49:28.540
Angewandte Informatik Universität Kassel.

49:29.040 --> 49:35.800
Then I have 36,000 pages at AltaVista 201,000 at Google.

49:38.040 --> 49:38.840
Well.

49:39.660 --> 49:43.380
And in 2007 I had 268,000.

49:44.780 --> 49:45.860
Even more.

49:46.520 --> 49:50.860
You would assume that the number of pages has increased from 2007.

49:51.560 --> 49:55.480
Maybe it has decreased because we don't have any more Universität

49:55.480 --> 49:57.600
Kassel but we have Kassel Institute of Technology.

49:58.100 --> 50:00.440
Maybe that certain pages just disappeared.

50:01.060 --> 50:06.400
But I don't know why that happens but it just reflects the information

50:06.400 --> 50:09.560
that is available in the catalogs of those search engines.

50:09.720 --> 50:10.860
And that's the important point.

50:11.360 --> 50:14.460
You only get the information that is available in those catalogs.

50:15.700 --> 50:21.820
Then I looked for Angewandte Informatik and Kassel and not Mathematik.

50:24.080 --> 50:25.980
And then this is reduced.

50:26.500 --> 50:31.080
Just 17,000 pages here and only 29,600 at Google.

50:32.980 --> 50:36.600
And it had been 41,000 in 2007.

50:37.880 --> 50:38.820
I don't...

50:38.820 --> 50:44.880
I have no indication on how many of those listed or these numbers

50:44.880 --> 50:47.520
actually refer to relevant pages.

50:47.700 --> 50:50.540
It's at least the number of hits that they have in the index.

50:51.460 --> 50:52.720
Or if I looked under...

50:52.720 --> 50:55.260
This is the third way of looking for...

50:55.260 --> 50:59.600
or another way of looking for information if we are interested in an

50:59.600 --> 51:00.940
exact phrase.

51:02.320 --> 51:07.800
Then here we see, okay, Angewandte Informatik Kassel, just 117 pages

51:07.800 --> 51:12.240
at AltaVista and 31,000 at Google.

51:14.880 --> 51:15.880
This is strange.

51:16.760 --> 51:18.100
This is very strange.

51:19.560 --> 51:19.840
Yeah?

51:20.460 --> 51:21.580
It's really strange.

51:21.840 --> 51:24.220
Because I did that last night.

51:24.220 --> 51:32.470
I looked for this one and now I also look for this.

51:34.750 --> 51:41.550
And definitely every page that has a listing which contains Angewandte

51:41.550 --> 51:49.770
Informatik Kassel is containing Angewandte and Informatik and Kassel.

51:50.290 --> 51:57.470
And we got 29,600 hits at Google but for the string Angewandte

51:57.470 --> 52:01.430
Informatik Kassel, which should be a subset of the documents, we got

52:01.430 --> 52:03.050
31,300 at Google.

52:06.180 --> 52:07.000
This is strange.

52:07.660 --> 52:09.020
Something must be wrong there.

52:09.860 --> 52:11.040
But this happens.

52:12.160 --> 52:12.400
Yes?

52:12.600 --> 52:13.240
...

52:16.900 --> 52:17.580
Okay.

52:18.540 --> 52:18.900
Maybe.

52:19.400 --> 52:20.020
You're right.

52:20.880 --> 52:23.560
But yes.

52:23.560 --> 52:23.660
Yes.

52:23.960 --> 52:24.460
You're right.

52:24.920 --> 52:25.220
Thanks.

52:26.060 --> 52:26.460
You're right.

52:27.000 --> 52:27.920
This can happen.

52:28.080 --> 52:33.020
So definitely I have this part here so maybe that some of those here

52:33.020 --> 52:33.940
contain Mathematik.

52:34.040 --> 52:34.440
You're right.

52:34.560 --> 52:37.580
So my conclusion was wrong.

52:38.140 --> 52:39.160
This is still adequate.

52:39.400 --> 52:39.920
May well be.

52:40.160 --> 52:40.720
You have another question?

52:46.090 --> 52:47.250
They are very strange.

52:47.670 --> 52:48.170
Yes.

52:49.130 --> 52:50.170
But things like that happen.

52:52.110 --> 52:58.530
I do this every time I teach this course and I also have a few other

52:58.530 --> 53:03.850
test queries that I always perform and do that at different search

53:03.850 --> 53:08.890
engines and the results are very different and sometimes I have very

53:08.890 --> 53:15.850
strange results which indicate that certain things well indicate that

53:15.850 --> 53:20.730
these algorithms are not always executed in an exact way.

53:21.550 --> 53:23.990
Some things are in some way erratic.

53:24.850 --> 53:29.090
It's always depending where the query actually is executed.

53:29.690 --> 53:32.690
And certainly it's always the case that if you execute these queries

53:32.690 --> 53:38.970
here in Germany or if you are here or when you execute that query at

53:38.970 --> 53:43.270
some other location where you connect to the network from a different

53:43.270 --> 53:47.230
location, you get different results because you will be located to

53:47.230 --> 53:51.450
different catalogs and they have different content there.

53:51.670 --> 53:51.990
Yes.

54:06.420 --> 54:06.980
Maybe.

54:07.580 --> 54:07.940
Yes.

54:08.140 --> 54:10.280
But I think I did not check that.

54:10.680 --> 54:14.800
I just put it in there last night, just that query.

54:15.200 --> 54:18.100
I could have checked for the advanced search in Google and there you

54:18.100 --> 54:20.700
can search exactly for the phrase.

54:21.200 --> 54:26.060
I did not do that explicitly, so you may check whether you get similar

54:26.060 --> 54:26.800
results or not.

54:27.280 --> 54:31.260
But I just like this observation nevertheless is very valid.

54:31.380 --> 54:34.300
So definitely thanks for that remark.

54:34.420 --> 54:39.780
Definitely the conclusion here that this was not correct was a false

54:39.780 --> 54:40.320
observation.

54:41.020 --> 54:47.720
So definitely maybe that it's just the difference that this extra term

54:47.720 --> 54:52.960
not mathematique is reducing the number of pages.

54:53.200 --> 54:54.300
It should reduce it, definitely.

54:55.160 --> 54:55.340
OK.

54:56.260 --> 54:59.900
I just wanted to indicate to you that those large numbers anyway,

55:01.220 --> 55:03.640
these numbers are much too large.

55:04.080 --> 55:08.200
What kind of information do we actually get from that if I have 33

55:08.200 --> 55:10.940
million or 88 million listings?

55:11.100 --> 55:12.240
I never look at all these.

55:13.500 --> 55:20.480
And if you go... I did not do that, but if you ask the same queries to

55:20.480 --> 55:25.220
MetaCrawler then you will get much smaller results.

55:26.060 --> 55:28.820
Because MetaCrawler is looking at...

55:28.820 --> 55:34.760
is sending a query to a list of search engines and is then extracting

55:34.760 --> 55:38.100
the relevant information from the responses of these different search

55:38.100 --> 55:38.480
engines.

55:39.640 --> 55:43.940
And in that way only providing to you a subset of the relevant

55:43.940 --> 55:50.280
documents that are sent to you as a response from the individual

55:50.280 --> 55:51.120
search engines.

55:51.880 --> 55:56.140
And in that way they always present to you a smaller list of documents

55:56.780 --> 55:58.980
but it should be those that are more relevant.

56:00.100 --> 56:01.960
So everybody should use MetaCrawler.

56:02.320 --> 56:03.140
I don't do it.

56:04.540 --> 56:09.840
But one could do it and then you should get more relevant documents.

56:11.720 --> 56:18.420
And documents where they don't provide you with millions of hits or at

56:18.420 --> 56:24.520
least don't tell you they have that many relevant documents there.

56:25.900 --> 56:30.100
So I just wanted to show you that it's a difficult topic to talk about

56:30.100 --> 56:32.040
how we can actually retrieve information.

56:32.640 --> 56:36.280
Another point is I said we would like to look for similar words.

56:36.780 --> 56:41.860
Now what does this actually mean to look for similar words?

56:43.400 --> 56:53.640
So we look for something like Hausaufgabe or Hausarbeit or Hausaufgabe

56:53.640 --> 56:55.260
or Heimarbeit.

56:55.860 --> 56:57.140
Very similar words.

56:57.780 --> 57:02.620
You could say at least Hausaufgabe and Hausaufgabe are almost the

57:02.620 --> 57:02.900
same.

57:04.480 --> 57:09.480
But for a search engine which is analyzing those words, very

57:09.480 --> 57:09.880
different.

57:10.680 --> 57:12.800
We immediately see it's the same meaning.

57:13.240 --> 57:14.900
But how can a search engine do that?

57:15.000 --> 57:18.880
Or if we look for Stadt, we should also look for maybe for documents

57:18.880 --> 57:19.820
containing Städte.

57:20.220 --> 57:21.160
What about this?

57:21.300 --> 57:23.620
Is there Stadt with double T and not DT?

57:24.400 --> 57:25.420
Simple misspelling.

57:25.980 --> 57:27.020
Completely different meaning.

57:27.240 --> 57:30.500
Maybe you are also interested in something like that or maybe not.

57:31.180 --> 57:36.400
Or if you look at the typical misspellings of Karlsruhe, very similar.

57:37.300 --> 57:38.960
But how do you measure that similarity?

57:40.720 --> 57:48.080
So one computer science way of doing that is just to look at the two

57:48.080 --> 57:48.560
words.

57:48.860 --> 57:49.920
So here we have a word.

57:50.460 --> 57:51.440
There we have a word.

57:51.760 --> 57:54.300
We just compare the different symbols.

57:55.100 --> 57:59.420
And if we have a difference, if here there's an A and there's a B,

58:00.000 --> 58:01.680
then we would say that's a difference.

58:01.780 --> 58:04.860
We count the number of positions where certain words are differing.

58:05.520 --> 58:08.860
Then we have the Hemming distance of two words.

58:09.700 --> 58:12.700
Standard notion from coding theory.

58:13.160 --> 58:18.460
We know if we talk about faults in codes, we talk about the Hemming

58:18.460 --> 58:22.740
distance and we can characterize the ability to tolerate certain

58:22.740 --> 58:30.960
faults by just looking at the Hemming distance in that code word.

58:31.060 --> 58:33.820
But here we talk about similarity of words.

58:34.580 --> 58:38.420
So if we look at the Hemming distance of Hausarbeit and Heimarbeit,

58:38.980 --> 58:45.400
the Hemming distance is three because here A-U-S is just replaced with

58:45.400 --> 58:46.520
E -I-M.

58:47.760 --> 58:49.160
So Hemming distance is three.

58:49.820 --> 58:55.280
If we look at Karlsruhe and Karlsruhe, the R here is missing.

58:56.340 --> 59:01.540
But that means that at all these positions we have mismatches.

59:02.020 --> 59:05.140
The R is missing, so instead of the R, we have an L.

59:05.480 --> 59:07.500
Instead of the L, we have an F, and so on.

59:08.320 --> 59:12.720
So a very large Hemming distance, but they are very similar.

59:13.240 --> 59:16.460
So this should be something which we should also consider.

59:17.100 --> 59:21.860
That's why we look at the editing distance, which is the number of

59:21.860 --> 59:26.920
editing operations that are needed to get from one word to the other

59:26.920 --> 59:27.240
word.

59:28.160 --> 59:31.780
So if we type something, how do we actually get from one word to the

59:31.780 --> 59:31.920
other?

59:32.120 --> 59:35.120
So how many deletions do we have to make?

59:35.400 --> 59:37.280
How many insertions of symbols?

59:37.280 --> 59:39.500
How many symbols have to be replaced?

59:40.200 --> 59:41.040
Or switched?

59:41.760 --> 59:43.920
Sometimes we just switch two symbols.

59:46.000 --> 59:49.340
Now the question is, what are the operations that are available to us?

59:50.160 --> 59:55.480
If I can just delete and insert, I have more operations than if I

59:55.480 --> 59:58.440
would be able to replace or switch something.

59:59.080 --> 01:00:04.540
So we have to look at the allowed operations, and then we count the

01:00:04.540 --> 01:00:08.080
number of operations that we actually have to use in order to

01:00:08.080 --> 01:00:10.020
transform one word into the other.

01:00:10.680 --> 01:00:13.380
And so if we look at the editing distance between Hausarbeit and

01:00:13.380 --> 01:00:15.160
Heimarbeit, it's the same as before.

01:00:15.460 --> 01:00:21.620
At least if we assume that we have replacements as operations, so one

01:00:21.620 --> 01:00:27.200
replacement is one operation, then we can replace A-U-S with E-I-M,

01:00:27.640 --> 01:00:29.400
and we have an editing distance of three.

01:00:29.800 --> 01:00:33.620
If we would have just insertions and deletions, the editing distance

01:00:33.620 --> 01:00:37.920
would be six, because we would have to delete three symbols and insert

01:00:37.920 --> 01:00:38.500
three symbols.

01:00:40.640 --> 01:00:41.280
So...

01:00:42.200 --> 01:00:44.940
it could also be just six.

01:00:45.460 --> 01:00:50.380
If we look at Karlsruhe and Kalsruhe, then we would have to insert, or

01:00:51.000 --> 01:00:55.680
to get from that one to that one, we would have to delete one symbol

01:00:55.680 --> 01:00:57.520
and add one symbol.

01:00:58.540 --> 01:00:59.580
Editing distance of two.

01:01:00.420 --> 01:01:04.380
And definitely those are, those two words are much closer, much more

01:01:04.380 --> 01:01:05.940
similar than Hausarbeit and Heimarbeit.

01:01:07.120 --> 01:01:10.980
Okay, so these are possible, these are distances that one could look

01:01:10.980 --> 01:01:11.180
at.

01:01:11.680 --> 01:01:16.140
And now the question is how can we actually do that, or use that?

01:01:16.800 --> 01:01:19.220
How can we determine the editing distance?

01:01:19.360 --> 01:01:22.080
Obviously it's very simple to determine the editing, the hemming

01:01:22.080 --> 01:01:22.540
distance.

01:01:22.960 --> 01:01:27.700
We just scan the word and check what difference is, but it is more

01:01:27.700 --> 01:01:30.700
difficult to determine the editing distance.

01:01:30.860 --> 01:01:31.740
How can we do that?

01:01:32.140 --> 01:01:38.840
So, hemming distance is obvious, and for the editing distance, it's a

01:01:38.840 --> 01:01:39.620
bit more difficult.

01:01:39.820 --> 01:01:41.120
So if we have two words,

01:01:44.780 --> 01:01:48.640
how can we determine how different they are?

01:01:49.520 --> 01:01:52.240
So let me draw that in a different way.

01:01:52.620 --> 01:01:58.600
So, certainly a simple observation is that if they have different

01:01:58.600 --> 01:02:03.600
lengths, then we know that, well, we have at least to add certain, or

01:02:03.600 --> 01:02:09.040
either to insert some, if we go from that, from the lower word to the

01:02:09.040 --> 01:02:13.060
upper word there, we would have to insert certain extra symbols.

01:02:13.300 --> 01:02:14.060
At least that.

01:02:14.300 --> 01:02:19.220
But that certainly is just a very bad estimate.

01:02:20.280 --> 01:02:29.340
The exact thing is to say, okay, is the size of U, this is the word U,

01:02:30.060 --> 01:02:34.920
this is V, we look at the difference between those two words, how can

01:02:34.920 --> 01:02:37.340
we get from U to V, or from V to U?

01:02:38.920 --> 01:02:46.240
We can just, well, delete all the symbols of U, insert all the symbols

01:02:46.240 --> 01:02:46.700
of V.

01:02:47.860 --> 01:02:51.420
But then we have done unnecessary work.

01:02:51.940 --> 01:02:55.400
Because it may be that we have a certain symbol here, maybe an A,

01:02:55.780 --> 01:02:57.320
which is also occurring here.

01:02:58.120 --> 01:03:02.320
Maybe it's followed by a B, and that B is also there, and then it's

01:03:02.320 --> 01:03:06.960
followed by a C, and that C is occurring somewhere there, and then

01:03:06.960 --> 01:03:09.160
there is a D, and the D is there.

01:03:11.700 --> 01:03:17.900
Then certainly it would be unreasonable to delete ABCD and insert it

01:03:17.900 --> 01:03:18.160
again.

01:03:19.440 --> 01:03:26.880
So, if we delete all the symbols of U, and insert all the symbols of

01:03:26.880 --> 01:03:32.320
V, we would have deleted all the symbols that are occurring in both

01:03:32.320 --> 01:03:36.940
words, in the same sequence, and we would have inserted them again.

01:03:37.380 --> 01:03:42.500
That means we would have twice done something with symbols which is

01:03:42.500 --> 01:03:48.460
unnecessary, and W here is the longest common subsequence of U and V.

01:03:49.000 --> 01:03:55.100
So it's the longest sequence of symbols that are occurring in both

01:03:55.100 --> 01:03:56.900
words in exactly this sequence.

01:03:57.380 --> 01:03:58.740
The longest common subsequence.

01:03:59.500 --> 01:04:02.500
And so in order to determine the editing distance, what you have to do

01:04:02.500 --> 01:04:06.340
is just determine the longest common subsequence.

01:04:07.960 --> 01:04:10.520
But this is not that simple.

01:04:10.760 --> 01:04:16.780
It can be done certainly, I will show you an example, or the algorithm

01:04:16.780 --> 01:04:18.700
in a moment, how we actually do that.

01:04:19.080 --> 01:04:22.840
But it's not as simple as just computing the Hamming distance, which

01:04:22.840 --> 01:04:26.440
obviously is done in linear time, linear in the size of the words.

01:04:27.460 --> 01:04:31.100
So editing distance is something which is more interesting.

01:04:31.780 --> 01:04:36.040
I said your proof is exercise, I just proved it to you by this here

01:04:36.040 --> 01:04:37.200
screw and also the other one.

01:04:37.420 --> 01:04:41.160
So this is not very difficult to understand.

01:04:42.760 --> 01:04:45.500
And what the longest common subsequence is, is obvious.

01:04:45.920 --> 01:04:51.040
Here, formally, it means we have a certain, like we have our word U

01:04:51.680 --> 01:05:02.400
and we have a word V U and V and we have some U0 here, we have a V0

01:05:02.400 --> 01:05:09.680
there, and we have the W1 there, we have W1 there, and then we have a

01:05:09.680 --> 01:05:14.100
U1 and a V1 and so on.

01:05:14.620 --> 01:05:21.620
So we have these there somewhere a WK, and we have a UK, and here also

01:05:21.620 --> 01:05:25.280
we have somewhere a WK and we have a VK.

01:05:25.860 --> 01:05:33.460
So we have these words, W1 to WK occurring within the word U and

01:05:33.460 --> 01:05:39.040
occurring within the word V and it is the largest or it is, first of

01:05:39.040 --> 01:05:42.620
all, it is a common subsequence occurring in both words, and then we

01:05:42.620 --> 01:05:46.740
are looking for the largest of those subsequences which are occurring

01:05:46.740 --> 01:05:47.460
in both words.

01:05:48.440 --> 01:05:49.660
And we have to determine that.

01:05:49.740 --> 01:05:55.020
This is just the formal definition of a common subsequence and now we

01:05:55.020 --> 01:05:57.180
should look at how we can actually do that.

01:05:59.400 --> 01:06:04.300
You could actually utilize such a thing, like similarity by saying,

01:06:04.460 --> 01:06:10.020
okay, if I send a query to a search engine, that search engine should

01:06:10.020 --> 01:06:15.360
also look for all words that are at editing distance, at most, two.

01:06:16.280 --> 01:06:21.680
It means, just the difference is just inserting one or two symbols or

01:06:21.680 --> 01:06:24.780
inserting one, deleting one certainly you have to say what kind of

01:06:24.780 --> 01:06:30.500
operations you allow here, if it's insert delete or replacement or

01:06:30.500 --> 01:06:30.860
switching.

01:06:31.260 --> 01:06:35.520
So this has to be specified, then you can search for something which

01:06:35.520 --> 01:06:39.840
is similar to the words that you actually have input as a query.

01:06:41.540 --> 01:06:46.440
Okay, let's now look at how we can compute the editing distance.

01:06:48.980 --> 01:06:49.580
Hello.

01:06:49.780 --> 01:06:52.760
Welcome to the final part of this lecture.

01:06:55.140 --> 01:06:59.740
Okay, so here it is called the so-called Lievenstein distance.

01:07:00.240 --> 01:07:02.800
It's known under very different names.

01:07:03.020 --> 01:07:04.220
It's just the editing distance.

01:07:04.660 --> 01:07:08.660
But Lievenstein has designed this algorithm.

01:07:09.140 --> 01:07:10.900
Many people have designed this algorithm.

01:07:11.860 --> 01:07:15.540
Hirschberg is also one, which is sometimes called it, as somebody who

01:07:15.540 --> 01:07:16.720
was looking at that.

01:07:17.140 --> 01:07:21.640
Here, the special thing is that we look at three operations.

01:07:22.380 --> 01:07:25.880
We look at insertions, deletions and replacements.

01:07:26.440 --> 01:07:31.360
Three different operations that we allow for editing and then we would

01:07:31.360 --> 01:07:36.700
like to see how or what the distance is of two words.

01:07:38.240 --> 01:07:39.960
Here we call them S and T.

01:07:41.760 --> 01:07:43.980
So, here we have S and we have T.

01:07:44.700 --> 01:07:50.700
Now, this word has let's assume these are N no, M here I said.

01:07:51.020 --> 01:07:52.560
So, M symbols.

01:07:52.760 --> 01:07:54.140
Here we have N symbols.

01:07:54.580 --> 01:07:55.380
One to N.

01:07:56.840 --> 01:07:59.540
And now the approach is a dynamic programming approach.

01:08:00.140 --> 01:08:02.800
You know what dynamic programming approach means.

01:08:03.360 --> 01:08:08.540
It's a standard approach to output to address certain problems.

01:08:08.940 --> 01:08:14.080
We first of all look at the small problems, solve those small problems

01:08:14.080 --> 01:08:16.180
and then address larger.

01:08:16.380 --> 01:08:22.580
So we solve small problems, list of small problems, then would like to

01:08:22.580 --> 01:08:28.940
solve larger problems by just combining information from these smaller

01:08:28.940 --> 01:08:29.540
problems.

01:08:30.260 --> 01:08:34.800
And so this is not divide and conquer, but it's dynamic programming.

01:08:35.280 --> 01:08:40.220
We just use the information from small problems in order to get the

01:08:40.220 --> 01:08:41.860
solution for the larger problems.

01:08:42.940 --> 01:08:46.900
Usually we do that in a tabular approach that we know that that's why

01:08:46.900 --> 01:08:53.340
we usually fill some kind of table and that's the standard name for

01:08:53.340 --> 01:08:54.000
dynamic programming.

01:08:54.000 --> 01:08:56.120
Now what are we doing here?

01:08:57.300 --> 01:09:00.380
What is the dynamic programming approach in this sense?

01:09:01.200 --> 01:09:03.280
What is the simple problem?

01:09:03.740 --> 01:09:11.880
The simple problem would be to look at just the first symbol of S and

01:09:11.880 --> 01:09:17.920
the first symbol of T and look how much information or what kind of

01:09:17.920 --> 01:09:23.400
operations are necessary to get from the first symbol of S to the

01:09:23.400 --> 01:09:24.380
first symbol of T.

01:09:25.240 --> 01:09:28.400
If it's the same, we don't have to do anything.

01:09:29.380 --> 01:09:33.840
If it's different, we should have to replace something.

01:09:34.380 --> 01:09:39.360
Or maybe we have to delete something or insert something.

01:09:41.080 --> 01:09:42.380
These are the different operations.

01:09:43.800 --> 01:09:50.360
Then we look, essentially, if we have two symbols of S, how can we get

01:09:50.360 --> 01:09:53.200
from two symbols of S to one symbol of T?

01:09:54.840 --> 01:09:55.740
We have three.

01:09:56.780 --> 01:09:57.360
And so on.

01:09:57.420 --> 01:10:03.160
Or more general, if we have all the symbols from 1 to i, this

01:10:03.160 --> 01:10:09.820
substring and a substring from 1 to j and t, how many operations are

01:10:09.820 --> 01:10:17.880
necessary to get from this substring here, S1 to S i, to a substring

01:10:17.880 --> 01:10:19.520
T1 to Tj.

01:10:21.840 --> 01:10:25.080
This can be done by looking at this small information.

01:10:25.360 --> 01:10:26.920
So we build up a table.

01:10:28.280 --> 01:10:32.300
And this table essentially looks like this.

01:10:32.760 --> 01:10:43.920
We have here our word and we have here essentially S 1, 2, 3, and so

01:10:43.920 --> 01:10:44.200
on.

01:10:44.280 --> 01:10:45.540
And we have T.

01:10:45.540 --> 01:10:47.240
No, other way around.

01:10:47.920 --> 01:10:51.300
This usually T is up there, S is here.

01:10:51.860 --> 01:10:54.260
S1, 2, 3, and so on.

01:10:55.080 --> 01:10:59.440
And so if we have assumed we have here just dot dot dot, and here we

01:10:59.440 --> 01:11:03.240
have an i, and up here we have j.

01:11:04.960 --> 01:11:11.640
Now, we would like to fill in this field here, the field i, j.

01:11:12.240 --> 01:11:16.860
And we would like to get there the value d i j.

01:11:18.460 --> 01:11:22.520
Now how can I get d i j from the information that is already in the

01:11:22.520 --> 01:11:22.780
table?

01:11:22.900 --> 01:11:32.160
I assume I have started here and so I assume that I have information

01:11:32.160 --> 01:11:37.660
in this field here, which is i j minus 1.

01:11:38.360 --> 01:11:44.020
I have information in this field, which is i minus the distance, I'm

01:11:44.020 --> 01:11:50.380
referring to transforming the string S up to i minus 1 into T up to j.

01:11:51.200 --> 01:11:55.660
And here I have i minus 1 j minus 1.

01:11:56.700 --> 01:12:01.300
And now we have to this is exactly the information I need in order to

01:12:01.300 --> 01:12:06.220
find out what the distance, or what the number of operations is that I

01:12:06.220 --> 01:12:14.480
need to get from S 1 to S i to T 1 to T j.

01:12:15.900 --> 01:12:17.700
So how can we use that?

01:12:18.700 --> 01:12:28.500
So if I look at d i minus 1 j, d i minus 1 j means from S up to the

01:12:28.500 --> 01:12:38.600
position i minus 1 to j i minus 1 is this one here, I have a shorter

01:12:38.600 --> 01:12:47.790
sequence if I would like to use that number, I know that I would have

01:12:47.790 --> 01:12:53.250
to delete the symbol S i in order to have exactly the distance that I

01:12:53.250 --> 01:12:56.770
had for S 1 to S i minus 1 to get to j.

01:12:57.330 --> 01:12:59.330
That means I would have to delete one symbol.

01:13:00.230 --> 01:13:03.510
That means the number of operations is the number of operations I have

01:13:03.510 --> 01:13:12.130
to get from S 1 to S i minus 1 one symbol to the left of that and

01:13:12.130 --> 01:13:13.950
transform that into T 1 to T j.

01:13:14.130 --> 01:13:18.330
So if it's just a deletion, I would have d i minus 1 j plus 1.

01:13:19.070 --> 01:13:26.270
I could look at the same row here and look at what would happen if I

01:13:27.270 --> 01:13:32.150
look for the distance, the number of operations I need to get from S 1

01:13:32.150 --> 01:13:34.850
to S i to T 1 to T j minus 1.

01:13:34.850 --> 01:13:40.770
If that is the same as going from i to j it means I have to insert

01:13:40.770 --> 01:13:41.250
something.

01:13:41.690 --> 01:13:43.810
I have to insert the symbol T j.

01:13:46.070 --> 01:13:47.250
Another operation.

01:13:47.650 --> 01:13:50.110
So that would mean this distance plus 1.

01:13:51.090 --> 01:14:02.450
Now, if I look at this entry here I have to compare the symbol S i and

01:14:02.450 --> 01:14:12.490
T i S i and sorry, S i and T j If S i and T j are identical I don't

01:14:12.490 --> 01:14:13.330
have to do anything.

01:14:13.570 --> 01:14:19.830
I have the same distance as I had for transforming S 1 to S i minus 1

01:14:19.830 --> 01:14:22.370
to D 1 to T j minus 1.

01:14:23.210 --> 01:14:26.090
If they are different, I just have to replace the symbol.

01:14:27.230 --> 01:14:35.750
And so, these are the possibilities for getting the distance or the

01:14:35.750 --> 01:14:40.930
number of operations that I have to execute in order to get from S 1

01:14:40.930 --> 01:14:42.850
to S i to T 1 to T j.

01:14:43.750 --> 01:14:45.750
And I certainly take the minimum of that.

01:14:46.690 --> 01:14:49.530
Because I don't want to execute extra operations.

01:14:50.050 --> 01:14:52.770
I just take the minimum of the possible choices.

01:14:53.450 --> 01:15:00.150
And so, by just knowing those three entries I can fill in the adequate

01:15:00.150 --> 01:15:01.830
information there.

01:15:02.910 --> 01:15:08.670
That means I can start here and then enter those values there.

01:15:08.950 --> 01:15:09.930
This is very simple.

01:15:10.810 --> 01:15:20.390
I can actually generate from nothing the term T 1 T 2 T 3 and so on.

01:15:20.790 --> 01:15:21.730
Very simple.

01:15:22.030 --> 01:15:25.170
So this is just 1, 2, 3 and so on.

01:15:25.290 --> 01:15:29.430
Here I have 1, 2, 3, 4 and so on.

01:15:30.490 --> 01:15:32.030
And then this is simple.

01:15:33.170 --> 01:15:36.670
And so then I can fill in that field, I can fill in that one, I can

01:15:36.670 --> 01:15:37.510
fill in that one.

01:15:38.010 --> 01:15:39.330
Very simple operation.

01:15:40.150 --> 01:15:46.290
It's just a scanning of those, of that table, at every table at every

01:15:46.290 --> 01:15:51.170
entry I just have to compare those three values and so definitely this

01:15:51.170 --> 01:15:55.310
is just an operation which takes time n times n.

01:15:56.350 --> 01:16:01.870
I have to look at all the different fields in there and so this is a

01:16:01.870 --> 01:16:06.450
quadratic or you could say just the product of the length of those two

01:16:06.450 --> 01:16:13.250
terms and in that way I have information on how many operations I have

01:16:13.250 --> 01:16:16.690
to execute in order to get from S to T.

01:16:17.870 --> 01:16:23.030
Now if we do that for a simple example here you see exactly again

01:16:23.030 --> 01:16:26.750
these four possibilities that I just listed.

01:16:27.330 --> 01:16:34.830
The initial thing would be if we have nothing the empty word how can I

01:16:34.830 --> 01:16:38.550
generate from the empty word the word Saturday.

01:16:39.170 --> 01:16:43.050
I just have to enter those symbols, insertions.

01:16:44.010 --> 01:16:50.490
How can I again here, how can I get from zero to that word, again

01:16:50.490 --> 01:16:56.390
those values and then here from S to S certainly this would be a zero.

01:16:56.990 --> 01:16:59.430
The smallest value, you have the same symbol.

01:16:59.970 --> 01:17:10.910
If we have S to A now here we have this would be one because we just

01:17:10.910 --> 01:17:16.090
have to insert one symbol.

01:17:17.170 --> 01:17:17.510
And so on.

01:17:17.530 --> 01:17:21.550
I don't want to go through all these different fields here I will just

01:17:21.550 --> 01:17:23.930
show you what happens here.

01:17:24.530 --> 01:17:32.230
This is the complete table filled in using always computing always the

01:17:32.230 --> 01:17:40.750
minimum of those values that have to be compared and so we get here

01:17:40.750 --> 01:17:46.950
the values and we also get these links which just indicate how we have

01:17:46.950 --> 01:17:52.830
or which term actually is which operation has been taken in the going

01:17:52.830 --> 01:18:01.430
from this top left to the bottom right entry.

01:18:02.590 --> 01:18:07.350
So in this way we see how these are generated and then certainly to

01:18:07.350 --> 01:18:13.570
get actually the distance from getting the editing distance between

01:18:13.570 --> 01:18:19.850
Sunday and Saturday we just have to look for the smallest entry here

01:18:20.310 --> 01:18:26.390
like this is the final value indicating three and so if we now follow

01:18:26.390 --> 01:18:32.530
that line here we finally get to or see how these operations are

01:18:32.530 --> 01:18:33.270
actually executed.

01:18:34.410 --> 01:18:42.930
So this is indicating what we have to do to get from one word to

01:18:42.930 --> 01:18:49.150
another one and how we can execute or how we can calculate the editing

01:18:49.150 --> 01:18:53.690
distance of two words using or assuming that we just have deletion,

01:18:54.110 --> 01:18:55.470
insertion and replacement.

01:18:56.010 --> 01:18:56.530
Do you have a question?

01:19:05.390 --> 01:19:06.550
That's just the button.

01:19:08.270 --> 01:19:09.930
The line is there.

01:19:11.390 --> 01:19:11.510
Yeah.

01:19:13.410 --> 01:19:14.050
Okay.

01:19:14.230 --> 01:19:19.550
I think it's so this is just showing you the line following the

01:19:19.550 --> 01:19:25.910
smallest values there and so we have the editing distance indicated

01:19:25.910 --> 01:19:26.370
there.

01:19:27.870 --> 01:19:28.510
Okay.

01:19:28.870 --> 01:19:31.990
We can use pseudocode for that.

01:19:32.210 --> 01:19:34.350
I don't want to go into the details there.

01:19:34.430 --> 01:19:38.550
This is just this calculation which I told you about.

01:19:38.990 --> 01:19:41.950
We don't have to go into the details of that algorithm.

01:19:41.950 --> 01:19:46.050
In fact, you are all capable of transforming something which I have

01:19:46.050 --> 01:19:49.990
explained to you just now into a code of a program.

01:19:50.150 --> 01:19:56.150
This is not that interesting really to write a program if we know what

01:19:56.150 --> 01:19:57.450
the algorithm actually is about.

01:19:58.910 --> 01:19:59.130
Okay.

01:19:59.750 --> 01:20:05.070
The important point certainly is that the complexity is just a product

01:20:05.070 --> 01:20:07.150
of the two words that we have there.

01:20:08.230 --> 01:20:16.170
And then we would like to now look for documents in...

01:20:16.170 --> 01:20:18.470
no, look for words in documents.

01:20:18.790 --> 01:20:23.570
I would like to follow now this assumption one, that we would like to

01:20:23.570 --> 01:20:27.470
do a full text search, look for the occurrence of words in documents

01:20:27.470 --> 01:20:32.570
and for that we have to find out how we can actually do that.

01:20:33.090 --> 01:20:36.590
So the input for that would be a document and a word.

01:20:36.750 --> 01:20:39.870
We would like to check does this word occur in that document?

01:20:40.570 --> 01:20:45.430
We assume that the document has definitely a larger length than the

01:20:45.430 --> 01:20:48.230
word otherwise we wouldn't have to look for that.

01:20:49.310 --> 01:20:54.730
And what we would like to get are all the positions where W starts in

01:20:54.730 --> 01:20:55.290
D.

01:20:55.890 --> 01:21:01.450
So if we have our string here, our very long document written as a

01:21:01.450 --> 01:21:07.350
sequence of symbols, then if W does occur there, we would like to get

01:21:07.350 --> 01:21:08.050
that position.

01:21:08.270 --> 01:21:13.030
Or maybe if it's occurring several times, we might also want to get

01:21:13.030 --> 01:21:14.010
that position.

01:21:14.450 --> 01:21:20.270
So maybe we would like to get all the positions of where a word occurs

01:21:20.270 --> 01:21:20.890
within a document.

01:21:21.210 --> 01:21:27.210
As I told you, you might be interested in finding out how often a term

01:21:28.190 --> 01:21:30.470
actually is appearing in a document.

01:21:30.670 --> 01:21:34.430
For that we need the number of occurrences, not just does it occur.

01:21:35.010 --> 01:21:39.010
This would be the initial thing we would be interested in.

01:21:39.710 --> 01:21:44.850
So, what we would have to look at is something like define something

01:21:44.850 --> 01:21:48.230
like a finite automaton which is capable of finding out whether the

01:21:48.230 --> 01:21:51.570
word W occurs within some document.

01:21:52.170 --> 01:21:58.210
Simplified here by writing just the asterisk W and asterisk we check

01:21:58.210 --> 01:22:03.830
whether D is, well, this is formalism to say D is an invert of the

01:22:03.830 --> 01:22:04.910
language of that automaton.

01:22:05.890 --> 01:22:08.410
So we could just specify the automaton very simply.

01:22:09.030 --> 01:22:13.910
We just write a non-deterministic automaton having like this starting

01:22:13.910 --> 01:22:18.890
state here, and then if we look for uni, we would just write those

01:22:20.970 --> 01:22:23.350
finite automaton in this way and that's it.

01:22:23.670 --> 01:22:26.870
Just implement that and you can execute the query.

01:22:27.410 --> 01:22:30.990
Now this would take a bit of time.

01:22:31.130 --> 01:22:32.970
You would need a deterministic version of that.

01:22:33.250 --> 01:22:34.850
We can write that as a program.

01:22:35.810 --> 01:22:37.510
So how do we write that as a program?

01:22:38.230 --> 01:22:46.010
We would just for well, this is written now in a Pascal-like or not

01:22:46.010 --> 01:22:51.990
Java -like version but it's easily readable I think.

01:22:52.570 --> 01:22:58.390
So we just go into a loop from 0 to 1 per n-m.

01:22:58.810 --> 01:23:09.250
So certainly the final the rightmost position could be n-m because we

01:23:09.250 --> 01:23:11.470
look for complete occurrences of the word.

01:23:12.450 --> 01:23:16.590
That's why we only have to look for... let me rewrite that here.

01:23:17.030 --> 01:23:18.930
We look at possible occurrences.

01:23:19.450 --> 01:23:25.130
So this would be one position i that we look at and then we would like

01:23:25.130 --> 01:23:31.870
to check whether starting from that position i we actually have at the

01:23:31.870 --> 01:23:37.770
positions i plus 1 to i plus m exactly our word w in there.

01:23:38.830 --> 01:23:47.970
So j is set to 1 and then while we scan through that word and while

01:23:47.970 --> 01:23:55.890
the document is exact or has the same symbols as w at those locations

01:23:58.010 --> 01:24:05.950
we increase the value of j and if after we exit that loop j is larger

01:24:05.950 --> 01:24:10.130
than m it means that all the symbols actually match and we have a

01:24:10.130 --> 01:24:12.630
match at position i plus 1.

01:24:13.030 --> 01:24:19.510
Because we looked at positions w1 we looked at the symbols w1 to wm at

01:24:19.510 --> 01:24:22.150
positions i plus 1 to i plus m.

01:24:22.750 --> 01:24:24.390
So this is a very simple algorithm.

01:24:25.210 --> 01:24:25.570
Trivial.

01:24:26.230 --> 01:24:26.750
That's it.

01:24:27.130 --> 01:24:27.690
Pattern matching.

01:24:28.750 --> 01:24:31.370
But that now has to be analyzed.

01:24:32.370 --> 01:24:37.270
How much time does that actually need to execute this algorithm?

01:24:37.710 --> 01:24:42.110
We have a loop there this is one loop, this is another loop this loop

01:24:42.110 --> 01:24:48.090
is running from 0 to n minus m if m is a constant or a small value

01:24:48.890 --> 01:24:55.750
it's approximately n here we have at every position what we do here

01:24:55.750 --> 01:25:01.870
actually is at every position from i to n minus m, we might scan

01:25:01.870 --> 01:25:07.410
through almost all the symbols of w so the upper bound for that would

01:25:07.410 --> 01:25:08.770
be n times m.

01:25:09.950 --> 01:25:11.190
Quite a long time.

01:25:12.310 --> 01:25:16.830
The point is if we have for example come to such a position and then

01:25:16.830 --> 01:25:22.990
notice well, there's a mismatch here's some kind of mismatch, some x

01:25:22.990 --> 01:25:29.150
which does not occur in our word we have scanned through this prefix

01:25:29.150 --> 01:25:33.410
of the word and noticed these symbols are occurring in the document.

01:25:34.810 --> 01:25:38.970
And now this is information one should not lose because we have this

01:25:38.970 --> 01:25:42.730
information and then we should exploit that.

01:25:43.290 --> 01:25:47.570
And to exploit that is something which Knuth Morris Pratt did a long

01:25:47.570 --> 01:25:52.910
time ago when people looked at these pattern matching algorithms so

01:25:52.910 --> 01:25:58.150
what we actually notice is we have been at some position so this was i

01:25:58.150 --> 01:26:05.050
this is position i plus 1 and we notice a mismatch here's a mismatch

01:26:07.670 --> 01:26:17.350
and if we have a mismatch we should not just move the word the

01:26:17.350 --> 01:26:21.630
potential pattern here one position to the right but we should exploit

01:26:21.630 --> 01:26:27.030
the knowledge that we have about this prefix we should look at the

01:26:27.030 --> 01:26:32.670
structure if we know that the first symbol here is not occurring at

01:26:32.670 --> 01:26:39.450
all in the remaining positions here we can immediately shift So what

01:26:39.450 --> 01:26:49.990
we should do is, we find out how many symbols at the prefix of our

01:26:49.990 --> 01:27:00.230
pattern, how many of these symbols occur to the left of the symbol wj

01:27:00.230 --> 01:27:01.950
in our pattern.

01:27:01.950 --> 01:27:11.770
So if those symbols here reoccur at this position, then we know we can

01:27:11.770 --> 01:27:19.230
shift the pattern exactly by that distance.

01:27:19.230 --> 01:27:24.610
And we would like to optimize that distance, shift the pattern as far

01:27:24.610 --> 01:27:28.930
as possible to the right, but certainly not too far, because certainly

01:27:28.930 --> 01:27:31.870
this could be a potential new starting position.

01:27:32.490 --> 01:27:37.650
So we would like to indicate the next possible starting position of

01:27:37.650 --> 01:27:41.010
the pattern and shift it exactly that much.

01:27:41.010 --> 01:27:49.610
But that also means we don't have to look again at those locations

01:27:49.610 --> 01:27:55.170
that we have already scanned, because we will shift the pattern as far

01:27:55.170 --> 01:28:01.230
to the right as reasonable, exploiting the information that what is to

01:28:01.230 --> 01:28:10.650
the left of the wj is exactly the same as before, but the symbol that

01:28:10.650 --> 01:28:15.670
is at this location here, so the symbol that was there, certainly

01:28:15.670 --> 01:28:17.330
should be different from wj.

01:28:17.330 --> 01:28:24.290
And then we can optimize the performance of the algorithm, and that's

01:28:24.290 --> 01:28:27.710
the Knuth-Morris-Pratt algorithm, which runs in linear time and not in

01:28:27.710 --> 01:28:32.590
time, like in time order of n, because we only scan every symbol here

01:28:32.590 --> 01:28:37.770
once, we only increase those values, and we can shift larger distances

01:28:37.770 --> 01:28:41.730
and then can improve the efficiency of the algorithm.

01:28:42.150 --> 01:28:43.690
Okay, that's it for today.

01:28:43.870 --> 01:28:43.990
Thank you.