Now let's ask how fast the procedure that
we just described for index creation
actually is.
Lets assume there are n documents, m words
and on the average, w words per document.
For example, in the case of the web, n
will be a really large number, maybe in
the millions, billions or trillions.
M will be another large number, perhaps
not as large as n.
But quite large nevertheless.
And W may or may not be very large because
every document may have a few thousand or
a few hundred thousand words but certainly
not billions of words.
Let's see now what the answer is.
We have an index structure here, we have
our documents and we assume we have N
documents M total possible words and on
the average twenty words per document.
First thing we notice is that every word
in each document needs to be read at-least
once, so the complexity is at-least order
nw.
Additionally as each word is read, we need
to look up this sort of structure of words
to figure out whether or not it has been
already inserted before.
The cost of looking this kind of a
structure up is, log in, as we've seen
earlier.
For example, if a balanced binary tree is
used to store these words.
Further, we must insert the URL of the
document against the word if we happen to
find it already in the index.
Else, we must insert an entry for that
word if we don't find it.
And then insert the document against it.
Now we claim that each of these is just a
constant cost per word.
Obviously the second part which is
inserting a blank entry for a word like
worm with...
With just one fresh document is clearly a
constant cost.
Once we know where to insert the word,
worm.
But suppose the word already exist and
there are thousands of document already
against it, then it is not that clear that
it is constant cost to insert.
The fresh ID in a long list of IDs.
So there's an important assumption.
That this is going be a constant cost.
And the reason for that assumption we'll
come to in a later lecture.
For the moment we'll go ahead with that
assumption.
If either of you missed it, in the
homework, and got confused that's okay
because you were thinking pretty well.
But for the moment we're gonna make this
assumption.
And therefore the complexity of our
procedure is order N W log M.
Using a balance bynatry destroy the words
and assuming that entering a fresh
document in an existing list against some
word is a constant cost.