Die Suche

Autor: Ervin Hizliok

In diesem Abschnitt wird die Suche im Index der Suchmaschine beschrieben, nachdem eine Benutzeranfrage (also ein Filter- und ein Rankingausdruck) eingelesen und geparst wurde.

Die Programmkomponente enthält drei Klassen:

Search
MyResult
ResultObject

wobei die Klasse Search (bzw. deren Methode getMaches) die einzige "Schnittstelle nach außen" bildet.
Die Methode getMatches in der Klasse Search erhält dabei als Parameter die geparste Anfrage (vom Typ: PParsedQuery) und gibt als Suchergebnis auf diese Anfrage eine Liste von Dokumenten mit ihren Relevanz-Werten zurück. Der ResultObject-Array als Rückgabeparameter repräsentiert diese Liste. Dabei ist ein ResultObject ein Tupel, bestehend aus einem Dokument (CIndexedPage Object) und dessen Relvanz-Wert. Die ResultObjects sind im Rückgabearray nach ihren Relevaz-Werten geordnet.
 

Desgin

Der Eingabeparameter (PParsedQuery), der die geparste Anfrage repräsentiert, besteht aus zwei Komponenten: einem Filter- und einem Rankingausdruck (man erhält diese durch Aufruf der PParsedQuery-Methoden getPFilter und getPRanking). Diese werden nacheinander abgearbeitet:
Erst werden anhand des Filterausdrucks die für die Anfrage relevanten Dokumente aus dem Index "gefiltert". Dannch sollte anhand des Rankingausdurcks jedes Dokument einen Relevanzwert zugewiesen bekommen und anhand dieser Wertes die Dokumente geordnet (oder "gerankt") werden. Leider wird momentan bei der Berechnung der Relevanz eines Dokuments der Rankingsausdruck nicht mit einbezogen (mehr dazu: weiter unten).

Filtering

Im folgenden wird die Auswertung des Filterausdrucks beschrieben.

Der geparste Filterausdruck ist als einfach verkettete Liste von PFilter-Objekten repräsentiert, so daß jedes PFilter-Objekt als Attribut eine Referenz auf seinen Nachfolger enthält.
Des weiteren enthält es als Attribut eine Liste von Termen und einen Existenzoperator.
Die Länge der Liste ist >1 genau dann, wenn es sich bei diesen Termen um eine Phrase handelt (dabei treten die Terme in der Liste in der entsprechende Reihnfolge auf).
D.h. wir haben bis jetzt insgesamt eine verkette Liste von PFilter-Objekten, wobei jede Komponente eine Liste von Termen und einen dazugehörigen Existenzoperator enthält.
(Für weitere Informationen zur Semantik des geparsten Filterausdrucks bitte in der entsprechenden Dokumentation nachschauen!).

Man könnte (jetzt in der Suche!) zu jeder Liste von Termen eine Menge von Dokumenten herausfiltern. (Wie? kommt noch ..)
Wie werden diese Mengen aber dannach assoziiert?
Das letzte Attribut in einer Komponente (also in ein PFilter-Objekt) ist ein boolscher Operator, der Art der Verknüpfung zum Nachfolger angibt.
Typischerweise sind hier als Verknüpfungsmöglichkeit das AND und das OR vorhanden.
D.h. also: Zu jeder Liste von Termen kann eine Menge von Dokumenten herausgefiltert werden, und diese Mengen dann zu einer einer Gesamtmenge verknüpft werden.
Man verknüpft je zwei dieser Mengen, indem man: bei einem OR zwischen zwei Termlisten die zugehörigen Mengen vereinigt; bei einem AND die Schnittmenge bildet; der Existenzoperator hat Vorrang vor AND/OR und entspricht (rein semantisch) der Komplementbildung. Des weiteren gilt, daß AND vor OR vorrang hat.

Im folgenden wird beschrieben, wie dieser Vorgang implementiert ist.
 

Auswertungstrategie

Anfrage in DNF

Da die Anfragesprache nur AND/OR und Existenzoperator(en)  und der geparste Filterausdruck keine Klammern enthält, ist es möglich, den Filter-Ausdruck als einen DNF-Ausdruck (d.h. einen Ausdruck in disjunktiver Normalform) aufzufassen.
Dabei werden die Termlisten als Literale gedeutet, die Existenzoperatoren als eventuelles  Negationszeichen vor diesen Literalen (ExistOp=false <=> NOT); die boolschen Operatoren behalten ihre Semantik.
Für ein bestimmtes Literal (ohne bzw. mit positivem), das ein Term oder eine Phrase oder NEARBY-Ausdruck sein kann, sei die Aussage zu einem Dokument genau dann wahr (TRUE), wenn das Dokument dieses Literal, also diesen Term/Phrase/NEARBY-Ausdruck enthält.
Sei z.B. "b" diese boolsche Funktion, so daß:

Sei d ein Dokument und  l  Literal(=Term oder Phrase oder NEARBY-Ausdruck), es gilt:

b(d, l) = TRUE, wenn l in d vorkommt
          = FALSE, sonst;

Dann erhält man einem Literal l die Ergebnismenge:
{ d | b(d, l); d ist Dokument aus dem Index }

Wie diese Mengen mit AND/OR zu einer Gesamtmenge verknüpft werden, ist bereits oben beschrieben. Die resultierende Menge ist das Ergebnis der Suche zum Filterausdruck
 

Auswertung der ganzen Anfrage

Die Auswertung der Anfrage geschieht auf mehreren Ebenen. Wie gesagt, wird dieser als ein Ausdruck in DNF aufgefaßt.

Auf der obersten Ebene wird die ganze Anfrage in Disjunktionsglieder unterteilt.
Die einzelnen Disjunktionsglieder sind im Filterausdruck(=ganze Anfrage) durch ORs miteinander verknüpft. Ein einzelnes Disjunktionsglied besteht aus Literalen, die einen zugehörigen Existenzoperator (bzw. evtl. ein Negationszeichen) haben und durch ANDs miteinander verknüpft sind.
Nachdem die Disjunktionsglieder nacheinander ausgewertet worden sind, und für jedes DNF-Glied (Disjunktionsglied) eine Menge von Dokumenten ermittelt wurde, werden die Ergebnismengen vereingigt (wie gesagt: "Vereinigung bei OR").

Auf der nächst-unteren Ebene wird ein Disjunktionsglied ausgewertet. Dazu wird erst jedes Literal erst einzeln ausgewertet. Man erhält dann für jedes Literal eine Menge von Dokumenten. Entsprechend des dem Literal vorgestellten Existenzoperators werden die Schnittmengen gebildet ("Schnittmengen bei AND"). D.h.: Ein Dokument ist genau dann in der Gesamtergebnismenge zu diesem DNF-Glied, falls es in jeder Ergebnismenge zu einem Literal mit positivem Existenzoperator vorkommt; und in keiner Menge zu einem Literal mit negativem Existenzoperator enthalten ist.
 
Die unterste Ebene ist die Auswertung eines Literals. Man erhält zu jedem Literal eine Menge von Dokumenten.

Hier alles nochmal detaillter

Unterteilen in Disjunktionsglieder

    Der Filterausdruck, repräsentiert als verkettete Liste von PFilter-Objekten, wird durch aufsplitten an den OR stellen in Teilketten (oder Teilausdrücke) zerlegt -> Mehtode filter. Diese Teilketten sind dann die einzelnen Disjunktionsglieder. Für jede dieser wird die Auswertungsroutine für Disjunktionsglieder aufgerufen->Methode makeFiltering.
    Man erhält nach dem Aufruf von makeFiltering für ein Disjunktionsglied als Ergebnis eine Menge von Dokumenten mit jeweils zugehörigen Attributen; repräsentiert als Array von MyResult-Objekten. Ein solches MyResult-Objekt korrespondiert einem Dokument in der Ergebnismenge und enthält eine Dokument ID, eine Liste der in diesem Dokument gematchten Terme (als WordLink-Array) und eine zu diesem Array korrespondierendes Array mit Ranking-Inforamtionen bzw. Postings (repr. als posting-Array).
(Für weiteres zu WordLinks und Postings -> Dokumentation des Index).

Diese Mengen werden vereinigt. Dabei gibt es eine Dublikatenentfernung und eine Aktualisierung der Ranking-Informationen.

Auswertung eines Disjunktionsglieds 

wie beschrieben: Auswertung der Literale -> Ergebnismengen; Gesamtergebnis für ein DNF-Glied ist die Schnittmenge dieser Ergebnismengen; dabei auf den dem Literal zugehörigen Existenzoperator achten.

Man erhält nach der Auswertung eines Literals eine Menge von Dokumenten repräsentiert als Array von MyResult-Objekten.
Diese Mengen für die verschiedene Literale werden unterteilt in Mengen mit positiven bzw. negativen Existenzoperator vor dem zugehörigen Literal. Ein MyResult-Object wird genau dann ins Ergebnis aufgenommen, wenn er in jeder Menge mit positivem Existenzoperator Literal enthalten ist, und keiner mit negativem Existenzoperator auftaucht. Die MyResult-Objekte werden anhand der Dokument ID miteinander verglichen.

Bsp.: Sei  "L1 AND L2 AND NOT L3"  ein DNF-Glied

Wir erhalten zu L1, L2, L3 die Dokument-Mengen D1, D2, D3. Die Ergebnismenge lautet:
{ d | d ist Dokument;  D1 enthält d;  D2 enthält d; in D3 taucht D nicht auf }
= ( D1 geschnitten D2 ) \ D3
 
 

Auswertung eines Literal

Die Literale werden unabhängig ihrer Existenzoperatoren ausgewertet. Für die Zugriffe auf den Index sind entsprechende Schnittstellen vorhanden.

  • einzelner Term: Postings werden direkt aus dem Index gelesen und die Ergebnismenge (=Arry von MyResult-Objekten) gebildet.
  • Wildcard: Die zu diesem Wildcardausdruck passenden WordIDs werden aus dem Index gelesen; da die WordIDs einzelne Terme sind, werden zu jeder (wie bei einzelnen Termen) die Ergebnismengen ermittelt. Schließlich werden die Ergebnissmegen vereinigt.
  • Phrasen, Nearby: Phrasen entsprechen NEARBY 1, wobei die Position (d.h. rechts oder links) unterschieden. wird. Ansonsten wird beim NEARBY als erstes der Term herausgesucht, der die kleinste Anzahl von Ergebnisdokumenten zurückliefert, d.h. die kürzeste Posting-Liste hat. Diese zu einem Term gehörende Zahl , die angibt, wie lang die zugehörige Postingliste ist,  wird als "use count" bezeichent. Sie kann direkt aus dem wordLink eines Terms extrahiert werden, ohne das ganze Postinglisten gelsen werden müssen (siehe: Dokumentation zum Index).  Zu dem ausgesuchten Term  werden die Ergebnisdokumente herausgelesen. Für jedes Dokument wird anhand seiner Inhaltsrepräsentation überprüft, ob auch zusätzlich die NEARBY-Klausel erfüllt wird, d. h.: ob auch die anderen Terme, rechts von links vom ausgesuchten Term, in dem Dokument an den entsprechenden Positionen auftauchen (dies natürlich für alle Positionen an denen der ausgesuchte Term auftritt). Wenn dies der Fall ist, wird das Dokument in die Ergebnismenge aufgenommen,  sonst verworfen.

  • Anmerkung: Da hier für jedes Dokument für ein hoher Aufwand gemacht wird, ist diese Stelle von der Laufzeit her am kritschsten. Daher ist es wichtig, den Term mit dem kleinsten "use count" zu ermitteln. Da wir dann die kleinste Kandidatenmenge von Dokumenten erhalten und untersuchen.
    Natürlich sind auch Kombinationen dieser drei innerhalb eines Literals möglich.
     

    Ranking

    Da wir,  für einen vom Benutzer gegebenen Rankingausdruck, kein Auswertungsmodell gefunden hattten, geschieht das Ranking folgendermaßen.

    Gegeben ist ein Array von MyResult-Objekten, wobei jedes MyResult-Objekt ein Dokument mit zugehörigen Informationen präsentiert:
    Man hat zu jedem Dokument eine Liste von darin auftauchten Termen der Suchanfrage (also die hier gematchten Terme) repräsentiert als wordLink-Array). Dazu hat man ein korrespondierendes Array  mit den Postings, wobei eines von denen, die Dokument ID, den Ranking-Wert des Termes innerhalb dieses Dokument und Meta-Informationen enthält.
    Interessant sind an dieser Stelle die Ranking Werte, diese werden alle aufaddiert und dann die Suche durch die Anzahl der gematchten Wörter geteilt. Man erhält, damit den durchschnittlichen Ranking- Wert eines gematchten Wortes auf dieses Dokument.
    Um einen normierten, prozentualen Wert (zwischen 0 und 1) zu erhalten, wird durch den maximal erreichbaren Ranking-Wert dividiert.
    Nun haben wir aber zu jedem Dokument durchschnittliche Rankingwerte. Um dem "Hit count" (Anzahl d. gematchten Terme) auch ein Gewicht zu geben, d.h. z.B.: um ein Dokument mit 3 Treffern von einem mit 5 Treffern hinsichtlich seiner Relevanz unterscheiden zu können, addieren wir zu jedem die Wert die Anzahl der Treffer (oder Matches). Für das vorige Bsp. erhielte das Dokument mit 3 Treffern einen Wert zwischen 3 und 4 (>=3 und <4) und das mit 5 einen zwischen 5 und 6.

    Diese Werte sind in diesem Ranking-Algorithmus die endgültige Relevanzen der Dokument.
    Anhand derer werden die Dokumenten sortiert als Anfrageergebnis zurückgegeben. (Dazwischen findet natürlich noch eine Konvertierung von MyResult nach ResultOject statt)
     
     
     >


    Last modified: Mon Feb 22 09:44:45 MET 1999