Robert Sedgewick: Algorithmen

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


19. Suchen in Zeichenfolgen



Zu verarbeitende Daten lassen sich oft nicht logisch in unabhängige Datensätze mit kleinen identifizierbaren Teilen zerlegen. Dieser Datentyp ist nur durch die Tatsache gekennzeichnet, daß er als Zeichenfolge (string) aufgeschrieben werden kann: eine lineare (gewöhnlich sehr lange) Folge von Zeichen.

Zeichenfolgen haben offensichtlich eine zentrale Bedeutung für Textverarbeitungssysteme, die eine Vielzahl von Möglichkeiten für die Bearbeitung von Text bereitstellen. Derartige Systeme verarbeiten Text-Zeichenfolgen, die grob als Folgen von Buchstaben, Ziffern und Sonderzeichen definiert werden können. Diese Objekte können sehr umfangreich sein (zum Beispiel enthält das vorliegende Buch über eine Million Zeichen), und effiziente Algorithmen spielen für ihre Bearbeitung eine wichtige Rolle.

Ein anderer Typ von Zeichenfolgen ist die binäre Zeichenfolge, eine einfache Folge von Einsen und Nullen. In gewisser Hinsicht ist dies nur ein spezieller Typ von Text-Zeichenfolgen, doch es ist zweckmäßig, diese Unterscheidung zu treffen; zum einen, weil für diese Typen unterschiedliche Algorithmen geeignet sind, zum anderen, weil binäre Zeichenfolgen in vielen Anwendungsfällen auf natürliche Weise entstehen. Zum Beispiel stellen einige Computergraphiksysteme Bilder als binäre Zeichenfolgen dar. (Dieses Buch wurde mit Hilfe eines solchen Systems gedruckt; die vorliegende Seite wurde zu einem bestimmten Zeitpunkt als binäre Zeichenfolge dargestellt, die aus Millionen von Bits bestand.)

In bestimmter Hinsicht sind Text-Zeichenfolgen völlig andere Objekte als binäre Zeichenfolgen, da sie aus Zeichen aus einem umfangreichen Alphabet aufgebaut sind. In anderer Beziehung sind die beiden Typen von Zeichenfolgen jedoch äquivalent, da jedes Textzeichen durch (beispielsweise) acht binäre Zeichen dargestellt werden kann, und da eine binäre Zeichenfolge als Text-Zeichenfolge betrachtet werden kann, indem aus acht Bits bestehende Abschnitte jeweils als ein Zeichen aufgefaßt werden. Wir werden sehen, daß die Größe des Alphabets, aus dem die Zeichen zur Bildung einer Zeichenfolge entnommen werden, ein wichtiger Faktor für die Entwicklung von Algorithmen zur Verarbeitung von Zeichenfolgen ist.

Eine grundlegende Operation mit Zeichenfolgen ist das pattern matching (Musteranpassung): Gegeben seien eine Text-Zeichenfolge der Länge N und ein Muster der Länge M; zu suchen ist ein Auftreten des Musters innerhalb des Textes. (Wir benutzen den Begriff »Text« selbst dann, wenn wir uns auf eine Folge von Einsen und Nullen oder einen anderen speziellen Typ von Zeichenfolgen beziehen.) Die meisten Algorithmen für dieses Problem können leicht dahingehend erweitert werden, daß sie alle Stellen finden, wo das Muster im Text vorkommt, da sie den Text sequentiell durchsuchen können und an der Stelle unmittelbar nach dem Beginn einer Übereinstimmung neu gestartet werden können, um die folgende Übereinstimmung zu finden.

Das Problem des Pattern Matching kann als ein Suchproblem (mit dem Muster als Schlüssel) charakterisiert werden, doch die Suchalgorithmen, die wir betrachtet haben, lassen sich nicht unmittelbar anwenden, da das Muster lang sein kann und da es in einer unbekannten Weise in den Text »eingebaut« ist. Dies ist ein interessantes Problem; erst in jüngster Zeit sind mehrere sehr unterschiedliche (und überraschende) Algorithmen entdeckt worden, die nicht nur eine Vielzahl von nützlichen praktischen Methoden liefern, sondern auch einige grundlegende Techniken der Entwicklung von Algorithmen illustrieren.


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