So, good morning.
Welcome back to the course on Algorithms for Internet Applications.
Today I did not start the feedback tool because I got the impression
that you don't use that, so that's okay with me.
If anybody wants that, just ask for it.
So, last time we looked briefly at the remaining parts of internet
technologies.
We had looked at the TCP algorithms.
We had like the slow start and the...
I think I should briefly open that just because I always make that
brief repetition of what we did.
So, let me briefly go in there.
We had looked at... that was long ago, IP protocol.
We looked at completely other things.
Meanwhile, we had looked at TCP header format.
We had looked at the meaning of the header fields for TCP.
We had looked at why certain information entries there are necessary.
We had looked at the TCP connection management, how logical
connections are established, how data is actually sent and controlled,
the role of the sliding window protocol.
I showed you that.
And then we looked at the dynamic flow control, the slow start
algorithms where we have a gradually increasing or steadily increasing
then window size which then is at some point growing slower if you
have reached that threshold value which is changing all the time
whenever there is a fault in the... like a missing acknowledgement in
the communication.
Then the window or the threshold value is reduced by half and we start
again from the initial window size.
And that's why we have this varying data rate when we transmit
something with TCP.
I showed you then briefly the slide on UDP and finally one slide, very
brief, on SETP, on ATM and that was the remainder of that chapter.
And then we start with chapter 6 where... there's chapter 6, there's
chapter 6...
where we started to look at the way we can actually search for
information in the Internet.
I showed you... this was the last slide... this classification of
search engines.
And then we start with the new slide today on how search engines
actually work.
So they have several elements.
There is the spider which is crawling over the Internet which I guess
some of you know already, so we have all the nodes.
And then we have... like it's called... since this is a network, we
say we have some kind of spider which is just crawling from node to
node which means that all the nodes, all the web servers are visited.
And so the program, which is the crawler or the spider, goes to a
webpage or a website, reads and analyzes the webpages, analyzes it,
retrieves information that is relevant and then follows links from
that webpage to other webpages and so in this way explores the net
depending on the link structure of those documents.
So in this way it can detect all the large numbers of documents in the
Internet.
Somehow the information has to get into the catalogs in order to be
able to actually respond to search queries.
So you have to first of all detect that information is available
somewhere on some website and then if they are linked by hyperlinks
then you get to the next pages and they are detected, analyzed and the
information is retrieved and stored in a reasonable way in that
catalog that I mentioned on the previous slide.
So this is one part, to detect what is there.
And then it has to be up-to-date information always, so the
information has to be updated.
So regularly these pages have to be revisited because one essential
point in what we have on the web is that the information can be
dynamically changing, so all the information, all the documents are
visited regularly, have to be visited regularly in order to be able to
actually maintain an up-to-date database on what is available on the
World Wide Web.
And so this means quite a bit of effort that has to be undertaken in
order to have an up-to-date catalog of the web content.
And then this catalog is the index, and this index just is this large
table with all the entries, all the words that are somewhere available
and you have the links to the documents that actually contain relevant
entries that are listed in that index.
So it is, as I said before, like a giant book where you have a copy of
every webpage, certainly not a copy of every webpage, but you have
links to all the webpages.
And this has to be updated whenever changes are detected and only the
pages that are available in that catalog, in that index, are available
for searching.
So if you can put as many documents on your web server as you like,
only those that are detected at some point by a search engine can
actually be found as a result on search queries.
And in order to be able to do that, we know that we have billions of
webpages available in order to be able to actually provide responses
to a query in such fast time as we are used to.
This means we need very efficient data structures to be able to
actually provide that information.
And we will look the following little bit at what it actually means to
analyze a document, to find information inside a document, and also to
then respond to queries of what kind of data structures you actually
can have to support the detection of information in documents.
So the search engine software that you have then has the task to...
well, certainly it has to be able to...
or the spider and the index are part of that, or the services around
the index are part of that, the spider is part of that, but then the
search engine software has to analyze a query.
You write a query into the query field of a search engine, and then
this has to be analyzed appropriately.
Then it searches the index for documents matching that query, and it
ranks those documents with respect to relevance.
And this is one of the most... or these are very essential for our
feeling how relevant or how well-performing actually a search engine
is, because what we would like to get is a listing of all the
documents that are matching our query, and we certainly would like to
have the most relevant documents listed in the front.
And if we notice that in the response to a query, those entries in the
first links here on that list don't really give us the information we
are looking for, we don't like the quality of that search engine.
Meanwhile, you know that if you look at what happens as a response to
a query, you have a certain part there, all kinds of entries, which
are just ads.
Commercially entered information, which very often has only very
little to do with your query, just because they have paid for being
there.
This is very annoying, but somehow they have to make profit, so that
has to be accepted properly.
And then there are certain things like they send you this list of
links, and then you assume, for example, if they send you a link to
such a document over here, that this link here would directly lead you
over there, but that does not happen.
You are always first linked back to the search engine, because they
have to know how you responded to the responses to a query.
So you will never get direct links from the response to a query back
to the pages that are listed there, but you always are redirected
first back to the search engine, then they notice how you respond to
their response to the query, and then they forward that request onto
the page that you are actually looking for.
So these are things which you might have noticed, that when you list
on the links in the responses to a query that you put at Google, you
first always visit Google, and you don't get directly to the pages
that you are interested in.
We will look at these things in a little bit more detail in this
chapter.
And one of the main points is what actually are the points that
influence the relevance of a document with respect to a query.
So we would like to make statements on the quality of this information
retrieval, and there are certain standard criteria how we actually do
that.
From information retrieval, long-established quality criteria...
The first of this is the so-called recall.
You have a number of documents which you might be interested in, which
are on your database, and then somebody asks for certain documents,
and you get a response.
So in green here, you have all the documents that are retrieved, as
listed on your web page there, on your browser window.
And then you say the recall is the fraction of the relevant documents
that are in the database that you actually received.
So you received certain documents, but the number of relevant
documents can be much larger, so it's the fraction of the retrieved
relevant documents that you actually get.
So that is this fraction here.
That's the recall.
How many of the relevant documents were recalled from the database?
The next point is precision.
You look at the number of relevant retrieved documents.
How many of the documents in your response to the query, actually, are
relevant?
That means how correct was the response, how many irrelevant documents
did you get?
And if you just look at the fraction of relevant documents in the
response to the query.
You don't want to get irrelevant documents, but you always get some,
or very often get some irrelevant documents.
And there are all kinds of variants of these two criteria, recall and
precision.
And what you can immediately notice is there are very simple ways of
actually making sure that you get perfect recall.
What's the easiest way to present or to actually get perfect recall?
You just give, as a response to a query, all the documents that you
have.
Then all the relevant documents are there, you have perfect recall.
But the precision probably will be very bad.
If you would like to have perfect precision, you just send back one
relevant document.
100% precision, because if you know that's a relevant document, you
only send this one, and you have perfect precision, but the recall may
be very bad.
And so the quality of a search engine has to be managed in a way that
you make sure that you perform well with respect to those criteria.
You should provide links to most of the relevant documents, and you
should not provide links to irrelevant documents.
And this is the challenge that you have if you organize such a search
engine, that you must ensure that, well, no irrelevant documents, and
you should provide the most relevant documents, or most of the
relevant documents.
Now this assumes that we have some binary decision, relevant or not
relevant.
This certainly is not the case.
We have some quantitative measures of how relevant a document is.
You can insert a threshold and say everything above a threshold you
call relevant, and everything below a threshold you call irrelevant.
And then, I did not mention exactly this diagram here, this is just
indicating what I just said with these two examples.
You may easily get a very high precision or a very high recall, but
that always leads to something which is bad for the other measure.
And so, what you would like to get is something in between as far to a
best recall and best precision.
Okay, now the question is, what actually makes a document relevant for
a query?
And for that, you can give several answers.
Many different criteria have been developed to determine the relevance
of a query.
And we have had many, many different search engines.
They all had their own view on what is relevant.
Some are common to all those search engines, some are specific to some
search engines, and we will look at a few of them.
So certainly, if you have a document and you are looking for a certain
word, then if that word occurs somewhere, you should say, okay, that
document must be or can be relevant if the query term is inside the
document.
So, match or no match of the query term that you have here in your
document.
Then, the question is, maybe you have several of those matches.
A term appears several times in a document.
Obviously, it should be a good indication of the relevance of the
document if the term that you are looking for is appearing very often.
So this, at least, is an indicator.
This is the number of matches.
And then you may have, this is actually the next point here, was the
number of query terms.
You may have several query terms.
If they all appear in your document, then it should be really relevant
because all the terms in your query are actually in that document.
And then, this is the number of query terms that match actually in
your document.
And then, it might be of interest to look at where actually a term
occurs.
So, if you have a very long document,
and there you have the terms that are in your query.
You look at that document, and that's your window on that document,
and you slide that down with your browser.
You don't notice that those terms of your query, and you say, this is
bullshit.
I don't want this search engine anymore.
It provided an irrelevant document.
The terms are just at the bottom.
So, in order to make sure that the recipient of that response to a
query gets the impression that this is a relevant document, or it is
also a relevant thing, if the query terms that you have appear in the
title of your document, then it should be really relevant.
If it appears in the abstract, another point where you say, okay, that
must be relevant.
And so, you just look at the distance from the start of the document
where actually a term appears.
And the further down it appears, the less relevant the document will
be.
So, these are the number of things that you look at.
And then you can also look at the quality of matches.
You can have a complete or partial match.
You can have misspellings of a word, different versions of a word that
you look for.
And so, do you only go for documents which have exactly this word as a
match, or is something which is similar also relevant?
And so, this is an important point.
And then, there is sometimes direct information on the relevance, meta
-tags.
I hope you know what meta-tags are from HTML documents.
We know that there we have a leading part in the beginning where you
have meta-tags.
And you can provide information in these meta-tags on certain keywords
that are of interest for somebody who wants to look at that.
So, there you can provide keywords that are relevant for a search
engine.
Not all search engines actually consider the meta-terms, but most of
them actually do.
And so, in meta-terms, you can indicate to a search engine what query
terms should match that document.
And this is very important.
So, if you design a webpage, these fields, the meta-terms that you
have there are very important because there you can direct the
responses to a query that had been sent to a search engine.
And this means that if you are a designer for a webpage, then you
should know how actually the relevance of a document is evaluated.
Because this will hopefully influence, if you are a good designer,
this will influence the way you present the information.
If you would like to be at the top-ranked documents in the response to
certain queries where certain search terms are looked for, you must
make sure that your document is actually ranked very high.
It must be ranked very relevant.
And so, this is a very important point to know how actually search
engines evaluate the relevance of a query.
And then you can try to actually design your document appropriately.
There have been all kinds of attempts to get unjustified high ranks by
just putting in certain words which many people might actually ask
for.
You just look into the statistics that I showed you last time at
Search Engine Watch.
Statistics on the most frequently searched terms in questions to
search engines.
These statistics are available.
And then you just make sure, if you design a webpage, that those terms
are on your webpage.
And then you could direct all the queries to your webpage.
But this is spamming.
This is unjustified.
But nevertheless, you have to know how that is evaluated, and then you
can do something.
We will look at a few more components.
Like what I did not mention here is one important component or one
component aspect is, for example, the link popularity of certain
documents.
We will come back to that later on.
That's one of the major criteria of Google.
Then the statements on relevance certainly are not unique.
They depend on the method of evaluation, so different search engines
can have different results in their evaluation of the relevance of a
document.
We will come back to that notion of relevance a little bit later.
I just wanted to briefly mention what kind of ideas one would have
with respect to that term.
Then the question is, what actually is a query?
A query is, well, a specification of some string.
So we just ask something.
We specify a string, a word, a term, or maybe several words.
Then we would like to search for those words in a document.
There are some statistics on how long queries are.
I guess this will be changing over time because people tend more and
more just to search or just to put in a question or something.
So this has been some statistic that tells that you have 2.35 terms on
average in a query.
Maybe true, I don't know.
It depends.
I don't know how you are actually searching.
So here is just a maybe a little bit strange way of looking for a
certain document.
So this certainly is very obvious.
You can look for University of Karlsruhe.
Nobody will find an University of Karlsruhe because that's not
existing anymore.
But there may be documents which are still there.
You can look for algorithms.
So there would be different ways of phrasing a query.
You could say, well, what does it actually mean to look for documents
containing certain words?
A document is in some way just a sequence of symbols.
That's a sequence of symbols.
And the search query or the search term should appear somewhere in
there.
And it means that if you describe that formally, the documents that
match your query are members of this set here.
You have any symbols in the start of your document.
Then you have University of Karlsruhe.
And then you have some other symbols after that.
So this is just a language of documents or a set of words which have
this pattern inside.
So you could say a query corresponds to a regular expression.
You can use regular expressions which you know from language
descriptions, language models, to actually describe a query.
Or essentially you describe the set of all documents which match that
query.
Essentially you could say if a query corresponds to a regular
expression, it means if you would like to detect whether a certain
document, like this document there, if that document matches your
query, what you are doing is you are running a finite automaton on
that input and you look whether that input is accepted by your finite
automaton which corresponds to the regular expression.
That's what you are formally doing.
That's what a search engine does.
It analyzes a query and it means that you actually look for whether a
certain word has that pattern inside.
We will look at efficient ways of actually looking for patterns.
So this is one assumption, that the document is just a sequence of
symbols from some alphabet.
And then you would look for occurrences of patterns inside those
documents.
Now if you would do that actually when we are executing a query, then
it would take very long to actually find all those documents.
So what I said before already is that the document is not just, or
when you respond to a query, you don't actually go to all the
documents and look for occurrences of those patterns, but you have
some pre-processing, the document is represented by the index, and you
have a data structure which allows you for efficient retrieval.
And then you get all words of the document somewhere in that index,
and then you can actually get faster responses.
You know that when you look, for example, through all your emails, for
certain words that are in emails.
This may take some time, but if all your emails are indexed, it's much
faster.
Because then the emails are not scanned through as a text scan, but
then you just look into the index and get directly to those messages.
And if your index is incomplete, which sometimes happens, it's really
annoying if you look at how, for example, Outlook does it, at least my
experience, sometimes the index is not complete and I search for
certain emails, and I don't get the hits that I know they must be
there, I just don't get them because they have not been entered into
the index currently.
Then I would much appreciate it if I would have the option to just
switch off the index and scan through directly, which is not often, at
least I don't know how to do that.
Maybe it is possible to do that, but this is the point of how you
actually organize your search.
Do you search directly in the documents?
That's assumption one.
Or do you search just in an index?
And then the quality of the responses depends on the quality of your
index.
Okay, we will look at both parts.
We will look at searching directly in the text document, which
certainly you have to know how to do.
This is the basis for actually finding something in a larger document.
And if you look at any document, you would like to find a certain
word, you have to know how to scan the text for an occurrence of
patterns.
So let's just look at the first part.
Again, I hope you remember what a regular expression is.
You have operations plus some product and iteration.
And this is all known to you.
And then you can simplify that.
You can say you have the empty word instead of empty set iterated.
You can say you just put a question mark after some expression.
And it means that it's either exactly that expression or not.
So you look whether there are some occurrences of that.
But you can also look for the empty word.
Or you have letters within brackets.
And you mean that you are looking for all the symbols in between AI
and AJ, assuming that you have a linear ordering of the characters of
your alphabet.
Or you could say, well, I would like to look at iterations, but not
like arbitrary iterations of a certain term.
But I would like to look whether maybe at most K occurrences are of a
certain pattern in a document.
Or I would look for whether there are at least K occurrences of a
certain pattern in a document.
You can specify all this with some notation.
So I give an example here, which would be a way of actually
formulating a query, which looks rather complex, but actually it is a
very simple way of writing, a very formal way of writing, or a simple
formal way of writing a query.
It means that you look for documents starting with just some arbitrary
sequence of characters.
And then you would like to have either a capital or a small A.
Then you have L-G-O-R-I-T-H-M.
And after that, you would like to have either S or U-S or E-N or I-C
or I-S-C-H.
And this could appear, but need not appear.
Even a document which does not contain anything of those is matching
that query.
And then you say, after that you can have an arbitrary number of
characters, but this should appear at least five times.
And after that, you have an arbitrary sequence of characters.
So this would be a query which looks for any variance of the word
algorithm, which should appear at least five times in your document.
This would be a formal way of actually specifying such a query.
Now, I guess you have never seen such a formal way of doing that.
If you look into the more sophisticated search interfaces at search
engines, they offer you more opportunities to specify your queries
more sophisticated than the queries that you put in the initial query
window.
So this is something which you can do, which to some extent is
actually offered by search engines, but normally you would not write
it like that.
But you would like to be able to actually assume that if you write a
word in a query, certain variance of that word should also be
considered to be relevant and not just the one term that you write.
So you would like to have something where, well, maybe you just write
algorithm, but all these other parts, or you write algorithms or
algorithms, and you would like to have documents also which just match
partially.
So you would like to have documents which contain similar words.
This is something which in some way you have to capture what actually
are similar words.
This is what we will look at next.
So search engines, as I said, allow for simple specification of
queries.
I already showed you last time a link to that webpage here, search
engine math at search engine watch, where they tell you how to
actually formulate a query using some product and iteration and a few
more formal ways of actually constructing a query, which then allows
you to have more efficient searches.
So I don't want to go there today again.
I did that last time.
Before I come to this notion of similarity of search terms, let me
briefly show you this statistics on actually experience how search
engines respond to certain queries.
And this is sometimes very interesting to see how they differ.
I did not update that this year.
I did it last year.
There are always some changes, but the entries that I have here just
show some effects.
So what you can do is, for example, like in a normal search engine, in
Google or Bing or so, you can search for something like Angewandte or
Informatik or Universität or Karlsruhe, which means that you look for
the occurrence of at least one of those terms.
This is a Boolean query.
And so Boolean operations, conjunction, disjunction and complement are
also used.
So I did that at Bing and at Google.
The problem is if I go to, for example, Yahoo or to some other of the
old standard search engines or AltaVista or whatever we had there,
very often they use either Bing technology or Microsoft technology or
they use Google technology.
And so you get the same results.
So I just looked.
Those two are different, as you see.
So here I got 16 million pages back from Bing, 181 million back from
Google.
And so they contain just at least one of those words.
If I look for the occurrence of all those words, then much reduced,
712,000 at Bing, 151,000 at Google.
You see definite differences there.
Then I looked for something here where I said, and not mathematique.
So mathematique should not occur in that document.
You see 18,000 pages at Bing, 121,000 at Google.
I did not check whether those 121,000 pages there actually satisfied
exactly that query or how relevant they were, but you see different
responses.
And then you can also use plus in those here.
So this is similar to conjunction.
22,000 pages at Bing, only 27 at Google.
Interpreted in a very different way.
I should know.
I just have to... we can find that out.
Let's go to Search Engine Watch.
The formal interpretation of plus and product has been changing over
the years.
Using the plus symbol to add.
Sometimes you want to make sure that the search engine finds pages
that have all the words you enter, not just some of them.
The plus symbol lets you do this.
But this is not true for Google.
Now I remember.
The plus sign... this is something you should know.
Let me go back to the... and now remember what happened there.
The plus sign used in Google means you look for all documents that are
listed in Google+.
So you look for all documents in Google+.
That contain the word, in that case here, Angewandte Informatik
Universität Karlsruhe.
So this is... they just redefined the notion of plus in a search term.
That's why they have only 27, because nobody is using Google+.
So that's how these queries are responded to.
And then you can certainly also use quotes to look for a string.
So this is not just looking for occurrence of those three terms,
Angewandte Informatik Karlsruhe in any ordering, but exactly that
term, that sequence.
And there you have a few thousand at Bing, 1,220 at Google.
Very different numbers.
And some years ago I had made these test queries for some search
engines.
All of a sudden I got more responses, for example, for a conjunctive
query than for a disjunctive query, which does not make sense.
So one has to be very critical in what they actually do, and it's
reasonable to just now and then look at how they actually respond to
queries.
So I just want to say somehow here we have to look very clearly into
the technology.
We know quite a bit about what kind of algorithms these search engines
are using.
We don't know everything, because certainly some things are just
company secret.
But the major algorithms are well known, and I will just mention some
of them.
Now, let's look at what I mentioned.
We would like to be able to search for documents containing not just
this one word, but also words which are similar.
Now the question is, what does it mean for a word to be similar to
another word?
I'll give you examples.
Here we have different words.
Hausaufgabe, Hausarbeit, Hausaufgabe, Heimarbeit.
Obviously look similar to us.
Or Stadt, Städte, Stadt look similar.
Where certainly Stadt with DT is very different from Stadt with double
T.
And we would not actually look for something having the word Stadt
with double T, because that's not a relevant word.
But certainly if you look for Hausaufgabe, you would also like to get
documents having hyphens in between.
Or you look at all kinds of misspellings of a certain term.
Some webpage designers actually exploited things like that and
redirect or have just reserved domains which correspond to
misspellings of favorite URLs.
So you can always try to exploit those technologies in all different
ways.
But how do we actually... if we say, okay, I would like to look for
Karlsruhe, and then I would also like to get links to documents where
the author has misspelled a certain word.
And so the question is how we do that.
We have similarity measures available in informatics.
One is the Hamming distance.
You know how we do that.
We have two words.
And we just look at every position in the word.
And wherever we have different entries there, we count all those
positions where we have differences.
That's the Hamming distance.
And it means that if we look at the Hamming distance of Hausarbeit and
Heimarbeit, it is three.
Because only A, U, and S here are different.
Everything else is the same.
If we look at the Hamming distance between Karlsruhe and here the R
has moved somehow to the right, there the Hamming distance is seven,
because you have mismatches at all those positions.
It looks very similar, but with respect to the Hamming distance, they
are very different.
So it doesn't look to be adequate.
Another thing is the editing distance.
The editing distance corresponds to how we actually type in a word or
how we edit text.
How do we edit text?
We edit it by inserting something.
We type on the keyboard.
We delete something.
We might replace something.
Or we might switch certain words.
So there are different operations.
You could imagine other operations, but these are the major ones.
The simple ones are just delete and insert.
Maybe you have replace.
If that is one operation, it just counts one as one operation.
If you don't have that, you certainly can always simulate a replace by
delete and insert.
But then you have two operations.
So if you count the number of editing operations that you need to get
from one word to the other word, then it depends very much on what
kind of operation you have available.
And very often we look at exactly those three.
Delete, insert, and replace.
That's one of the standard things.
Switch very often is not included.
You could also include that, but it depends on what actually you would
like to allow as editing operations.
And then if we would look here at the editing distance with respect to
those operations, like Hausarbeit and Heimarbeit, here we would have
the same distance between Hausarbeit and Heimarbeit as for the Hamming
distance.
But for the words Karlsruhe and here this Karlsruhe, we would have an
editing distance of two, because we just have to get from Karlsruhe to
the other one, we have to delete the R, and we have to insert the R in
the end.
That's just two operations.
So it looks as if the editing distance is something which is more
adequate, because the words that you get there look closer to what our
intuition is about similarity of words.
So that's why we will look at that a little bit more.
Obviously, it looks as if the way we would actually determine the
editing distance is simple for the Hamming distance.
You just scan through the two words that you are looking for, an easy
way of calculating the Hamming distance.
But for the editing distance, it doesn't look that simple.
Because how do you know which operations you should actually use,
insert, delete, replace, whatever you have available.
And so Hamming distance is simple.
Editing distance is a little bit more difficult, depends on the
operations.
Then we could have, for example here, arbitrary replacement.
You could have replacement with characters which are neighbors on the
keyboard, something which happens very often, that you just hit the
wrong key.
And so you could look at those things.
You could look at insertion of hyphens, blanks, or these things.
And so these are all ways that you could allow in there.
If we just look at insertions and deletions, at least those two have
to be there, those operations.
We could easily make some statement on the editing distance.
So if we have two words, U and V,
and we would like to look at the number of editing operations.
Well, if you just look at the difference in length, certainly you need
to act, if this is U and that is V, certainly in order to get from U
to V, you have to at least insert certain characters in the end.
Maybe you have to do more.
This is a very simple way of estimating that.
The exact value actually is the length of U, plus the length of V,
minus two times the length of W.
Now what is W?
W is the longest common subsequence of U and V.
So what is a subsequence?
Well, a subsequence is some subsequence of U, and this might appear
also here somewhere, maybe at the same position.
The same appears there, and then you have another part there, which
might appear somewhere over there, and then maybe you have a long
part, which appears somewhere at the end.
So you look for the longest common subsequence.
Here's a formal definition of that.
You have your words U and V.
You say that your word U contains some W1 to WK.
There's some other letters in between, and your word V contains the
same W1 to WK, and this is then a common subsequence.
And you look for the largest common subsequence of two words, which is
not that obvious how you would actually compute that.
And why is that actually?
Here I say proof is an exercise.
The proof is rather simple, because what do you have to do if you say
it is the length of U plus the length of V
minus two times the longest common subsequence.
So to get from U to V, you might have to delete certain parts from U.
You will have to insert certain parts of V.
That means if they're completely different, you would have to delete
every character from U.
You have to insert every character of V, that is the length of U plus
the length of V.
But then you did too much, because you deleted the symbols from this
longest common subsequence in U, and you inserted that again when you
built up the word V.
So two times the number of characters that you have in the longest
common subsequence have to be reduced, or have to be subtracted.
Because you don't have to delete those elements in the longest common
subsequence, and you don't have to insert them afterwards.
That's why you have exactly that value here.
That's the distance, the editing distance of two sequences.
Now the question is how do we actually do that algorithmically, and
it's not that difficult to do that.
We'll come to that in a moment, just one other notion how you would
use that.
So you could say, for example, you would like to search for all words,
such that the, or you would like to, I should say, you search for all
documents containing words that have an editing distance of at most
two from your query term.
It means you just allow for a certain deviation from the correct word
that you put in your query, and the similarity search should allow to
also look for terms that are similar at a distance of two with respect
to the editing operations, whatever you allow, insertions, deletions,
or replacements, or switch, or that depends on how you implement that
editing distance.
And now I would like to show you an algorithm how we do that.
So there's actually a special name for a special editing distance
definition, so the Lievenstein distance.
There we just look at insert, delete, and replace.
So that's a special name for editing distance with these three
operations.
And in order to be able to now determine the editing distance of two
terms, we follow a dynamic programming approach.
So what do we do?
We just form a table.
Dynamic programming always means that we in some way build up a table.
And we start from simple information, basic information, and gradually
build up more complex information.
So we put the two terms here, so let me say here A1, A2, and so on, to
A, N, or M, it doesn't matter.
And here I put in, oh here I have S, sorry, I should put in.
This should be, for example, T.
There I said S1 to M.
So this is a T always, and here we have S1, S2, and so on, up to S.
No, this was, sorry, T, N, doesn't look nice.
And here we have S, M.
And we would like to show now how we can actually get from the word S
to the word T.
That's the editing distance.
And we start by just looking at how can we get from S1 to T1.
How can we get from, that's obvious, is it obvious?
So we assume that we have certain entries which are already there, so
it is very simple to put in the first line here.
Actually, we start here, I should have inserted, I should have left
one row open here, because I should input here the empty word, or the
empty word there, and the empty word there.
Yeah?
Because to get from the empty word to that, I know here I have to do
0, 1, 2, and so on, and here I would get the entry M.
So to get from the empty word to the word T1 to T, sorry, this is
again the N here.
To get from T1 to TN, I need exactly N operations, N insert
operations.
And to get from, now the other way around, to get from S1 to SM, to
get from S1 to the empty word, I have to delete one symbol.
Then I have to delete two symbols, and here I would have to delete M
symbols.
And now I can look at this location here.
What is the value that I have to insert there?
Now this is simple.
If S1 and T1 are the same, I don't have to do anything.
If they are different, I have to do something, I have to delete and
insert something.
So it depends on the values that we have here in those fields that
are, like if we are at some position later on, somewhere at SI, and
here some TJ, we are then at some position there, and we look at the
entries that we have around that, at these three positions there.
We would like to determine what we have to put into that field.
And we assume we have the neighboring positions already available.
That's what you saw at this location here also.
And then if you start from there, you can gradually fill in that
table.
Now what is the situation that we have?
We look at the entries in the neighboring fields, which are the fields
in the row above, row i-1, and columns j and j-1.
And we look into the same row, but in the neighboring column.
That's DI j-1.
And then we say, okay, if it is the minimum, the value that you have
to put in there, of what we see in the same column above, plus 1.
Because in the same column above is that field.
So we knew how many operations we needed to get from the word S1 to SI
-1, to that term T1 to TJ.
And now we have the term S1 to SI, and we want to get to T1 to TJ.
Then we have a longer word.
So we get from the longer word to that.
We might need to delete the symbol SI, and then do the same thing,
because then we are at the string S1 to SI-1.
And we need one more operation, maybe.
That was one possibility.
The other possibility is we look into the same row.
That means we know how we get from S1 to SI to T1 to TJ-1.
Now we have to add another symbol, TJ.
That means we have to insert something.
Or we look at the entry that we have here in the diagonal neighboring
element, DI-1J-1.
And now if SI and TJ are different, we know that up to T1 to TJ-1, we
know what the number of editing operations is, and now the SI is
different from TJ, then we have to replace that SI with TJ.
One operation.
If they are the same, we are done.
We have transformed S1 to SI-1 into T1 to TJ-1, and SI and TJ are the
same.
So we have these two situations, and either they are the same or they
are not the same, and then we look at the minimum number of those that
are listed here.
The minimum value.
Because that shows us what we have to do, at least, to get from S1 to
SI to T1 to TJ.
So this is the algorithm, more or less.
And in that way we can fill in all the entries here.
Now we do that for a specific word.
We have the table.
We want to transform Sunday into Saturday.
And we have just here the empty word initially, so that's the empty
word there.
And obviously we have the simple entries initially, and then we look
at, okay, here, for example, we have the same character, S and S here.
Here, again, the four different possibilities that we have.
So here we would insert a zero.
What would we put in there?
If we have, like, to transform S into SA, well, obviously here you
have to do just one, write in one more.
This is simple.
You get here one, two, three, and so on.
And here you have seven.
What about this here?
To get from SU to S, you look at those three things here.
Again, you have to add one, because here it's one more than that one
here.
And in this way, you fill in the table completely.
Now, that's not a complete table.
I didn't want to fill in every field here manually, directly, so this
is just a completely filled-in table.
Here you have all the entries that you get from that algorithm.
And so at the end, we'd see here, that's actually the number of
operations that we need to get from the word Sunday to the word
Saturday.
So this is the editing distance.
And here we see actually the operations that we have to perform to get
from Sunday to Saturday.
We only have to do something there, there, and there.
That's it.
And so this is a way of actually finding out the editing distance, and
you see also what you have to do, at what locations you have to
insert, delete, or replace something.
And the complexity of that is obvious.
It is you have to fill in the complete table, and so you have to have
an effort of n times m, if you have the two terms having length n and
m.
Or you could say if it's the same length words, you have n squared as
the complexity.
We can put this into a pseudocode if we like to, and then we have here
our two characters, or our two words, s and t.
And we have the distance matrix, which initially can be easily filled
in the first column and the first row.
That's what we did there in the table initially.
And after that, we just have to distinguish the two cases that s i
equals t j or not.
For that, we have a cost variable, which either is 0 or 1, because
remember that if we consider the diagonally neighboring element, we
had to distinguish the two cases, whether the terms differ or the
characters differ or not.
So we just add the cost variable here, and this is either 0 or 1,
depending on whether they match or not.
And then we just compute the minimum of those distances, and we are
done.
So a very simple algorithm.
Runtime, order of n squared, or I should say order of n times m.
That's how we determine the editing distance of two words.
Now we look into the question how we can actually follow what I said.
This was Assumption 1.
We actually want to search for the occurrence of a word inside a
document.
Pattern matching.
So we have our word that we are looking for.
For example, UNI.
If you look for that, then, as I said, it corresponds in some way to a
finite automaton.
You look for all the words matching that query.
That means you look for all the words accepted by that finite
automaton where this is the starting state, and then you could
actually implement that easily in software, and you have your
algorithm.
For every document that you have is put on the input tape of some
finite automaton, and you look whether in the end you are in the final
state.
Very simple.
Or you could write that as some pseudocode, and it means that you
just...
What you do here, you have your document.
In this case, the document has N characters.
And you just look for whether your pattern occurs there.
That means you have a pointer for...
This is a pointer for the document.
J is the pointer for the pattern.
And you just get or go to the first position and look whether the
document matches the pattern W at that position.
So you look, scan through here.
If you have a mismatch, then this very simple approach just says,
okay, I just increase my value of I.
That means I go to the next position in the document.
And so this was just gradually shift my pattern through all the
positions and you would check whether from that position your pattern
matches.
And if you actually...
Here in that while loop, you have...
You always look whether J is less or equal to M.
That means if you are still inside the pattern, inside the word W, if
you got all the way through that word W, it means that you had a
match.
And then you report the match at the position I plus one.
Because that was the starting position, the current starting position.
So if you are somewhere here, that's the starting position.
That was starting with I.
This is I plus one.
And that's the first position of your word.
And you notice that there is a match.
So report the starting position of that match.
Very simple algorithm.
Takes a little bit long because it takes time N times M.
The question is, can we do better than that?
And you can do better.
And it's interesting to look at how you can actually do that.
There are standard algorithms for that.
I guess that a few persons might have seen those algorithms in the
informatics.
Like if you are in information engineering, Informatik
Zoneswirtschaft, you might have heard that in Informatik Zwei in the
algorithms course there for pattern matching algorithms.
One of the standard algorithms is by Knuth, Morris and Pratt.
It's just looking a little bit more intelligently at what we do there.
Essentially it is the algorithm I just mentioned to you on the
previous slide.
But we exploit the knowledge of the prefix of W.
So we know this here matched.
If we are in such a situation, we have a mismatch here.
These here are unequal.
And we know that this prefix was the same up there in the document.
And we should exploit that.
Because we know if we shift this one position to the right, we know
something about the pattern.
And we should exploit our knowledge of the pattern.
We know the pattern and then go into the document.
So we can pre-process the pattern intelligently.
And notice that, for example, this was the prefix that actually
matched.
Now we have to shift our pattern to the right.
And we should shift it as far to the right as reasonable.
Not just by one position.
But we should shift it to a position, the first position that is
reasonable, where the part to the left of the current position that we
now look at is identical with what we had in the pattern there.
So we are at position WJ in the pattern.
We would like to know which position of the pattern has to be compared
to DI next.
We look for some position here.
And so we just shift it to the right.
And so here we have this, that again.
And certainly we should shift it that far such that the symbol that we
have there is different from this WJ here.
So if we now just take here WI again.
So we look for the earliest position or the best position where we
have or we look for the largest suffix that we can find.
The suffix of that prefix, this suffix here of that prefix, which
occurs again as a prefix.
Such that the symbol to the right of that is different.
We will see examples of that, how that actually operates or how that
works.
Formally, it means we look for the maximum position that is less than
I.
So the maximum position here to the left of J.
Such that WI is not equal to WJ because it doesn't make sense to
compare the symbol WJ again to DI.
Because we know that or to the symbol in D at the moment.
So we look for a different symbol such that all the symbols to the
left of WI actually, which is just this prefix here, that prefix, is
the suffix of the word to the left of WJ.
So that's what's stated here.
These two sequences here should match.
This is just expressed in this description here, this formal
specification.
That's the way we define the next position that we have to compare in
the pattern with the current symbol in the document.
Should be different and we should choose the maximum position that is
the closest to WJ such that we can actually have a matching part again
in our document.
And that means if we now perform our pattern matching, we start at
some position and then we are at some position in our document DI and
afterwards we move our pattern and compare again our symbol at that
position to the next position of our pattern.
And then maybe we have to shift the pattern again if it mismatches.
And then if it matches, we just go to the next position in our
document.
So the pointer in our document is only moving to the right.
It will never go back to the left.
We check for the possibilities that a certain symbol in our document
matches parts or matches a position in our pattern.
And we compare it to reasonable locations in the pattern and shift the
pattern to the right whenever we have a mismatch.
And certainly if we shift the pattern completely to the right of that,
then we go one position further.
And if we have matches, certainly we also go to the right.
So this is the algorithm.
And you see immediately, since we only increase our pointer I
linearly, never go back, this is something which looks like linear in
the length of the document.
We have to shift our pattern W to the right a few times.
But when we increase our pointer J here inside the document, we always
increase also our pointer in the document.
The pattern and the document, we increase them simultaneously.
And so whenever we increase J, we also increase I.
And so in total, it is a linear operation.
Like these few shifts in here don't increase the number of operations
significantly, we have a linear number of comparisons that we actually
make.
So we get linear time, which we will see in a moment.
We have just one definition here.
We define that the maximum of the empty set is zero.
That means if there is no such I, no such to the left of J, such that
there is a different symbol to the right of a matching part there,
then we say the position is zero.
Now if the next position is zero, it means that we have to shift our
pattern completely to the right.
Zero is the position before the first symbol of our pattern.
And next of one is always zero.
That means if we have a mismatch at position one in our pattern, we
have to move it one position to the right.
This is simple.
Or this actually is a consequence of that definition up there.
Okay, now this is the algorithm that we use.
So we start with pointers I and J.
We have a pointer here, there is a pointer I, there we have the
pointer J.
We go through the document and the pattern.
So we repeat something.
So this is just simple pseudocode.
If we start, like if J is zero, initially it's not zero.
We are at the first symbol.
Or D I is equal to W J, we increase both.
If J is zero, it means that we have shifted our pattern one position
to the right.
And so we have to increase the pointer I and certainly also the
pointer J.
And then we increase both pointers.
Certainly also if the two symbols match.
Now if we are beyond the limit of our pattern, we are done.
We report a match.
Otherwise, if we are inside, then...
Let me just see.
If they are the same,
J is next.
And J...
Something is...
If J is larger than M, we report a match and we are done.
Then we are done.
We jump out of that.
If it is not greater than, if it is less than that...
No, this is just this statement.
So there we stop.
And then I have J equal next J at this point.
Sorry, somehow I'm puzzled here.
Because we have D I is equal to W J.
And somehow I'm puzzled.
Because if it's the same, I would not say J has...
I would not shift our pattern because it was equal.
Something is... I'm completely puzzled.
I don't know what happened here.
Let me just...
I have the impression that a line of code has been missing here.
I'm completely puzzled.
I'm sorry.
I don't see why we have actually J equal next J at that line.
Because we are still inside that.
We have looked whether that is the same.
There must be...
An else must be missing here.
Because we have here.
That makes sense.
Now I see.
I was just puzzled.
What is the reason for doing that?
We report the match I equal M, I minus M.
We are inside.
This is the if statement.
And the end here corresponds to that if statement.
Sorry, I was a little bit puzzled here.
Doesn't matter.
We report the match.
And now we have reported a match.
And shift the pattern to the right to look for the next match.
And this makes sense.
Because we are one position to the right of our pattern.
We are now, for example, in a situation where we have already looked
through our pattern.
And then we know we can shift our pattern to the right.
But only as far as is reasonable.
Again, we have to shift it just as far to the right as makes sense
with respect to the structure of the pattern.
That's why we have J equal next J here.
Sorry, I was a little bit puzzled there, but it is completely correct.
This end here corresponds to that if statement.
Then we have the else corresponding to that test.
That means we have J is not equal to 0 and DI is not equal to WJ.
So we are inside our pattern and we have a mismatch and then we shift
to the right.
This is the second part.
Completely correct.
So either we are completely through and we shift to the next position
just to look for the next match.
We have reported one.
We look for the next match.
This is this J equal next J setting the next position in the pattern
that we should look at that you compare to the current position in our
document.
And if we have a mismatch, we have to shift to the right.
And we do that until we actually get completely through our document.
Then we are done.
So this is the algorithm for Knuth-Morris-Pratt search.
Certainly that I needed more time here to actually analyze it, but
everything is correct.
So pseudocode is not always completely easy to follow.
You have to look at the syntax in this end here.
So this is one statement and this was the other if statement there.
And if you look at what is happening here, the I is incremented
exactly n times.
This is where I is incremented.
It's never decremented.
J is always incremented together with I.
And it means that J cannot be decremented more than I is incremented.
And it means that we have maximally O over N operations.
The pattern length is less than the document length.
And we decrement our J a few times, but whenever we increment that, I
is also incremented.
And so the number of increment and decrement operations in total is
linear in the number of positions in N.
Okay.
And then we have to...
So this definitely is a significant reduction of the runtime.
We have linear time for search, whereas before we had quadratic time
for the search or N times M for the search.
And then I should stop for today.
We meet again next week and then look at examples and also another
approach, which will be the Boyer-Moore algorithm.
Okay.
Thank you very much for your attention.
That's it for today.