Kurs:Algorithmen und Datenstrukturen/Vorlesung/Textsuche Einleitung

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Einleitung Suchen in Texten[Bearbeiten]

Nun behandeln wir das Suchen in Texten. Das Problem ist das Suchen eines Teilwortes in einem langen anderen Wort. Dies ist eine typische Funktion der Textverarbeitung. Nun ist eine effiziente Lösung gesucht. Das Maß der Effizienz ist hierbei die Anzahl der Vergleiche zwischen den Buchstaben der Worte. Den Vergleich von Zeichenketten nennt man String-Matching und eine nicht übereinstimmende Position nennt man Mismatch.

Vorgegebene Daten[Bearbeiten]

  • Worte als Array:

- text[] zu durchsuchender Text

- pat[] 'Pattern', gesuchtes Wort

  • Wortlängen:

- n Länge des zu durchsuchenden Textes

- m Länge des gesuchten Wortes

  • Alphabet, leerer String

Abstrakte Algorithmenbeschreibung:

Eingabe: text[], pat[]

Ausgabe: Index i mit text[i...i+m]=pat[1...m+1] oder -1 falls das gesuchte Wort nicht im Text vorkommt.

Literatur[Bearbeiten]

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5 zu finden.


Vorheriges Thema.jpg Discussion Nächstes Thema.jpg