I built a word search engine in Python.  It isn't yet to the point of
being really usable, although I have gotten some interesting results
searching my local documents.

I thought reiserfs would be a reasonable way to keep my term indices
on disk.  It ends up taking about two-thirds of its wall-clock time in
userland, so reiserfs isn't costing *that* much, but it seems to be
actually writing data to reiserfs at only about 50-150 kilobytes per
second, which is disappointing, because my disk seems to be capable of
sequential writes at about 10 000 kilobytes per second.  However, this
may be my fault; I'm using the reiserfs in the standard 2.4.13 kernel,
and I've heard that maybe I should use some other kernel patches (or a
newer kernel) to make it faster, and I have CONFIG_REISERFS_CHECK set
to 'y', which is documented to slow reiserfs down significantly.

It also uses more space than I would like, essentially due to the file

Some notes on indexing document types other than plain text:

    A trial on 10 random PostScript documents produced the following
    rough results using ps2ascii from gs 5.10:
    - ps2ascii can spew out about 2000 words per second on my PII-366
    - words were about 6 chars long
    - ps2ascii fails on 20% of input documents for unknown reasons
    - ascii files were typically 20% of the size of the PostScript originals
    - according to the above, ps2ascii could convert PostScript to text at 
      about 60 kb of PostScript per second

    ps2ascii's output should generally be good enough extracting keywords
    for searches, but could be improved for that purpose, and it will be
    ugly for displaying excerpts.  However, ps2ascii tries to decolumnize
    columns.  Its major problems are guessing wrong about fonts (inserting
    Greek letters or ligatures for bullets or mathematical symbols),
    joining words it shouldn't, and splitting words it shouldn't.

    A similar test with the pdftotext program from xpdf 1.00 produced the
    following results:
    - pdftotext can spew out about 10 000 words per second
    - words were about 6 chars long
    - pdftotext failed on one input document that was encrypted (an application
      for a Danish entry visa)
    - sizes of output files varied widely; about the same size as input was
      common, as was half the size of input, a tenth of the size of input,
      and 10x the size of input

    pdftotext didn't handle multicolumn input in a fashion desirable for
    text searching, and otherwise suffered the same problems as ps2ascii,
    but not as severely.

    pdftops (from xpdf) worked much better than pdf2ps (from gs).

    On extracting HTML stuff: lynx -dump -nolinks does a reasonably good
    job of extracting contents, but it should be easy to improve on.  It
    can spew out somewhere between 10 000 and 100 000 words per second and
    is quite reliable.

Here's the program that builds or updates indices; after it is the
program to search them:

import sys, socket, time, os, errno, re, random, profile, posix
usage = "index indexdir filename [filename ...]"

# Builds a full-text index using the filesystem.
# Not surprisingly, this will be slow and space-hungry unless your
# filesystem rocks.  I recommend running it on ReiserFS.
# Initially this indexes at about 28-36 kilobytes per second on my
# PII-366, about 2/3 of which is user time.
# http://www.searchtools.com/tools/lucene.html describes Lucene as
# having "very fast indexing, over 200 MB per hour", which works out
# to 55K per second, so I guess that's not too shabby.  It takes about
# 20% longer to complete a small job on ext2 than on reiserfs (due to
# taking nearly 3x as much system time), and I expect that the size of
# the difference should increase as the job size increases.  (It also
# used 20 times as much disk space.)
# Profiling reveals that 17.7 seconds of a 52.0-second run are in
# 137980 calls to text_word_iterator.next, while another 4.2 seconds
# are in 137801 calls to indexer.stem and another 5.6 seconds are in
# 137801 calls to indexer.wanted.  So it should be possible to essentially
# double the speed of this indexer with a little C code, making it as fast
# as Lucene on plain text.
# Space is another matter.  On reiserfs, it has rather poor space
# usage; in one instance, 213 mail messages totaling 909kB used
# 1572kiB for their index.  In another, 12 documents totaling 8.8MB
# used 8388kiB for their index.  This could be prohibitive overhead,
# although as mentioned above, it's 20 times better than ext2fs.
# An indexdir contains two subdirectories: "docs" and "words".
# Files in "docs" are documents that have been indexed.
# This dir normally contains symlinks to the actual files.
# Some of them may be dangling.
# "words" contains one file per word; it lists the names of files in "docs"
# that contain that word, along with some other data (presently the number
# of occurrences).  
# "words" might contain index entries that point at no-longer-existing files
# (or files the creation of which failed) in "docs", and some things in "docs"
# might not be fully indexed.
# We need a way to update the index for an already-existing file!

# XXX backwards-compatibility hack
try: StopIteration
except: StopIteration = "StopIteration"

jumper = random.Random()
serial = 0
def linkfileinto(dir, file):
    while 1:
        global serial
        serial = serial + 1
        filename = str(serial)
            # XXX assumes symlink() is atomic
            os.symlink(file, os.path.join(dir, filename))
            return filename
        except OSError, err:
            err_errno, msg = err
            if err_errno == errno.EEXIST:
                serial = serial + 10**jumper.randrange(3)

class text_word_iterator:
    def __init__(self, filename):
        self.file = open(filename)
    def readline(self):
        self.line = self.file.readline()
        if self.line == '': self.words = None
        else: self.words = filter(None, re.split(r'\W+', self.line))
    def next(self):
        while 1:
            if self.words is None: raise StopIteration
            elif self.words: return self.words.pop()

class texttype:
    def getwords(self, filename):
        "Return a word iterator."
        return text_word_iterator(filename)

def makedirs(dirname):
    if not os.path.exists(dirname): os.makedirs(dirname)

class indexer:
    def docsdir(self): return os.path.join(self.indexdir, "docs")
    def wordsdir(self): return os.path.join(self.indexdir, "words")
    def __init__(self, indexdir):
        self.indexdir = indexdir
        self.words = {}

    texttypeinstance = texttype()
    def guesstype(self, origname, linkedname):
        for compressed_extension in ['.zip', '.gz', '.pdf', '.PDF']:
            if origname[-len(compressed_extension):] == compressed_extension:
                return None
        return self.texttypeinstance
    def stem(self, word): return word.lower()
    def wanted(self, word):
        # length limit of 60 should cut down on uuencode and base64 "words"
        return (len(word) > 1 and len(word) < 61 and
                word not in ['the', 'and'])

    def indexfile(self, origname, linkedname):
        """Add a file to the full-text index.

        indexdir --- the top-level directory the index lives in
        origname --- the file's original name (used for guessing type)
        linkedname --- the name the file is known as in this system

        This routine figures out what kind of file the file is,
        extracts words from it, stems them, and remembers them for
        addition to the index.

        filetype = self.guesstype(origname, linkedname)
        if filetype is None: return  # XXX should report as failure!
        filewords = filetype.getwords(os.path.join(self.docsdir(),
        words = {}
            while 1:
                word = self.stem(filewords.next())
                if self.wanted(word):
                    if not words.has_key(word): words[word] = 0
                    words[word] = words[word] + 1
        except StopIteration:
        for word in words.keys():
            if not self.words.has_key(word): self.words[word] = []
            self.words[word].append((linkedname, words[word]))

    def index(self, filename):
        filename = os.path.abspath(filename)
        docsdir = self.docsdir()
        linkedname = linkfileinto(docsdir, filename)
        self.indexfile(filename, linkedname)

    def commit(self):
        wordsdir = self.wordsdir()
        for word in self.words.keys():
            wordfile = open(os.path.join(wordsdir, word), "a")
            for file, data in self.words[word]:
                # FIXME: really big concurrent indexing jobs could
                # exceed PIPE_MAX bytes and result in interleaved appends
                # due to buffering
                wordfile.write("\n%s: %s" % (file, data))

def main(argv):
    if len(argv) < 2:
        sys.stderr.write(usage + "\n")
        return 1
    indexdir = argv[1]
    files = argv[2:]
    myindexer = indexer(indexdir)
        for file in files:
            print "indexing", file,
            print "done."
        print "committing",
        print "done."
    return 0

#if __name__ == "__main__": profile.run('sys.exit(main(sys.argv))')
if __name__ == "__main__": sys.exit(main(sys.argv))
# bug log:
# - forgot about argv[0], tried to use argv[0] for the index dir
# - assumed os.makedirs() would succeed if dir already existed
# - forgot to declare hostname in uniqname global --- "local variable
#   referenced before assignment"
# - had local variable "time" shadowing global "time" module --- same
#   problem
# - used "symlink" instead of "os.symlink"
# - wrote foo(os.path.join(x), y) instead of foo(os.path.join(x, y))
# - didn't think about the case of an empty word (now the text word iterator
#   avoids them)
# - didn't think about lowercasing words
# - when I moved the rename code from function to function, I didn't rename
#   'linkedname' to 'file' as I should have
# - forgot to makedirs(todir)
# - didn't provide for "stop words"
# and then it worked.
# - forgot to declare 'serial' global
# - tried to catch IOError from symlink(), but it's OSError
# - forgot to put "return filename" inside loop
# - tried to use symlink()'s atomicity to provide concurrency control for
#   concurrent indexing jobs, but forgot I was symlinking into a different
#   directory than the finished files were in.  Gave up on not making
#   docs visible in "docs" until indexing them was finished.
# - the symlink logic was stupidly wrong --- when the symlink already
#   existed, symlink() would fail, so it would pick a new number --- and
#   then return the number it had tried in the first place instead of
#   trying again.

And here's the 'search' program:

import sys, socket, time, os, errno, re, string
usage = "search indexdir searchterm [searchterm...]"

# Search a full-text index created by the "index" program.

# for scoring, see lucene faq sec. 3 q. 31

def set(list):
    rv = {}
    for item in list: rv[item] = 1
    return rv

def intersect(somelists):
    rvdict = set(somelists[0])
    for eachlist in somelists[1:]:
        listdict = set(eachlist)
        for item in rvdict.keys():
            if not listdict.has_key(item): del rvdict[item]
    return rvdict.keys()

class indexer:
    def docsdir(self): return os.path.join(self.indexdir, "docs")
    def docstmpdir(self): return os.path.join(self.indexdir, "docstmp")
    def wordsdir(self): return os.path.join(self.indexdir, "words")
    def __init__(self, indexdir):
        self.indexdir = indexdir
    def docscontaining(self, term):
        try: index = open(os.path.join(self.wordsdir(), term))
        except IOError, err:
            err_errno, msg = err
            if err_errno == errno.ENOENT: return []
            else: raise
            rv = []
            while 1:
                line = index.readline()
                if line == '': return rv
                colonpos = string.find(line, ':')
                if colonpos != -1:
    def realname(self, filename):
        return os.readlink(os.path.join(self.docsdir(), filename))

def main(argv):
    if len(argv) < 2:
        sys.stderr.write(usage + "\n")
        return 1
    if not os.path.exists(argv[1]):
        sys.stderr.write("No such indexdir: " + argv[1] + "\n")
        return 2
    myindex = indexer(argv[1])
    doclists = map(myindex.docscontaining, argv[2:])
    doclist = intersect(doclists)
    for doc in doclist:
        print myindex.realname(doc)
    return 0

if __name__ == "__main__": sys.exit(main(sys.argv))
# bug log:
# - called "indexer" "index" --- oops.
# - did except OSError, but open was raising IOError
# - said readlink instead of os.readlink
# - tried to do [:colonpos-1] instead of [:colonpos}, duh
# and then it worked.
# - didn't error on misspelled indexdir name

/* By Kragen Sitaker, http://pobox.com/~kragen/puzzle2.html */
char a[99]="  KJ",d[999][16];main(){int s=socket(2,1,0),n=0,z,l,i;*(short*)a=2;

Reply via email to