Writing an indexed search engine

After due nagging, I decided that as this is a field I know about (or
so I thought <g>) I really ought to try and put it into practice.

The existing scenario is a follows:

User enters a search phrase (single word or actual phrase) and this is
searched for by brute force within 1500 files using a simple system of
(roughly):

open file
read line
does line contain search phrase (case insensitive) ?
if so, output this article
if we've done 10 articles, finish otherwise
carry on with next line
next file

Surprisingly, this is actually quite fast on a Linux server, less than
2 seconds to return results for a found word or phrase.

However, far more efficient (in theory, and I'm not arguing) to
produce an index:

<WORD><delimiter><FILE NAME>

such as:

CAT#B1.HTM
DOG#B2.HTM

for every word contained within articles within the 1500 pages, except
that:

1) Stop words (a, the, an, and, of.... and the like) are omitted
2) Only one entry in the index is made for each word/file name
combination

Then, rather than using brute force to search through every one of
1500 files, one scans the index for the search word or first
(non-stop) word in the search phrase until either:

a) a match is found or
b) the index entry word is alphanumerically higher - eg we've past
where in the index the search word would be if it existed, so we can
abort.


When a match is found, retrieve the name of the file containing the
search word, and do a brute force search on that file as before. Then
continue down the index until we reach the end or find an
alphanumerically higher entry (eg we pass all the entries).

Works fine on the Windows test machine (that surprises you doesn't
it!) even in this rough form, it reduces the search time by about
5/8ths - eg tests take 5 seconds rather than eight to finish.

So why is it that it fails on the Unix machine? By fail, I mean the
program operates correctly, but is so slow that searches using the
index are far slower than using the old brute force method.

It's friday night, I'm off to get pissed.

Any sad gits with a passion for programming might like to play with
this while I'm gone...

Oh, and yes I have considered producing an array of filenames which
satisfy ALL non-stop words in the search phrase, and then just
searching them, thereby searching even less files.

Matt

Matt Probert wrote:

 > However, far more efficient (in theory, and I'm not arguing) to
 > produce an index:
 >
 > <WORD><delimiter><FILE NAME>

In my engine I've found this to cause a huge file.
I'm in the process of converting the <FILE NAME>
list into a list of integers that index into an array of all filenames.

 > such as:
 > CAT#B1.HTM
 > DOG#B2.HTM

Which would, in my system, now be:
CAT#5,25,38,99,505
DOG#88,509,1284

with the numbers being an index into an array of filenames
(which you would, of course, read from a file). Should reduce
the size of the index files a lot.

 > Works fine on the Windows test machine (that surprises you doesn't
 > it!) even in this rough form, it reduces the search time by about
 > 5/8ths - eg tests take 5 seconds rather than eight to finish.
 >
 > So why is it that it fails on the Unix machine? By fail, I mean the
 > program operates correctly, but is so slow that searches using the
 > index are far slower than using the old brute force method.

What language? Mine is in Perl, and runs like a bat out of hell
on a 'nix box. Could be the language you're using isn't implemented
as well?<!-- ~MESSAGE_AFTER~ -->