Suchen von Zeichenketten

Wie sucht man lange Zeichketten?

Kann man keine Vorarbeit leisten, so bleibt keine Alternative: Man beginnt einfach am Anfang des Textes und vergleicht den Text solange mit der gesuchten Zeichenkette, bis die entsprechende Stelle gefunden wurde.

Praktisch wäre es, wenn man eine Liste aller Wörter erzeugen könnte. Diesen "Inverted Index" kann man dann verwenden. Man vergleicht den Index mit der gesuchten Zeichenkette und kann dann so den Text finden. Dieses Verfahren ist allerdings aufwendig zu Implementieren und relativ langsam. Es gibt allerdings einige Suchmaschiene im Internet, die nach diesem Verfahren vorgehen. Eine davon ist die Suchmaschine Altavista.

Dort wird ein sogenannter Scooter eingesetzt, der URLs sammelt. Er durchsucht alle Internetseiten, die er findet, nach weiteren URLs. Hierbei werden alle anderen Elemente vernachlässigt. Die von 'fetch' erstellte Liste wird dann an 'build' weitergegeben. Nun durchsucht 'build' jede einzelne Seite. Diesemal werden fast alle HTML-Tags ignoriert und es wird der Text durchsucht. Ein HTML-Tag, daß nicht ignoriert wird ist zum Beispiel das Meta-Tag. In diesem für den Benutzer nicht sichtbaren Tag besteht eine Möglichkeit, die Suche zu manipulieren.

Eine Wortliste wird erstellt. Diese erstellten Wortlisten bilden den Web-Index. Wird nun eine Wortkombination gesucht vergleicht 'lookup' die gesuchten Wörter mit dem Web-Index. Wird die gesuchte Kombination ermittelt, speichert 'lookup' die URL ab und wenn die Suche beendet ist, bekommt der Benutzer alle Treffer präsentiert.

Weitere Informationen, wie Altavista arbeitet kann man sich hier anschauen.