Now let's see how we could create a text index for a bunch of documents.
Such as the three documents we had earlier.
We go through each document one by one, reading each word in turn, when we read
the word the, we insert an element against the in the final structure that we want to
create. Similarly to read the word quick we enter
A.com as the id of this document against quick.
Similarly for brown, similarly for over and for other words in this document.
Moving on to the next document, we do the same thing.
Enter word with B.com this time instead of A.com because now we are processing the
second document. Singularly for the third document.
But this time since the is already present, in the index, we merely append
the entry c dot com after a dot com against the, rather than create a new
entry. Similarly for lazy.
Bird, and finally for worm we enter a new entry with just c dot com against it.
How would we write a program to do this? Now, we'll go a little bit slowly while
describing this program because I'm not assuming everybody is familiar with
programming Python or object-oriented programming, or even if you are I'm
assuming that you need a bit of refreshment.
So we'll create a class index which is going to be a data structure index that
we, we are gonna create which will have a function which will create, which given a
list of documents D. This function will essentially populate
our index in this manner. So what we'll do is we'll go through each
document in D. Now in Python what this means is that if D
is a list, for D in D will essentially iterate over each document in D.
One by one. And for each such document small d will go
through each word w in that document. Once again we are assuming the document
small, the document small d in this list of documents d is itself a list of words
this time. So for each of these words, we'll go
through the document small d. And you've to call another function, look
up, also on the same beta structure index that we are creating.
And look up and check if this word W is already in the index.
Moreover if the word W is in the index then we assume that the look up function
will return I, if you'll give us the position in the list.
Where W is actually present, so we can access W directly.
For example, if we're looking at the word "quick", then it will return I = zero,
one, two, three, four, five, six, so that we can directly access this particular
part of the index structure. If W is not in the index structure, then
we assume that this function look up returns a negative number.
If that is the case then we have to add W to the index, fresh just like we added
worm in the end. And in that case the, the function add
which does this will return the position where W was added, so for example here, it
would return the position eight. Once its, once we have the position eight,
we can append to this List against worm for example the ID of the document where
the word "W" was found which is "D" dot ID.
Not is that we don't append "D" directly because "D" itself is a list of words.
So we don't want to append the entire document here we want to append only the
name of the document of the ID of the web page or URL of the document Going back,
there's an [inaudible] part, of course. If we did find W in the first place, we
would simply append it. Append the ID at that position I, without
having to ap, add a fresh entry into the index.
So that's simple, so this program, if we, if we're able to write all this functions,
look-up, add, append. Then we can, essentially go through this
list of documents, where each document is a list of words and create this index
structure. Very simply.
We'll probably do some such assignment later on in the course.
But at that time we will do it on many machines using parallel computing, the way
it's actually done in Google and other large search engines.