Datenformat für Suchmaschinen-Index...

[jens]

Ich hab mir schon mal eine ganz einfach suche für meine Webseite geschrieben:
http://www.jensdiemer.de/cgi-bin/PyWebS ... bSearch.py

Allerdings ist die ziemlich billig programmiert, weil sie immer für jede Suchanfrage alle Dateien Live auf Dateiebene einliest, um die Ergebnisse zusammen zu stellen...

Nun möchte ich eine neue Variante schreiben, die einen Index benutzt. Ich frage mich nur, wie ich am besten diesen Index Aufbaue.

Bei meinen bisherigen Test's benutze ich anydbm und speichere im Dict jedes Wort, welches in den Index soll, als Key ab und im Value speichere ich die Zusatzinformationen (z.B. die HTML-Datei in dem das Wort vorkommt, Position usw.)
Diese Daten sind auch einfach nur ein Dict, welches ich mit pickle in einen String wandel und mit bz2 komprimiere... Das mache ich, weil wenn ich z.B. shelve benutzen würde, die Index-Datei super groß wird...

Jemand noch eine andere Idee???

[BlackJack]

Wirf mal einen Blick auf Lupy -- eine Python Implementierung von Lucene.

Wie gross werden denn die Zusatzinformationen bei Shelve? Kann es sein, dass Du zuviel speicherst?

[jens]

Also ich hatte eigentlich nur vor zu jedem Wort, das folgende zu speichern:

• Dateindex - In welcher Datei sind die folgenden Daten vorhanden:
  • Position des Wortes
    Fundtyp - int-Zahl (Typ ist Fliesstext, Überschrift oder Metatags)

Die Datenstruktur so:

Code: Alles auswählen

index = {
    wort-1 : {
        dateiindex-1 : [
            { "pos" : pos-1, "typ", fundtypID-1 }, ... , { "pos" : pos-n, "typ", fundtypID-n }
        ],
        ...,
        dateiindex-n : [...]
    },
    ...,
    wort-n : {...}
}

[ EDIT: Bulshit gelöscht ]

[BlackJack]

Die Position ist IMHO nicht so wichtig, wenn man erstmal weiss in welcher Datei der Begriff steht, dann kann man die verhältnismässig schnell ermitteln.

Ich habe heute mal nebenbei ein wenig rumprobiert. Mit `shelve` und den RFC-Texten die auf meiner Platte rumliegen (ca. 205 MiB in 3663 reinen Textdateien). Ich habe nicht die Grösse des Index sondern eher die Geschwindigkeit beim erstellen als Problem gehabt. Der Index enthält 280663 Worte und ist ca. 93 MiB gross. Dabei habe ich den Dateinamen nochmal in ein anderes `shelve` ausgelagert und im Index nur eine ID (`int`) für jede Datei gespeichert. Ausserdem wie oft das Wort im Text vorkommt um Suchergebnisse danach sortieren zu können. Das wäre vielleicht auch eine Idee für Deinen Indexer statt des Typs ein Gewicht zu speichern, also nicht nur eine 1 für jede Fundstelle zu addieren sondern höhere Werte wenn das Wort in einer Überschrift steht.

Suchen im `shelve` Index geht sehr schnell vonstatten aber das erstellen des Index hat Stunden gedauert. Ich weiss noch nicht ob das einlesen und analysieren der Texte solange gedauert hat, oder ob `shelve` so langsam ist. Naja, hier ist der Quelltext:

Code: Alles auswählen

#!/usr/bin/env python
import sys, shelve

_IDEM = ''.join(map(chr, xrange(256)))
_BAD_CHARS = ''.join(filter(lambda c: not (c.isalnum() or c.isspace()), _IDEM))


def clean_lines(lines, bad_characters):
    for line in lines:
        result = line.translate(_IDEM, bad_characters).strip()
        if result:
            yield result


def iter_words(lines):
    for line in lines:
        for word in line.split():
            yield word.lower()


class Index:
    def __init__(self, name):
        self.name = name
        self.document_ids = shelve.open(self.name + '_doc_id_index')
        self.index = shelve.open(self.name + '_words_index')
    
    def update(self, document_index):
        doc_id = str(len(self.document_ids) + 1)
        self.document_ids[doc_id] = document_index.name
        
        for word, count in document_index:
            if word in self.index:
                index_entry = self.index[word]
                index_entry[doc_id] = count
            else:
                index_entry = {doc_id: count}
            self.index[word] = index_entry

    def sync(self):
        self.document_ids.sync()
        self.index.sync()
    
    def close(self):
        self.document_ids.close()
        self.index.close()

    def search(self, words):
        if isinstance(words, basestring):
            words = [words]
        words = list(iter_words(clean_lines(words, _BAD_CHARS)))
        result = dict()
        for word in words:
            try:
                for doc_id, count in self.index[word].iteritems():
                    result[doc_id] = result.get(doc_id, 0) + count
            except KeyError:
                pass
        return [(count, self.document_ids[doc_id]) for doc_id, count
                in result.iteritems()]


class DocumentIndex:
    def __init__(self, name, words=tuple()):
        self.name = name
        self.words = dict()
        self.update(words)
    
    def __len__(self):
        return len(self.words)
    
    def __iter__(self):
        return self.words.iteritems()
    
    def update(self, words):
        for word in words:
            self.words[word] = self.words.get(word, 0) + 1


def update(filenames):
    filenames = sys.argv[1:]
    index = Index('rfc')
    
    for filename in filenames:
        print 'indexing %r' % filename
        
        input_file = open(filename, 'r')
        words = iter_words(clean_lines(input_file, _BAD_CHARS))
        document_index = DocumentIndex(filename, words)
        input_file.close()
        
        index.update(document_index)
    
    index.close()


def search(words):
    index = Index('rfc')
    result = index.search(words)
    result.sort()
    print ''.join(['%5d %s\n' % (count, filename)
                   for count, filename in result])
    index.close()


def info(dummy):
    # 280663 words in 3663 files.
    index = Index('rfc')
    print len(index.document_ids)
    index.close()


def main():
    command_func = {'-u': update, '-s': search, '-i': info }
    command_func[sys.argv[1]](sys.argv[2:])


if __name__ == '__main__':
    main()

Im Nachhinein ist mir aufgefallen, das die Zerlegung der Eingabedateien in Worte nicht so optimal ist. Es werden erst alle Zeichen gelöscht, die nicht (ASCII)Buchstaben oder Ziffern sind und dann wird die Zeichenkette in Wörter aufgeteilt. Leider enstehen dabei ab und zu "falsche", zusammengesetze Worte, z.B. bei Quelltext:

Code: Alles auswählen

In [122]: list(indexer.clean_lines(['def spam(arg):'], indexer._BAD_CHARS))
Out[122]: ['def spamarg']

In dem Beispiel sollten 'spam' und 'arg' eigentlich zwei eigenständige Worte sein, sie werden aber als ein Wort indexiert. Und `update()` sollte besser `add()` heissen.

Ansonsten könnte man sich natürlich überlegen, ob man die Daten nicht einfach im Dateisystem speichert, also eine Datei pro Wort oder eine Datenbank benutzt. SQLite bietet sich zum Beispiel an und hat auch eine Python-Anbindung.

[jens]

Die Position ist IMHO nicht so wichtig, wenn man erstmal weiss in welcher Datei der Begriff steht, dann kann man die verhältnismässig schnell ermitteln.
[...]
Ausserdem wie oft das Wort im Text vorkommt um Suchergebnisse danach sortieren zu können. Das wäre vielleicht auch eine Idee für Deinen Indexer statt des Typs ein Gewicht zu speichern, also nicht nur eine 1 für jede Fundstelle zu addieren sondern höhere Werte wenn das Wort in einer Überschrift steht.

Das hatte ich mir auch mal gedacht... Nur, die Suche dauert dann ziemlich lange wenn nach einem Wort gesucht wird, welches in sehr vielen Dateien vorkommt. Somit muß man sehr viele Dateien öffnen und wieder durchsuchen.

Die Position ist wichtig für das Bewerten von mehr als einem Suchwort. Also wenn man nach zwei sucht, hat die Datei mehr Punkte, bei dem die Wörter näher zusammen stehen. In welchem Verhältnis das zu den Typ-Punkten steht, weiß ich noch nicht. Die Verhältnisse der Gewichtung, wollte ich eh frei editierbar machen.

Wobei mir da jetzt einfällt, das der FundTyp (Fliesstext, Überschrift, Metatags usw.) schon zusammen Addiert werden kann. Allerdings noch nicht bewertet! Somit kann man die Bewertung hinterher verändern. Aber ich kann halt ehr festhalten wie oft das Wort im Fliesstext, in der Überschrift usw. pro Datei vorkommt, anstatt es für jeden Fund einzeln den Typ festhalten.

Ich habe nicht die Grösse des Index sondern eher die Geschwindigkeit beim erstellen als Problem gehabt.
[...]
Der Index enthält 280663 Worte und ist ca. 93 MiB gross.

Das ist auch noch ein Aspekt. Wobei ich da ehr einen Wert auf die Suchgeschwindigkeit, als auf die Index-Erstellung, lege!
Leider wird der Index auch recht groß, denn bei mir soll er ja auf die Webseite drauf, das hochladen dauert nicht nur lang, sondern nimmt halt auch Webspace Weg...

Ich habe mir nun überlegt, ob ich deswegen lieber die Informationen pro Wort in einem eigenen Format abspeichern soll, als pickel zu verwenden? Denn pickel produziert, meine ich, relativ große Daten, schon bei einfachen Strukturen. (Im übrigen nutzt shelve auch pickel.)
Daher ja auch die Idee mit dem gz2 komprimieren. Wobei ich da z.Z. Probleme mit hab. Eine Lösung wäre, den Index erstmal im Speicher zu beahlten, bis alle Dateien geparst sind, dann das Ganze ins eigene Format, Wort für Wort, pickeln und mit bz2 komprimieren und in eine Datei mit anydbm schreiben.
Nachteil ist natürlich, das der Index nur so groß werden kann wie der Hauptspeicher, aber der ist ja in den letzten Jahren stark gewachsen

Dabei habe ich den Dateinamen nochmal in ein anderes `shelve` ausgelagert und im Index nur eine ID (`int`) für jede Datei gespeichert.

Mit einer ID für jede Datei habe ich genauso vor.

Im Nachhinein ist mir aufgefallen, das die Zerlegung der Eingabedateien in Worte nicht so optimal ist. Es werden erst alle Zeichen gelöscht, die nicht (ASCII)Buchstaben oder Ziffern sind und dann wird die Zeichenkette in Wörter aufgeteilt.

Das selbe Problem hab ich auch... Ich zelege ja HTML-Dateien mit dem sgmllib.SGMLParser... Dabei bleiben Satzpunkte an den Wörtern kleben, oder auch ()-Klammern. Das muß ich noch irgendwie rausfiltern...

Ansonsten könnte man sich natürlich überlegen, ob man die Daten nicht einfach im Dateisystem speichert, also eine Datei pro Wort oder eine Datenbank benutzt. SQLite bietet sich zum Beispiel an und hat auch eine Python-Anbindung.

Das wäre eine Überlegung Wert... Aber ob das wirklich schneller ist?!?

[BlackJack]

Ansonsten könnte man sich natürlich überlegen, ob man die Daten nicht einfach im Dateisystem speichert, also eine Datei pro Wort oder eine Datenbank benutzt. SQLite bietet sich zum Beispiel an und hat auch eine Python-Anbindung.

Das wäre eine Überlegung Wert... Aber ob das wirklich schneller ist?!?

Beim Dateisystem kommt es auf das verwendete Dateisystem an. Ich denke ReiserFS kann man schon zutrauen das es schnell ist, da die Dateinamen in einem Suchbaum gespeichert werden und nicht einfach als lineare Liste. Und wenn der Dateiinhalt kurz ist, dann wird der sogar mit in dem Block mit dem Verzeichniseintrag untergebracht -- wenn man den Dateinamen gefunden hat, dann ist ohne weitere Plattenzugriffe auch der Inhalt schon im Speicher. Einem FAT Dateisystem würde ich 280000 Einzeldateien für die Worte aber nicht anvertrauen, da dauert das Suchen eines Dateinamens verhältnismässig lange, weil alle Einträge sequentiell durchgegangen werden müssen bis der richtige gefunden ist.

Wo wir gerade von Suchbäumen sprechen: mx.BeeBase wäre vielleicht auch einen Versuch wert.

Ob SQLite nun besonders schnell ist kann ich nicht sagen, ich weiss nur das es überaus handlich und unkompliziert ist. Kein Server, eine einzige Datei in der die Tabellen gespeichert werden und eine DB-API 2.0 kompatible Python-Anbindung. Unter KDE gibt's einen Mediaplayer (amaroK) der SQLite benutzt um die Metadaten zu MP3s, Oggs etc. zu verwalten und auf die Datenbank konnte ich von Python aus sehr einfach zugreifen.

[jens]

Also die Idee für jedes Wort eine Datei anzulegen hatte ich sowieso nicht! Was evtl. überlegenswet ist, für jeden Anfangsbuchstaben eine Datei zu machen...

Teile von mx.BeeBase scheinen wohl in C Ausgelagert zu sein, somit scheidet es schon mal aus, weil ich das ganze auf meinen Webspace ohne shell zugriff benutzen will...

[BlackJack]

Was mir noch eingafallen ist: Man sollte auf jeden Fall "Stopwörter" rausfiltern, also so Sachen wie `der`, `die`, `das` oder `the` im Englischen. Die Worte tauchen in fast jedem Dokument auf und verbrauchen nur (*viel*) Platz im Index.

[BlackJack]

Im Nachhinein ist mir aufgefallen, das die Zerlegung der Eingabedateien in Worte nicht so optimal ist. Es werden erst alle Zeichen gelöscht, die nicht (ASCII)Buchstaben oder Ziffern sind und dann wird die Zeichenkette in Wörter aufgeteilt. Leider enstehen dabei ab und zu "falsche", zusammengesetze Worte, z.B. bei Quelltext:

Code: Alles auswählen

In [122]: list(indexer.clean_lines(['def spam(arg):'], indexer._BAD_CHARS))
Out[122]: ['def spamarg']

In dem Beispiel sollten 'spam' und 'arg' eigentlich zwei eigenständige Worte sein, sie werden aber als ein Wort indexiert.

Das Problem habe ich jetzt mit folgender Funktion zum erzeugen einer Filterfunktion gelöst:

Code: Alles auswählen

def make_text_filter(replace_characters):
    """Creates a function that takes a text and replaces all characters in
    `replace_characters` with a space, deletes all characters from the text
    that are not alphanumeric or whitespace and finally strips leading and
    trailing whitespace.
    
    :returns: function(str) -> str
    """
    translate_chars = map(chr, xrange(256))
    for replace_character in replace_characters:
        translate_chars[ord(replace_character)] = ' '
    translate_chars = ''.join(translate_chars)
    delete_chars = ''.join(filter(lambda c: not (c.isalnum() or c.isspace()),
                                  translate_chars))
    return lambda text: text.translate(translate_chars, delete_chars).strip()


text_filter = make_text_filter('+-*/()[]{}.,;:<>|=')

Sieht im Einsatz so aus:

Code: Alles auswählen

In [22]: indexer.text_filter('def spam(args): print args.map[key]')
Out[22]: 'def spam args   print args map key'

Das Resultat kann man jetzt problemlos in die einzelnen Worte aufteilen.

[jens]

Ich habe da eine andere Lösung, denn ich will ja den Typ berücksichtigen. Schick mal eine HTML-Seite durch und schau dir es mit dump() an...

ContentParser.py

Code: Alles auswählen

__version__="0.0.1"

import sys, re, sgmllib


class MetaContentParser(sgmllib.SGMLParser):

    """
    Extrahiert den Text aus HTML-Seiten.
    Unterscheidet die folgende Daten:
        - title
        - meta-Tags-Informationen
        - Überschriften
        - nomaler Text
    """

    entitydefs = {
        "nbsp" : " ",
        "Auml" : "Ä",
        "auml" : "ä",
        "Ouml" : "Ö",
        "ouml" : "ö",
        "Uuml" : "Ü",
        "uuml" : "ü"
        }

    def __init__(self):
        # MetaTags die berücksichtigt werden sollen.
        self.metaTags = ["keywords","description","author"]

        sgmllib.SGMLParser.__init__(self, 0)

        self.data = {
            "title"     : " ",
            "meta"      : " ",
            "heads"     : " ",
            "content"   : " "
        }
        self.typ = "content"

    ###
    ### Default Funktionen
    ###

    def start_title( self, dummy ):
        self.typ = "title"

    def end_title( self ):
        self.typ = "content"

    def start_meta( self, metaData ):
        try:
            typ = metaData[0][1]
            content = metaData[1][1]
        except:
            return

        if not typ.lower() in self.metaTags:
            return

        content = " ".join( content.split(",") )
        self.data["meta"] += " " + content

    def handle_data( self, data ):
        self.data[self.typ] += data

    def unknown_starttag(self, tag, attrs):
        if tag[0] == "h":
            # Überschriften
            self.typ = "heads"
        else:
            self.typ = "content"

    def cleancontent( self ):
        "Leerzeichen verwerfen, nur Buchstaben zulassen"
        for typ in self.data:
            self.data[typ] = " ".join(
                    re.findall( r"[\wäöüßÄÖÜ]+",self.data[typ] )
                )

    ###
    ### Abfragen der Daten
    ###

    def get_data( self ):
        self.cleancontent()
        return self.data

    def dump( self ):
        for k,v in self.get_data().iteritems():
            print ">",k
            print v
            print "-"*80

WebTest.py

Code: Alles auswählen

import urllib2

from ContentParser import MetaContentParser


TestURL = "http://www.heise.de"

print "rufe [%s] ab..." % TestURL,
c = urllib2.urlopen(TestURL)
HTMLside = c.read()
c.close()
print "OK"


print "Parse Daten...",
MyParser = MetaContentParser()
MyParser.feed( HTMLside )
print "OK"

print "-"*80
MyParser.dump()

[jens]

So, jetzt habe ich einen Index von einer Webseite generieren lassen... Das geht recht schnell, aber es sind auch nicht so viele Seiten...

Der Index in "Roh-shelve-Format" ist 3,7MB groß!
Mit Kompression aber nur 776KB.

Index Komprimieren:

Code: Alles auswählen

class compress:
    def __init__( self, indexfile, compresslevel = 9 ):
        self.index = shelve.open( indexfile, "r" )
        self.compresslevel = compresslevel

    def compress( self, outfile ):
        outfile = anydbm.open( outfile, "n" )

        for word in self.index.keys():
            data = pickle.dumps( self.index[word] )
            outfile[word] = bz2.compress( data, self.compresslevel )


compress( "wordindex.bin" ).compress1( "wordindexcompressed.bin" )

Auf komprimierte Daten zugreifen:

Code: Alles auswählen

class compaccess:
    def __init__( self, compressedIndexFile ):
        self.index = anydbm.open( compressedIndexFile, "r" )

    def get( self, word ):
        compresseddata = self.index[word]
        data = bz2.decompress( compresseddata )
        return pickle.loads( data )


MyIndex = compaccess( "wordindexcompressed.bin" )
print MyIndex.get("python")