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.
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.
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
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
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.
Natürlich sind auch Kombinationen dieser drei innerhalb eines Literals möglich.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)
>