Okay, good morning.
Welcome to another session of Algorithms for Internet Applications.
Just five minutes delayed today, because now we know how to deal with
the technical problems.
But...
Okay.
Last time we looked at, again, last time at Internet technology, we
looked at some aspects of the TCP protocol.
I showed you the...
header for TCP, right?
That was it.
I told you something about the logical connections, about ports and
sockets, and all the different aspects of the header fields.
We talked about the connection management, and in particular talked
about the flow control, which is one of the major tasks of TCP.
And that was more or less it.
I mentioned that TCP has problems if we look at specific applications
where it is important to have a sustainable bandwidth, where it's not
that essential if some of the datagrams are lost, because in audio
transmission, for example, that would just be a small mistake in the
audio signal, but it's important to maintain a certain frequency of
data.
And so for that, TCP is not that reasonable.
So for that, we have UDP.
And then I briefly showed you this slide on ATM, where the most
essential point is that that is a protocol where the quality of
service is an important aspect that we can have guaranteed quality
there for different service classes.
And that was the last slide of the last lecture.
And so now I would like to come to the next chapter, where we talk
about something which is more using the Internet, using services on
the Internet, and in particular one point or one topic which is very
relevant for the Internet, as you all know, is dealing with
information.
Lots of things have evolved there, and we know that there is, well,
here I say there are currently about 300 million web searches per day.
Probably this is much larger.
Meanwhile, funny, all of a sudden I have a black pen.
Don't know why the pen switched to black.
I did not choose that.
So I would take red again.
Okay.
So definitely there might be more than that, but it's just, the
important point is that there are millions and millions of web
searches per day, and so this is something where we really have to
look at algorithms, how things like that actually are supported, how
we can get information.
Searching for information is definitely one of the most popular
applications.
We all do it.
We all search for information.
Very often we don't type in the address of a website, but type it in
the search field, and then just go to the appropriate location using a
web service, a web search service.
And so what we have to look at briefly is what search engines are
about, how they operate, what some essential aspects of these search
engines are.
We should look at some basics of information retrieval, and it's
always a problem that you have, there are different points in your
courses that you are taking here in your programs of study where you
might have already looked at topics related to this, so for example,
if we talk about retrieving information, then we very often look for
certain words in some documents, so if we would look for information
retrieval and would like to get this document, which I've just
presented to you, it means we would have to look for exactly the
occurrence of that word in that document, so that means we would have
to do some kind of pattern matching in texts.
And this would be something which would take a long time because we
would have to look through all the different documents.
Certainly we don't do that.
And so what we usually do is, or not we, but the search engines do is
they create a huge index where we can actually jump immediately to the
relevant documents.
That means we don't search in documents, but search in catalogs and
indexes where all the information is structurally available.
Then the search engine definitely has to analyze search phrases.
We formulate some queries in some way, and they have to be interpreted
in a reasonable way.
We will look at that briefly.
We have to measure the relevance of the retrieved documents.
We don't want to get all kinds of documents.
And we will look at that problem for a moment.
And then, there definitely is quite a large range of search engines
available.
And, well, most of you probably know at least one.
Namely, you all know...
Did I list it here?
Yeah, I listed Google.
So Google is one of many, many, many search engines.
And it certainly is one of the major ones.
Some appear in a different...
There's still quite a range of different search engines available.
So here I have some old list.
OLL, Netfine, Excite, Google, certainly, Hotbot, Infoseek, Lycos,
Webcrawler, Yahoo, Metacrawler, and so on, and so on.
Lots of search engines.
They all have different aspects.
Somehow, we use almost only one.
But this is another problem.
So, at this website that I mentioned here...
Actually, I think it's not important to go to the website now.
That website, you get all kinds of information on functionalities of
search engines.
And in particular, what you get there is information
on how you actually should design your document.
So if you write a document...
This was supposed to come from Google.
So if this is a document, you have several documents, and you have
certain important information in there, and you would like to make
sure that if you put a query to Google, then the result should be a
list, and the top documents should be exactly your documents.
Whenever it is information that was looked for, which is relevant for
your documents.
So, if you are designing the webpages of a certain company, or of your
own company, or you have certain interests, that your information is
available to the relevant users as a response to a query, you must
make sure that your website is listed as the top rank.
And so, in order to know how to do that, you have to know how actually
the search engines classify webpages, websites, documents, how they
are ranked, and how you can make sure that you don't end up somewhere
down there, where you never look at, but that you can jump up to some
places over there.
This has to be done in a way that is justified, and not considered to
be website or some kind of spamming, that you have unjustified
information in there, and in that way try to get to the top rank.
We know that if we look at the webpage that we get as a result to a
query, there are always some elements at the top listing, which are
paid entries.
This is something which has not been there in the beginning of the
search engines, but certainly popped up because the companies would
like to make money, and so they get payment from companies who would
like to be always listed as the top entries, and if you look more
closely, you will notice that certain sources of information are
always in the top rank, at least with Google, like for example
Wikipedia is always in the top ranks, because it's owned by Google,
and so they always make sure that their information is on the top.
So this is all stuff about...
when we talk about searching for information, we have to know how you
can actually locate information, and then how you can present that
information.
And so, you are shaking your head in the background there.
What's wrong?
Pardon?
As far as I know, yes.
That's what I heard some time ago, that they are very closely related
to Google.
So it has not been founded by Google, but they are at least very
closely connected to Google.
So Google owns many, many different services.
They are very powerful.
And they really provide perfect services.
What I wanted to tell you is that at this website, which changed its
appearance significantly in recent years, so yesterday I just wanted
to briefly update the information I have in my slides here on this
topic, and I noticed that all the nice sites where I had those
information have disappeared somewhere.
I don't know why.
It's more difficult to get exact information on certain web search
statistics.
Then I noticed a few things again.
So this URL that I listed here now has a list of tips on links to
information where you get all kinds of things about search engines,
facts and funds, status reports, resources, and so on.
And here the point of view of this website is always information for
the designer of websites, what they should consider when they design
websites in order to make sure that they are adequately listed in
search engine rankings.
So this is an important thing.
It's not sufficient to just produce information and make sure it can
be found, but you have to make sure that it is presented in the right
way, that it's made available and visible to the persons that you
think are the relevant target audience.
Okay, so this is what we will at least look at to some extent.
I cannot present you all the different algorithms that are around
there, but we have to briefly classify what's going on there.
So first of all, what is it that we talk about when we talk about
search engines?
Most of you use them, you know what they actually do.
They constantly visit websites on the Internet in order to create
catalogs of web pages.
So the search engines are usually created automatically by some
program which is visiting the web, and so this is done without human
interference.
You don't have to manually look at the results and then put it in some
catalog, but the search engines do that automatically.
Then there are directories, not catalogs, but directories.
This is just a classification.
Directories are actually manually created catalogs of web pages.
That means somebody has looked at those resources that are listed
there and classified them and made some quality check.
One of the major original examples is Yahoo, where Yahoo nowadays is
not just a directory, but also a directory extended with catalogs.
That means it is manually created content plus additional content.
Another example of that was WebDE.
So this was...
they were organizing the Internet, they said.
So they had classified information, organized information, and quality
checks on the links that are actually available there.
And as a provider of information, you can submit information, you can
submit websites to be listed in these directories.
So this is something like the official catalog of information that is
in some way quality checked.
Whereas the catalogs of search engines are not quality checked, are
just all the information you have or that you get access to is
actually listed in those catalogs.
And then certainly there are the hybrid search engines, which combine
both.
Where Yahoo again is a good example because they have search engines
which automatically create catalogs, but also have some more organized
and quality checked directories.
So how do these search engines work?
They have, as I said, they visit the major...
or they visit the websites, the pages on all the websites regularly.
This is done by programs called spiders or crawlers.
That means we have here the internet and now you could think, well,
this program is actually...
this spider is actually visiting all these different nodes in this
building or in this web of information.
And so you could think as if a program would visit all these different
nodes.
One could do it that way.
One could use mobile code for that, but we know we don't have to do
that.
We can just access all the websites and... but...
by just entering all the different or checking all the different URLs
for the website or the addresses.
But it's obvious for every check of the website, we have to execute
the HTTP protocol and access or communicate with the web server at the
site where we would like to get some information.
So we have to visit the page.
That means retrieve the information from there.
You have to read the page.
And then in the page, you might follow other links.
And then these links to these other pages may be within that site or
at other sites will also be followed in that way.
In this way, these spiders are crawling the web because they just
follow all the links that they can actually access.
And in this way, they get more and more information.
And this is just one point that you have to discover information on
the web.
And then you have to make sure that the information that you list in
your index or in your catalog actually is up to date.
So you have to revisit the sites on a regular basis every month or two
or maybe every three weeks, every five weeks, every eight weeks.
This revisiting interval will depend on the frequency of change that
you actually observe.
So you are just visiting a certain web page.
This is the time you visit that at regular intervals.
If there is no change, then you increase the intervals.
If there are more changes, then you have to decrease the intervals and
visit it more often in order to have always updated current contents
there.
So we know how many websites there are.
Quite a few.
So Google, for example, some five, six years ago, had something like
eight billion, that means ten to the nine, websites in its catalog.
We will come back to that probably a bit later, but if we just make a
simple calculation what that would mean if you have to revisit eight
billion websites every day or every three weeks.
Just every three weeks.
What that means for the number of websites you have to visit per day
and you know how long it takes to visit a server.
If you look at the time it takes to execute a ping operation.
A ping operation, like if you just want to go from one server to the
other, just communicate.
You just have to...
You are counting the people here.
What are you doing?
No?
Okay.
So it's a huge number of websites that you have to visit and you know
how long it takes to actually visit an individual site, how long it
takes to access a webpage, and then you can simply calculate how much
time you have to spend to visit all these websites or how much
computing power you have to provide in order to support something like
eight billion websites that always have to be up to date or content
should not be older than at most three weeks.
You always expect that it is the current information and then how much
computing power you would have to provide in order to be able to do
that.
I don't want to go into details here.
I'll do that later.
So that's the spider.
The spider is just checking the information and then the index is
built, this catalog, and we know what an index is.
If we have a book, at the end we have some listing and we have all
kinds of words like some word like web or something and then we have
here a listing of all the locations where this word actually is
occurring.
That essentially is an index, as you know it from every textbook,
where you have an index at the end in order to retrieve very quickly
the relevant locations where a certain word that you are interested in
is actually occurring.
So this is what has to be built and if you have 8 billion webpages,
you have many, many words that might occur there.
Certainly the number of words that are currently looked at is not that
large.
That's, by the way, an interesting information provided on the Search
Engine Watch website.
You can look up the most frequent search terms of today, yesterday, or
the last week or things like that and in that way see what are the
most common search queries.
So you have to make sure that search queries are supported, are
executed very fast, and so you need efficient data structures and
access methods for such an index.
To build up an index is a very complex and challenging task and it
needs a lot of computing power to actually execute all the queries.
And this is done, this executing the queries is done by the Search
Engine software which has to analyze your query if it's just one word.
It's simple, but if you have a sequence of words and maybe even
complex search query, then this has to be analyzed adequately.
This is the smallest task.
Then you have to search the index for documents matching the query.
The time for that depends on the efficiency of your data structures
there.
And then the software has to rank the matching documents in order of
relevance.
So you have to know something about relevance of the document for a
certain query.
Now, let us briefly look at what kind of measurements we would have to
talk about the quality of information retrieval.
So, information retrieval in general, which is much older than all the
Search Engine activities, information retrieval is a very old subject.
And there are two standard measures which are assessing the quality of
information retrieval.
One is called recall and the other is called precision.
So recall means, assume you have a certain database of documents.
So this is all the documents you have.
Now you ask for a certain document.
You ask for documents containing, let's say, words about the Karlsruhe
Institute of Technology.
Some documents will contain information on that.
Some won't contain that information.
So you can split up your database into your collection of documents
into at least two subsets.
One which is irrelevant, one which contains the relevant documents.
Now this assumes that we can exactly say this document is relevant,
that one is not relevant.
Very often we don't have such a 0-1 decision, but we have a degree of
relevance.
But here I simplify that and assume that we say this is relevant and
that is not relevant.
And now you get, as a result of your query, you get a certain
response.
You get a certain number of documents.
And the quality of that query, of that response to a query, can be
measured in two ways.
One is, well, you retrieved a certain number of documents and some of
them are relevant.
And you know in your database you may have more relevant documents.
So you look at how many of those relevant documents are actually
recorded.
This is about the number of relevant retrieved documents in relation
to all the relevant documents.
How many of those relevant documents did you actually get in the
response to your query?
Another point is, how precise is the response to your query?
How precisely did your search engine actually check whether the
documents are relevant or not?
And so what you now look at is, you have a certain number of retrieved
documents.
Here, this part of your documents is relevant.
But you may also get other documents which are not relevant.
And so you look at the number of, or the fraction of relevant
retrieved documents with respect to the number of retrieved documents
that you got.
So here you look at how much irrelevant documents there actually are.
Or you say, what is the quality of the response with respect to the
percentage of relevant documents.
And certainly, this is important to look at.
And the problem is that there can be different strategies.
You could say, well, I would like to provide a service which is always
relevant.
So I only return very few documents where I'm certain these documents
are relevant.
But then the recall will be small.
If there is a huge number of documents which might be relevant, then
if you are lazy, you just return one document which is relevant.
And then you have a very precise response to the query because
everything you return is relevant.
But if you say, okay, I would like to have also a high recall, you
could just, well, you could return all the documents.
Then you have a very high recall because you have provided all the
relevant documents, but it's not the task of the user to actually
search through that huge number of documents to find out which ones
are relevant and which ones are not.
You can have a high recall but a very small precision and the task or
challenge is to have high recall and high precision.
And now since the decision on whether a document is relevant or not is
not a simple 0-1 decision, you have to look at that more closely.
We will do that a bit later.
So you can easily achieve high recall or high precision but if you
look at both criteria then you are closer to getting something which
is measuring the real quality of your search engine.
Now, let's briefly look at this notion of relevance.
When would we say that a document is relevant for a query?
So if we get a link to a document and we look at that document, then
we have looked for a certain term, a search term, and then we
certainly assume that there should be a match of that term.
So this term that we looked at should appear in the document.
And certainly it's nicer if it appears many times.
So a number of query terms with matches.
Or maybe we have a list of terms not just one term but some list of k
query terms.
And certainly you would like to see as many as possible of those terms
in your documents that are presented to you as being relevant.
So the number of query terms with matches certainly is an important
point.
But then also the number of matches.
If you have one word which is appearing several times, the document
probably will be more relevant than a document where this term appears
only once.
Another point is where do we actually notice those terms?
If in the first line of the document we see one or several of these
query terms, we are happy.
It must be a very relevant document.
This is an indication of relevance for a term.
If it appears in the first lines of a document, it should be more
relevant than terms which just appear somewhere in the end.
So... or you could say if at the end you have the conclusion of a
paper or something so maybe the terms appearing there could again be
relevant but something which is just in the middle somewhere will not
be that relevant.
So this all are indications of relevance.
The location, the number of matches, the number of query terms which
actually match and then certainly the quality of the matches.
If you look for a certain term like match and you also get a link
where you have a word like this well, you would not really think that
that is relevant.
But it's just very close to the term that you looked for.
Just one misspelled letter there.
So you have one additional letter very close to the term you actually
looked for and sometimes you are very interested in actually getting
hits for words that are very similar to the word that you are actually
interested in.
And so the question whether you are only looking for complete matches
or also for partial matches is important because if you allow for
looking for partial matches then you get more documents back.
Maybe you have not completely specified the term that you are actually
interested in and that way you get the really relevant documents.
Then you might have misspelled your query.
You notice when you put queries to Google and you misspelled the
search term usually Google suggests certain other words which might be
the intended query term.
Then they ask isn't that the actual query term that you looked for?
So this is something looking or considering misspellings.
This all has to be done by the search engine software.
Then there may be explicit information on relevance.
Explicit information, direct information on relevance may be that you
have a certain header of your document which is not visible directly
in the web browser but is information contained in the file.
You know that you have meta tags in your documents and you can
explicitly specify their keywords and things like that and in that way
enter certain keywords that are important for search engines to
evaluate such that queries will also be linked to that document even
if a certain term does not appear directly in that document.
So this might be important if for example you are having a certain
term and this term is also known under different names.
You have synonyms for that and you could just put certain synonyms for
important words into your meta tags and so in this way you could list
here many different terms and in that way enhance the probability that
your document actually will get listed as the result of a query.
So this explicit information in the meta tags is important and
obviously the knowledge of the method of evaluation will influence the
way you present your document.
And also these statements on relevance are not unique.
They depend on the method of evaluation.
How you actually combine all these different aspects into some rank.
There are others.
I did not mention all the things but I should at least indicate it
briefly.
If you have a document and there are many more documents which are
linking to that page then usually this is also considered to be an
indication of relevance.
This actually is the major indicator of relevance for Google.
It says well, if a page is actually very popular in the number of
links that are pointing to that page then this must be a very relevant
page.
And if you know that, you know how to set up your web page.
Or how to create links to your page.
There are services available creating links to your page such that you
get a high popularity index.
But this certainly has to be justified.
So this is always this trade-off between or this problem that you
would like to get.
You know how ranking is done so you know what you have to do in order
to get to a higher location.
But it has to be justified.
It has to be an adequate ranking.
It has to do with marketing.
We are not talking about marketing, we are talking about algorithms.
But certainly in marketing people also use algorithms.
Another point which I would like to briefly mention I just told you
about the task of the spiders and so on.
They visit all the web pages.
Now assume you are setting up a very modern web page or website and
all you have there are dynamic contents.
You have certain services which will create contents depending on the
personal choices of the person who is visiting that web page.
That is a problem.
These web pages will never be indexed by a search engine because an
automatic crawler can only notice oh there are certain services
certain scripts that actually can access information but since there
is no person behind that these contents which can be dynamically
adjusted will never be indexed it will never enter the search engines
on the catalogs and the indexes and so on.
And so if you put all your information in a very fancy way using
dynamic techniques for presenting your content and your website this
information will never be available to other places.
So this is you always have to add extra information either in meta
tags or on static web pages which can actually be listed or checked by
search engines, by the spiders and then indexed in or entered into
these catalogs.
So this is a lot of extra information on this slide where I just
wanted to tell you what actually makes a document relevant for a
query.
The next question is, we'll come back to the notion of relevance a bit
later.
What is a query?
When we talk about queries, so what is actually in there?
There are many different ways of actually stating a query.
You can actually put in some natural language or some phrase in normal
language and this will be interpreted.
But you could also just enter a few terms and so the query normally
consists of something like this.
Some people have analyzed all the queries.
2.35 terms in a query.
Don't know how many terms you put in a query when you search for
something.
I think this may increase slightly.
If you type in something again at Google, you get suggestions what you
might actually be interested in.
And then you get certain numbers of terms, maybe two or three, but
usually not more.
So 2.35 actually is quite a large number.
I don't know what your habit is when you ask something in a query.
So let's assume we want to search for documents containing Universität
Karlsruhe.
Nobody knows what that is, but maybe there's still something around
there or the name Algorithmus.
How could we do that?
So now we have to decide what we actually want to do.
We want to search for all documents containing these words.
First of all, we have to notice a document here is essentially just a
sequence of symbols.
So we could have here a very long sequence of symbols.
It's a sequence of symbols over some alphabet.
We know how to talk about languages, about words, and so on.
So we could simply formalize that and say there's a match for a query.
For example, the query A that we have here, Universität Karlsruhe.
If we have a document D, which is an element of this set.
What is that set?
It is a set of words starting with any symbol from this alphabet
sigma, then having the letters Universität blank Karlsruhe, and then
again some sequence of letters.
That means this term here occurs somewhere in some document, in some
word.
Now this should remind you of something we have looked at if you are
students of business engineering or if you are students of other
programs, then you have looked at other courses.
So this is just regular set.
Regular set we know we can analyze using finite automata, so if we
would like to execute such a query, we could just run, or let some
finite automata, some state machine actually analyze all the documents
and find out which documents are acceptable to that finite state
machine.
Then we have actually, this actually is the algorithm to build this
finite state machine which will find out whether a document contains a
certain pattern.
This is one approach that you could look at.
So here, the query corresponds to a regular expression we have, we can
actually find out whether there is a match if we just execute this
finite automaton.
It's not just any finite automaton, we have to do that in a reasonable
way, but definitely we know what kind of system that is that we have
to look at.
And it certainly means every query corresponds to a finite automaton.
That means for every query, before we can execute that on a set of
documents, we have to generate that automaton.
Well, this can be done easily in an automated way.
And we will see how we can actually define or design very efficient
algorithms for pattern matching in documents.
The other assumption is that your document is represented within an
index.
That means you have a data structure which allows for efficient
retrieval of all the relevant words of a document.
And so there, you would not analyze the document, you would just go
into the index, search for the words for University of Karlsruhe, and
then follow the link that is showing you all the different documents,
but this is actually occurring.
But this certainly means we have to analyze the documents before we
actually execute the queries, and this is what I mentioned the search
engines actually do, that they look at all the different websites and
analyze the websites.
But certainly for that they have to find out what is actually the list
of relevant words that might be looked at later on by some query.
So if you are interested in full text search, you actually might have
to go through all those documents.
And you know, if you, for example, search through all the email
messages that you have on your computer.
If you don't have an index, it takes quite some time, because the
standard procedure would be to perform it following assumption one,
that you have actually to build or to execute a query on all the email
messages that you have and search for the occurrence of certain words.
If you have an index on your list of, on your database of email
messages, then it's much faster.
You just have to access the index, but you have to build that index,
and this takes quite a long time.
So this is just following the different approaches to searching for
information in documents.
We will look at both ways of analyzing documents.
I will present to you ways of actually looking for patterns in
documents, so full-text search.
We will also briefly look at how we can actually build up a search
structure for the words within a document.
Now, you remember what a regular expression is?
You know that this is the standard notion.
We have certain symbols that are regular expressions, so the symbol
for the empty set is a regular expression, or the elements of the
alphabet are regular expressions.
And if you have two regular expressions, then you know that you can
combine them with plus, dot, and the star.
So sum, product, and iteration are the three operations that we can
form there, whereas these are essentially only sequences of some
letters or some symbols, and then we name them regular expressions and
we have to interpret them adequately.
You know all that.
Now, certainly we don't want if you write a query, sometimes you have
these notation available and you can write something, for example,
write a question mark after a certain term, which means it might
occur, but it not necessarily occurs there.
Or you say, you can have the empty word there, or you can say, okay, I
just want to specify that some of the letters in between, for example,
A to F, will appear there.
Then you can specify it in this way, which is simpler than specifying
it as a sum of all the individual symbols.
Or you could say, well, I would like to look at all the documents
where a certain term appears at most k times.
This would be something like this.
Or you say, I would like to look for documents where a certain term
appears at least k times.
And you could specify it like that, which would be much more difficult
to specify if you would do it in a different way.
So this is just extensions, and you know that in many queries you can
actually specify search terms like that using this notation from
regular expressions.
So we could, for example, I don't assume that you would do that
actually, but one could specify a search where we look for all kinds
of variants of the word algorithmos, and this would occur at least
five times, in the following way that it should start with any symbol
from sigma, it might be followed by any symbol from sigma, and then it
should either start with a capital or small a, and then have here a
certain word in there, and then we would have to have either the
ending s, or us, or en, or ic, or isch.
All different variants of algorithmos, or algorithmen, or
algorithmisch, or whatever.
And so this here might occur, but does not necessarily occur.
It's a potential ending, and there could be anything following that,
and we would assume it should be there at least five times.
So it means there are five occurrences, at least five occurrences of
such a term in between.
A way of specifying a more complex, or more general query, but this
would be something for computer scientists who would be familiar with
this way of specifying queries, but normally you don't do that if you
have something for everybody, so there we have different ways of
specifying queries.
And so internally, this can be done in this way, but this is usually
presented to the user in a different way.
So normally we have certain Boolean queries where we just search for,
for example, conjunctive or disjunctive combinations of words.
We would say, okay, I list a certain number of words, so for example,
if I would have here these words, what is a regular expression?
This is in a standard way interpreted as if you would search for the
occurrence of any of those words.
At least one of those words.
Where you could say, okay, is and if are not really relevant.
So you would delete those words, but you would assume you have here,
and what also is not that important.
So you would have here a search for at least one of those that are
occurring in a list.
Or you could make that more explicit and say you explicitly write
there a disjunctive sequence of terms, or you combine it with an and,
and then you have a conjunctive search.
Or you could actually have more boolean operations in there, and then
have more complex queries.
Usually if you look at more advanced search inputs, then you can
specify exactly those things.
Now I have made a few just for examples, a few search queries where
you could so where you see what actually happens if you search for
certain words.
Actually I did not only in Google, I looked at this was interesting,
that one of the first search engines was AltaVista.
Still like AltaVista, and so I entered, or I searched at AltaVista,
and actually what is happening is that the search engine of AltaVista
now is the search engine used by Yahoo.
So it's still presented under the name of AltaVista, but if you ask a
query there, you get a link which is just a Yahoo link.
And now I think this is interesting.
I updated that last night, and so this is different every year.
I have for comparison, I just left there the indicator of the year
2007.
I could have updated that from the data I had last year, but I think
it's...
it tells the story that I wanted to present.
So, first of all, here is a query which could be simplified without
listing all the or's in there, but here I wanted to just indicate I'm
interested in one of the words that are listed here Angewandte
Informatik Universität Kassel.
And you notice that at AltaVista you had 33 million pages that are
listed.
At Google you have 199 million.
Perfect.
And now we can check all these pages and find out which are relevant
and which are not relevant.
Probably most of them will be irrelevant.
2007 I had 88 million.
So something in between.
I had not listed here whether it was Google or Yahoo search.
Like these 88 million.
But just to show you that there are differences in there.
Then if I look for all the words in...
all these four words should occur.
Angewandte Informatik Universität Kassel.
Then I have 36,000 pages at AltaVista 201,000 at Google.
Well.
And in 2007 I had 268,000.
Even more.
You would assume that the number of pages has increased from 2007.
Maybe it has decreased because we don't have any more Universität
Kassel but we have Kassel Institute of Technology.
Maybe that certain pages just disappeared.
But I don't know why that happens but it just reflects the information
that is available in the catalogs of those search engines.
And that's the important point.
You only get the information that is available in those catalogs.
Then I looked for Angewandte Informatik and Kassel and not Mathematik.
And then this is reduced.
Just 17,000 pages here and only 29,600 at Google.
And it had been 41,000 in 2007.
I don't...
I have no indication on how many of those listed or these numbers
actually refer to relevant pages.
It's at least the number of hits that they have in the index.
Or if I looked under...
This is the third way of looking for...
or another way of looking for information if we are interested in an
exact phrase.
Then here we see, okay, Angewandte Informatik Kassel, just 117 pages
at AltaVista and 31,000 at Google.
This is strange.
This is very strange.
Yeah?
It's really strange.
Because I did that last night.
I looked for this one and now I also look for this.
And definitely every page that has a listing which contains Angewandte
Informatik Kassel is containing Angewandte and Informatik and Kassel.
And we got 29,600 hits at Google but for the string Angewandte
Informatik Kassel, which should be a subset of the documents, we got
31,300 at Google.
This is strange.
Something must be wrong there.
But this happens.
Yes?
...
Okay.
Maybe.
You're right.
But yes.
Yes.
You're right.
Thanks.
You're right.
This can happen.
So definitely I have this part here so maybe that some of those here
contain Mathematik.
You're right.
So my conclusion was wrong.
This is still adequate.
May well be.
You have another question?
They are very strange.
Yes.
But things like that happen.
I do this every time I teach this course and I also have a few other
test queries that I always perform and do that at different search
engines and the results are very different and sometimes I have very
strange results which indicate that certain things well indicate that
these algorithms are not always executed in an exact way.
Some things are in some way erratic.
It's always depending where the query actually is executed.
And certainly it's always the case that if you execute these queries
here in Germany or if you are here or when you execute that query at
some other location where you connect to the network from a different
location, you get different results because you will be located to
different catalogs and they have different content there.
Yes.
Maybe.
Yes.
But I think I did not check that.
I just put it in there last night, just that query.
I could have checked for the advanced search in Google and there you
can search exactly for the phrase.
I did not do that explicitly, so you may check whether you get similar
results or not.
But I just like this observation nevertheless is very valid.
So definitely thanks for that remark.
Definitely the conclusion here that this was not correct was a false
observation.
So definitely maybe that it's just the difference that this extra term
not mathematique is reducing the number of pages.
It should reduce it, definitely.
OK.
I just wanted to indicate to you that those large numbers anyway,
these numbers are much too large.
What kind of information do we actually get from that if I have 33
million or 88 million listings?
I never look at all these.
And if you go... I did not do that, but if you ask the same queries to
MetaCrawler then you will get much smaller results.
Because MetaCrawler is looking at...
is sending a query to a list of search engines and is then extracting
the relevant information from the responses of these different search
engines.
And in that way only providing to you a subset of the relevant
documents that are sent to you as a response from the individual
search engines.
And in that way they always present to you a smaller list of documents
but it should be those that are more relevant.
So everybody should use MetaCrawler.
I don't do it.
But one could do it and then you should get more relevant documents.
And documents where they don't provide you with millions of hits or at
least don't tell you they have that many relevant documents there.
So I just wanted to show you that it's a difficult topic to talk about
how we can actually retrieve information.
Another point is I said we would like to look for similar words.
Now what does this actually mean to look for similar words?
So we look for something like Hausaufgabe or Hausarbeit or Hausaufgabe
or Heimarbeit.
Very similar words.
You could say at least Hausaufgabe and Hausaufgabe are almost the
same.
But for a search engine which is analyzing those words, very
different.
We immediately see it's the same meaning.
But how can a search engine do that?
Or if we look for Stadt, we should also look for maybe for documents
containing Städte.
What about this?
Is there Stadt with double T and not DT?
Simple misspelling.
Completely different meaning.
Maybe you are also interested in something like that or maybe not.
Or if you look at the typical misspellings of Karlsruhe, very similar.
But how do you measure that similarity?
So one computer science way of doing that is just to look at the two
words.
So here we have a word.
There we have a word.
We just compare the different symbols.
And if we have a difference, if here there's an A and there's a B,
then we would say that's a difference.
We count the number of positions where certain words are differing.
Then we have the Hemming distance of two words.
Standard notion from coding theory.
We know if we talk about faults in codes, we talk about the Hemming
distance and we can characterize the ability to tolerate certain
faults by just looking at the Hemming distance in that code word.
But here we talk about similarity of words.
So if we look at the Hemming distance of Hausarbeit and Heimarbeit,
the Hemming distance is three because here A-U-S is just replaced with
E -I-M.
So Hemming distance is three.
If we look at Karlsruhe and Karlsruhe, the R here is missing.
But that means that at all these positions we have mismatches.
The R is missing, so instead of the R, we have an L.
Instead of the L, we have an F, and so on.
So a very large Hemming distance, but they are very similar.
So this should be something which we should also consider.
That's why we look at the editing distance, which is the number of
editing operations that are needed to get from one word to the other
word.
So if we type something, how do we actually get from one word to the
other?
So how many deletions do we have to make?
How many insertions of symbols?
How many symbols have to be replaced?
Or switched?
Sometimes we just switch two symbols.
Now the question is, what are the operations that are available to us?
If I can just delete and insert, I have more operations than if I
would be able to replace or switch something.
So we have to look at the allowed operations, and then we count the
number of operations that we actually have to use in order to
transform one word into the other.
And so if we look at the editing distance between Hausarbeit and
Heimarbeit, it's the same as before.
At least if we assume that we have replacements as operations, so one
replacement is one operation, then we can replace A-U-S with E-I-M,
and we have an editing distance of three.
If we would have just insertions and deletions, the editing distance
would be six, because we would have to delete three symbols and insert
three symbols.
So...
it could also be just six.
If we look at Karlsruhe and Kalsruhe, then we would have to insert, or
to get from that one to that one, we would have to delete one symbol
and add one symbol.
Editing distance of two.
And definitely those are, those two words are much closer, much more
similar than Hausarbeit and Heimarbeit.
Okay, so these are possible, these are distances that one could look
at.
And now the question is how can we actually do that, or use that?
How can we determine the editing distance?
Obviously it's very simple to determine the editing, the hemming
distance.
We just scan the word and check what difference is, but it is more
difficult to determine the editing distance.
How can we do that?
So, hemming distance is obvious, and for the editing distance, it's a
bit more difficult.
So if we have two words,
how can we determine how different they are?
So let me draw that in a different way.
So, certainly a simple observation is that if they have different
lengths, then we know that, well, we have at least to add certain, or
either to insert some, if we go from that, from the lower word to the
upper word there, we would have to insert certain extra symbols.
At least that.
But that certainly is just a very bad estimate.
The exact thing is to say, okay, is the size of U, this is the word U,
this is V, we look at the difference between those two words, how can
we get from U to V, or from V to U?
We can just, well, delete all the symbols of U, insert all the symbols
of V.
But then we have done unnecessary work.
Because it may be that we have a certain symbol here, maybe an A,
which is also occurring here.
Maybe it's followed by a B, and that B is also there, and then it's
followed by a C, and that C is occurring somewhere there, and then
there is a D, and the D is there.
Then certainly it would be unreasonable to delete ABCD and insert it
again.
So, if we delete all the symbols of U, and insert all the symbols of
V, we would have deleted all the symbols that are occurring in both
words, in the same sequence, and we would have inserted them again.
That means we would have twice done something with symbols which is
unnecessary, and W here is the longest common subsequence of U and V.
So it's the longest sequence of symbols that are occurring in both
words in exactly this sequence.
The longest common subsequence.
And so in order to determine the editing distance, what you have to do
is just determine the longest common subsequence.
But this is not that simple.
It can be done certainly, I will show you an example, or the algorithm
in a moment, how we actually do that.
But it's not as simple as just computing the Hamming distance, which
obviously is done in linear time, linear in the size of the words.
So editing distance is something which is more interesting.
I said your proof is exercise, I just proved it to you by this here
screw and also the other one.
So this is not very difficult to understand.
And what the longest common subsequence is, is obvious.
Here, formally, it means we have a certain, like we have our word U
and we have a word V U and V and we have some U0 here, we have a V0
there, and we have the W1 there, we have W1 there, and then we have a
U1 and a V1 and so on.
So we have these there somewhere a WK, and we have a UK, and here also
we have somewhere a WK and we have a VK.
So we have these words, W1 to WK occurring within the word U and
occurring within the word V and it is the largest or it is, first of
all, it is a common subsequence occurring in both words, and then we
are looking for the largest of those subsequences which are occurring
in both words.
And we have to determine that.
This is just the formal definition of a common subsequence and now we
should look at how we can actually do that.
You could actually utilize such a thing, like similarity by saying,
okay, if I send a query to a search engine, that search engine should
also look for all words that are at editing distance, at most, two.
It means, just the difference is just inserting one or two symbols or
inserting one, deleting one certainly you have to say what kind of
operations you allow here, if it's insert delete or replacement or
switching.
So this has to be specified, then you can search for something which
is similar to the words that you actually have input as a query.
Okay, let's now look at how we can compute the editing distance.
Hello.
Welcome to the final part of this lecture.
Okay, so here it is called the so-called Lievenstein distance.
It's known under very different names.
It's just the editing distance.
But Lievenstein has designed this algorithm.
Many people have designed this algorithm.
Hirschberg is also one, which is sometimes called it, as somebody who
was looking at that.
Here, the special thing is that we look at three operations.
We look at insertions, deletions and replacements.
Three different operations that we allow for editing and then we would
like to see how or what the distance is of two words.
Here we call them S and T.
So, here we have S and we have T.
Now, this word has let's assume these are N no, M here I said.
So, M symbols.
Here we have N symbols.
One to N.
And now the approach is a dynamic programming approach.
You know what dynamic programming approach means.
It's a standard approach to output to address certain problems.
We first of all look at the small problems, solve those small problems
and then address larger.
So we solve small problems, list of small problems, then would like to
solve larger problems by just combining information from these smaller
problems.
And so this is not divide and conquer, but it's dynamic programming.
We just use the information from small problems in order to get the
solution for the larger problems.
Usually we do that in a tabular approach that we know that that's why
we usually fill some kind of table and that's the standard name for
dynamic programming.
Now what are we doing here?
What is the dynamic programming approach in this sense?
What is the simple problem?
The simple problem would be to look at just the first symbol of S and
the first symbol of T and look how much information or what kind of
operations are necessary to get from the first symbol of S to the
first symbol of T.
If it's the same, we don't have to do anything.
If it's different, we should have to replace something.
Or maybe we have to delete something or insert something.
These are the different operations.
Then we look, essentially, if we have two symbols of S, how can we get
from two symbols of S to one symbol of T?
We have three.
And so on.
Or more general, if we have all the symbols from 1 to i, this
substring and a substring from 1 to j and t, how many operations are
necessary to get from this substring here, S1 to S i, to a substring
T1 to Tj.
This can be done by looking at this small information.
So we build up a table.
And this table essentially looks like this.
We have here our word and we have here essentially S 1, 2, 3, and so
on.
And we have T.
No, other way around.
This usually T is up there, S is here.
S1, 2, 3, and so on.
And so if we have assumed we have here just dot dot dot, and here we
have an i, and up here we have j.
Now, we would like to fill in this field here, the field i, j.
And we would like to get there the value d i j.
Now how can I get d i j from the information that is already in the
table?
I assume I have started here and so I assume that I have information
in this field here, which is i j minus 1.
I have information in this field, which is i minus the distance, I'm
referring to transforming the string S up to i minus 1 into T up to j.
And here I have i minus 1 j minus 1.
And now we have to this is exactly the information I need in order to
find out what the distance, or what the number of operations is that I
need to get from S 1 to S i to T 1 to T j.
So how can we use that?
So if I look at d i minus 1 j, d i minus 1 j means from S up to the
position i minus 1 to j i minus 1 is this one here, I have a shorter
sequence if I would like to use that number, I know that I would have
to delete the symbol S i in order to have exactly the distance that I
had for S 1 to S i minus 1 to get to j.
That means I would have to delete one symbol.
That means the number of operations is the number of operations I have
to get from S 1 to S i minus 1 one symbol to the left of that and
transform that into T 1 to T j.
So if it's just a deletion, I would have d i minus 1 j plus 1.
I could look at the same row here and look at what would happen if I
look for the distance, the number of operations I need to get from S 1
to S i to T 1 to T j minus 1.
If that is the same as going from i to j it means I have to insert
something.
I have to insert the symbol T j.
Another operation.
So that would mean this distance plus 1.
Now, if I look at this entry here I have to compare the symbol S i and
T i S i and sorry, S i and T j If S i and T j are identical I don't
have to do anything.
I have the same distance as I had for transforming S 1 to S i minus 1
to D 1 to T j minus 1.
If they are different, I just have to replace the symbol.
And so, these are the possibilities for getting the distance or the
number of operations that I have to execute in order to get from S 1
to S i to T 1 to T j.
And I certainly take the minimum of that.
Because I don't want to execute extra operations.
I just take the minimum of the possible choices.
And so, by just knowing those three entries I can fill in the adequate
information there.
That means I can start here and then enter those values there.
This is very simple.
I can actually generate from nothing the term T 1 T 2 T 3 and so on.
Very simple.
So this is just 1, 2, 3 and so on.
Here I have 1, 2, 3, 4 and so on.
And then this is simple.
And so then I can fill in that field, I can fill in that one, I can
fill in that one.
Very simple operation.
It's just a scanning of those, of that table, at every table at every
entry I just have to compare those three values and so definitely this
is just an operation which takes time n times n.
I have to look at all the different fields in there and so this is a
quadratic or you could say just the product of the length of those two
terms and in that way I have information on how many operations I have
to execute in order to get from S to T.
Now if we do that for a simple example here you see exactly again
these four possibilities that I just listed.
The initial thing would be if we have nothing the empty word how can I
generate from the empty word the word Saturday.
I just have to enter those symbols, insertions.
How can I again here, how can I get from zero to that word, again
those values and then here from S to S certainly this would be a zero.
The smallest value, you have the same symbol.
If we have S to A now here we have this would be one because we just
have to insert one symbol.
And so on.
I don't want to go through all these different fields here I will just
show you what happens here.
This is the complete table filled in using always computing always the
minimum of those values that have to be compared and so we get here
the values and we also get these links which just indicate how we have
or which term actually is which operation has been taken in the going
from this top left to the bottom right entry.
So in this way we see how these are generated and then certainly to
get actually the distance from getting the editing distance between
Sunday and Saturday we just have to look for the smallest entry here
like this is the final value indicating three and so if we now follow
that line here we finally get to or see how these operations are
actually executed.
So this is indicating what we have to do to get from one word to
another one and how we can execute or how we can calculate the editing
distance of two words using or assuming that we just have deletion,
insertion and replacement.
Do you have a question?
That's just the button.
The line is there.
Yeah.
Okay.
I think it's so this is just showing you the line following the
smallest values there and so we have the editing distance indicated
there.
Okay.
We can use pseudocode for that.
I don't want to go into the details there.
This is just this calculation which I told you about.
We don't have to go into the details of that algorithm.
In fact, you are all capable of transforming something which I have
explained to you just now into a code of a program.
This is not that interesting really to write a program if we know what
the algorithm actually is about.
Okay.
The important point certainly is that the complexity is just a product
of the two words that we have there.
And then we would like to now look for documents in...
no, look for words in documents.
I would like to follow now this assumption one, that we would like to
do a full text search, look for the occurrence of words in documents
and for that we have to find out how we can actually do that.
So the input for that would be a document and a word.
We would like to check does this word occur in that document?
We assume that the document has definitely a larger length than the
word otherwise we wouldn't have to look for that.
And what we would like to get are all the positions where W starts in
D.
So if we have our string here, our very long document written as a
sequence of symbols, then if W does occur there, we would like to get
that position.
Or maybe if it's occurring several times, we might also want to get
that position.
So maybe we would like to get all the positions of where a word occurs
within a document.
As I told you, you might be interested in finding out how often a term
actually is appearing in a document.
For that we need the number of occurrences, not just does it occur.
This would be the initial thing we would be interested in.
So, what we would have to look at is something like define something
like a finite automaton which is capable of finding out whether the
word W occurs within some document.
Simplified here by writing just the asterisk W and asterisk we check
whether D is, well, this is formalism to say D is an invert of the
language of that automaton.
So we could just specify the automaton very simply.
We just write a non-deterministic automaton having like this starting
state here, and then if we look for uni, we would just write those
finite automaton in this way and that's it.
Just implement that and you can execute the query.
Now this would take a bit of time.
You would need a deterministic version of that.
We can write that as a program.
So how do we write that as a program?
We would just for well, this is written now in a Pascal-like or not
Java -like version but it's easily readable I think.
So we just go into a loop from 0 to 1 per n-m.
So certainly the final the rightmost position could be n-m because we
look for complete occurrences of the word.
That's why we only have to look for... let me rewrite that here.
We look at possible occurrences.
So this would be one position i that we look at and then we would like
to check whether starting from that position i we actually have at the
positions i plus 1 to i plus m exactly our word w in there.
So j is set to 1 and then while we scan through that word and while
the document is exact or has the same symbols as w at those locations
we increase the value of j and if after we exit that loop j is larger
than m it means that all the symbols actually match and we have a
match at position i plus 1.
Because we looked at positions w1 we looked at the symbols w1 to wm at
positions i plus 1 to i plus m.
So this is a very simple algorithm.
Trivial.
That's it.
Pattern matching.
But that now has to be analyzed.
How much time does that actually need to execute this algorithm?
We have a loop there this is one loop, this is another loop this loop
is running from 0 to n minus m if m is a constant or a small value
it's approximately n here we have at every position what we do here
actually is at every position from i to n minus m, we might scan
through almost all the symbols of w so the upper bound for that would
be n times m.
Quite a long time.
The point is if we have for example come to such a position and then
notice well, there's a mismatch here's some kind of mismatch, some x
which does not occur in our word we have scanned through this prefix
of the word and noticed these symbols are occurring in the document.
And now this is information one should not lose because we have this
information and then we should exploit that.
And to exploit that is something which Knuth Morris Pratt did a long
time ago when people looked at these pattern matching algorithms so
what we actually notice is we have been at some position so this was i
this is position i plus 1 and we notice a mismatch here's a mismatch
and if we have a mismatch we should not just move the word the
potential pattern here one position to the right but we should exploit
the knowledge that we have about this prefix we should look at the
structure if we know that the first symbol here is not occurring at
all in the remaining positions here we can immediately shift So what
we should do is, we find out how many symbols at the prefix of our
pattern, how many of these symbols occur to the left of the symbol wj
in our pattern.
So if those symbols here reoccur at this position, then we know we can
shift the pattern exactly by that distance.
And we would like to optimize that distance, shift the pattern as far
as possible to the right, but certainly not too far, because certainly
this could be a potential new starting position.
So we would like to indicate the next possible starting position of
the pattern and shift it exactly that much.
But that also means we don't have to look again at those locations
that we have already scanned, because we will shift the pattern as far
to the right as reasonable, exploiting the information that what is to
the left of the wj is exactly the same as before, but the symbol that
is at this location here, so the symbol that was there, certainly
should be different from wj.
And then we can optimize the performance of the algorithm, and that's
the Knuth-Morris-Pratt algorithm, which runs in linear time and not in
time, like in time order of n, because we only scan every symbol here
once, we only increase those values, and we can shift larger distances
and then can improve the efficiency of the algorithm.
Okay, that's it for today.
Thank you.