Kurs:Algorithmen und Datenstrukturen/Vorlesung/Textsuche Einleitung

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

Einleitung Suchen in Texten

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

• 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

• $\sum$ Alphabet, $\epsilon$ 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

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.