Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


19. Suchen in Zeichenfolgen



Mehrfache Suche

Die bisher betrachteten Algorithmen sind alle auf ein spezielles Suchproblem ausgerichtet: auf das Finden des Auftretens eines gegebenen Musters in einer gegebenen Text-Zeichenfolge. Falls ein und dieselbe Text-Zeichenfolge Gegenstand vieler Suchen von Mustern sein soll, lohnt es sich, die Zeichenfolge so zu bearbeiten, daß nachfolgende Suchvorgänge effizient erfolgen.

Wenn eine große Anzahl von Suchvorgängen vorliegt, kann das Problem der Suche in Zeichenfolgen als ein Spezialfall des allgemeinen Suchproblems angesehen werden, das wir im vorangegangenen Abschnitt untersuchten. Wir behandeln die Text-Zeichenfolge einfach als N sich überlappende »Schlüssel«, wobei der i-te Schlüssel per Definition a[i..N] ist, die gesamte Text-Zeichenfolge ab Position i. Natürlich operieren wir nicht mit den Schlüsseln selbst, sondern mit auf sie weisenden Zeigern: Wenn wir die Schlüssel i und j vergleichen müssen, nehmen wir zeichenweise Vergleiche vor, beginnend bei den Positionen i und j in der Text-Zeichenfolge. (Wenn wir am Ende ein »Marken«-Zeichen verwenden, das größer als alle anderen Zeichen ist, ist einer der Schlüssel stets größer als die anderen.) Dann können Hashing, Binärbaum-Suche und andere Algorithmen aus dem vorangegangenen Kapitel direkt angewandt werden. Erst wird aus der Text-Zeichenfolge eine vollständige Struktur aufgebaut, und dann können effiziente Suchmethoden für spezielle Muster durchgeführt werden.

Wenn Suchalgorithmen in dieser Weise auf die Suche in Zeichenfolgen angewandt werden, müssen viele Einzelheiten ausgearbeitet werden; unsere Absicht ist es, dies als einen gangbaren Weg für manche Suchanwendungen in Zeichenfolgen aufzuzeigen. In unterschiedlichen Situationen sind unterschiedliche Methoden zweckmäßig. Wenn zum Beispiel immer nach Mustern gleicher Länge gesucht wird, wird eine wie bei der Methode von Rabin-Karp mit einem einzigen Durchsuchen erzeugte Hash-Tabelle im Durchschnitt konstante Suchzeiten liefern. Wenn dagegen die Muster unterschiedliche Längen haben, so könnte eines der auf Bäumen beruhenden Verfahren geeignet sein. (Patricia eignet sich besonders für die Anpassung an derartige Anwendungen.)

Andere Änderungen des Problems können dieses wesentlich komplizierter machen und zu völlig anderen Verfahren führen, wie wir in den nächsten beiden Kapiteln feststellen werden.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]