klaus_b@.NET

Im vorherigen Artikel der Reihe habe ich die bisher erstellte Suche als linear und naiv so stehen gelassen. In diesem Artikel will ich nun ein Konzept zeigen, welches einer echten Volltextsuche schon sehr nahe kommt.
Dazu werden zunächst einmal zwei verschiedene Container benötigt:

1. Ein Index welcher die Seiten des Web mit all ihren Informationen enthält.
2. Ein Volltextkatalog der mit allen im Web vorkommenden Wörtern gefüllt ist. Dabei wird jedes Wort mit einer Liste von URLs verknüpft, in denen das entsprechende Wort vorkommt.

Gesucht wird jetzt nicht mehr im Index des Web, sondern im Volltextkatalog. Doch dazu gleich mehr.

Um nicht die verschiedensten Schreibweißen eines Wortes indizieren zu müssen, wird jedes Wort mit Hilfe der Kölner Phonetik kodiert und in den Volltextkatalog geschrieben. So wird gewährleistet, dass auch jede phonetische Ähnlichkeit in nur einem Datensatz gespeichert wird. Wie der Algorithmus der Kölner Phonetik in .NET verwendet werden kann, habe ich in diesem Artikel schon einmal erläutert.
Es macht allerdings keinen Sinn, jedes mögliche Wort zu kodieren. Also muss ein Kriterium erstellt werden welches festlegt, was ein Wort ist und was nicht. Nach diesem Kriterium muss einmal bei der Erstellung der Kataloge und zum anderen bei der Analyse der Zeichenfolgen aus der Suchmaske unterschieden werden. Zur Unterscheidung eines “echten” Wort von Pseudowörtern wie etwa einer Formel oder einer anderen Abkürzung, habe ich mir folgende Kriterien überlegt:

• Ein echtes Wort darf nur Buchstaben enthalten, keine Ziffern und Sonderzeichen.
• Es muss mindestens vier Buchstaben lang sein.

Anhand dieses Kriteriums werden zwei Wortlisten erstellt: eine für die “echten” Wörter und eine für alle vorkommenden Abkürzungen, Formeln udgl. Anschließend werden die beiden Listen entsprechen ihres Inhalts entweder kodiert oder als Klartext im Volltextkatalog gespeichert.

Da in einem etwas umfangreicheren Web schnell einige Tausend verschiedene Wörter vorkommen können, muss der Zugriff auf solch einen Volltextkatalog dementsprechend schnell sein. Da bekanntlich der schnellste Zugriff bei der Abfrage eines einzelnen Element ein O(1)-Vorgang ist, muss der Katalog auch so gestaltet werden, dass die abfragende Methode ein Resultat in einem O(1)-Vorgang liefern kann. Um diese Vorgabe umzusetzen, habe ich mich für ein Dictionary<TKey, TValue> als Kernelement für den Katalog entschieden. Da gewährleistet werden kann, dass jeder Schlüssel, in diesem Fall ein Wort, nur einmal im Dictionary vorkommt, kann die Vorgabe eines O(1)-Vorgang bei der Abfrage als erfüllt angesehen werden.
Wenn jetzt zum Beispiel nach der Zeichenfolge C# im Katalog gesucht wird, ist diese nur einmal enthalten und es wird sofort eine Liste der URLs zurückgegeben in denen die Zeichenfolge C# vorkommt.

Bis jetzt liegt bei der Suche nach der Zeichenfolge C# nur eine Liste von URLs vor, ohne jegliche Information der Seiten welche sich hinter den URLs befinden. Dazu wird nun der Seitenindex des Web benötigt.
Hier verhält es sich etwas anders mit der internen Architektur. Da der Seitenindex nicht nur für die Suche verwendet wird, liegen die Daten intern in einer List<T> welche die Informationen einer jeden Seite in einem Objekt vom Typ SiteEntry speichert. Die Struktur SiteEntry habe ich bereits in früheren Artikeln, z.B.: hier, erläutert.
Da die Aufzählung List<T> keine Zugriffe unterstützt die einem O(1)-Vorgang nahe kommen, habe ich mir hier mit einem kleinem Kniff beholfen. Die Klasse SiteIndex bietet unter anderem einen Indexer, der eine direkten Zugriff auf das jeweilige Element am angegebenen Index zulässt. Parallel zur List<T>, welche die Seiteninformationen speichert, wird ein Dictionary geführt, welches als Schlüssel eine URL verwendet und als jeweiliger Wert wird der Index des betreffenden Elements in der List<T> gespeichert. Das ganze verhält sich ähnlich wie verzweigte Arrays.

Das Dictionary wird nach einer URL abgefragt und liefert den Indexwert des betreffenden SiteEntry-Objekts in der List<T>. Nun wird das Objekt,dessen Index jetzt bekannt ist, direkt und ohne Iteration aus der List<T> zurückgegeben. Auf diese Art und Weiße besitzt der Seitenindex jetzt auch eine Methode, die einem O(1)-Vorgang nahe kommt.
Die Erstellung des parallelen Dictionary ist denkbar einfach. Wenn ein Element dem Seitenindex, also einer List<T>, hinzugefügt wird, fügt die Liste dieses Element am Ende an. Dem Dictionary kann jetzt ein Eintrag mit der aktuellen URL als Schlüssel und der Länge der List<T> –1 als Wert hinzugefügt werden.

public void Add(SiteEntry item)
{
    // prüfen ob der Eintrag noch nicht vorhanden ist
    if (!list.Contains(item))
    {
        this.list.Add(item);

		// Eintrag im Dictionary erzeugen
        this.index.Add(item.Url, this.list.Count - 1);
    }
}

Wenn ein Eintrag aus der List<T> gelöscht wird, muss das Dictionary natürlich ebenfalls aktualisiert werden.

Werfen wir jetzt einen Blick auf den Ablauf einer Suche.

// Liste welche die URLs der Ergebnisse aufnimmt.
List<Uri> uriList = new List<Uri>();

// die einzelnen Suchwörter abfragen
foreach (var word in searchTerms)
{
    // Liste für ein einzelnen Suchwort
    List<Uri> results = null;

    if (SiteSearch.IsRealWord(word))
    {
        // "echtes" Wort; kodiert suchen
        results = (List<Uri>)this.fulltextCatalog.Find(        ColognePhonetic.Encode(word));
    }
    else
    {
        // Abkürzung oder Formel; Klartextsuche
        results = (List<Uri>)this.fulltextCatalog.Find(word);
    }

    // prüfen ob Resultate vorliegen
    if (results == null)
    {
        continue;   // nichts gefunden
    }

    // Resultate der URL-Liste hinzufügen
    foreach (var entry in results)
    {
        if (!uriList.Contains(entry))
        {
            uriList.Add(entry);
        }
    }
}

// Liste mit den Seiten als Ergebnis zur Auswertung erzeugen
List<SiteEntry> preSelected = new List<SiteEntry>(uriList.Count);

// die Liste anhand der gefundenen URLs aus dem Seitenindex füllen
foreach (var entry in uriList)
{
    preSelected.Add(this.siteIndex.Find(entry));
}

Für jedes Suchwort aus der Eingabemaske ist nur ein Zugriff als O(1)-Vorgang auf den Volltextkatalog nötig, um sofort alle relevanten URLs zum Suchwort zu erhalten. Die Zurückgegebenen URLs werden in der Liste uriList gesammelt bis alle Suchwörter abgearbeitet sind. Beim übernehmen in die uriList wird geprüft, ob die aktuelle URL aus dem Ergebnis bereits enthalten ist.
Anschließend wird die Liste preSelected als List<T> vom Typ SiteEntry erzeugt und mit den Seiten, die jeweils den URLs entsprechen, aus dem Seitenindex gefüllt. Auch hier ist jede Abfrage ein O(1)-Vorgang.
Wie man im obigen Listing sehen kann, müssen nur zwei Schleifen verwendet werden; ausgenommen der Schleife für die einzelnen Suchwörter.
Wenn es eine Möglichkeit gäbe um zwei Listen zu mergen, so dass in der resultierenden Liste jedes Element nur einmal vorkommt, könnte auch auf die Schleife in der Zeile 277 verzichtet werden.
Was jetzt noch zu tun bleibt, ist die Aus- und Bewertung der Ergebnisse. Eine Umsetzung dazu habe ich schon in Teil – 6 der Artikelreihe gezeigt.

Wen mit dem .NET-Framework in der Version 4.0 endlich offiziell die Parallelisierung Einzug hält, können auch längere Schleifen in ausreichend kurzer Zeit verarbeitet werden. Damit dürfte sich die Ausführungszeit einer Suche noch einmal deutlich verkürzen lassen. Vor allem die Bewertung der Resultate wird davon profitieren.

Das eben vorgestellte Konzept kommt meiner Vorstellung einer Websuche schon sehr nahe. Ein paar Details müssen aber noch überarbeitet werden. Durch die Verwendung der Kölner Phonetik besitzt die Suche schon eine gewisse Fehlertoleranz. So werden z.B.: Resultate zu “shared memory” geliefert auch wenn sich vertippt wird wie etwa": “sharde” anstatt “shared” oder “memmory” anstatt “memory”. Im Ergebnis wird jedoch noch nicht darauf hingewiesen. Um den Hinweis darauf umzusetzen, werde ich wohl um die Verwendung des “teuren” Algorithmus zur Berechnung der Levenshtein-Distanz nicht herumkommen.
Auch die Verwendung eines Thesaurus zum Umsetzen von Erweiterungslisten währe Sinnvoll. Damit könnte z.B.: bei der Eingabe von JS auch zusätzlich nach JScript oder JavaScript gesucht werden.
Die Umsetzung Thesaurus könnte ich mir in naher Zukunft vorstellen, aber für die Implementierung des Levenshtein-Algorithmus warte ich definitiv auf .NET 4.0.

Wenn ihnen der Artikel gefallen hat oder er für sie hilfreich war, bitte "kicken" sie ihn.