Kurs:Algorithmen und Datenstrukturen/Vorlesung/Naiver Algorithmus Textsuche

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 betrachten wir einen naiven Algorithmus zur Textsuche.

Problem der Worterkennung

Direkte Lösung - brute force

a

b

a

c

a

a

b

a

c

c

a

b

a

c

a

b

a

a

b

b

a (1)

b (2)

a (3)

c (4)

a (5)

b (6)

a (7)

b

a

c

a

b

a (8)

b (9)

a

c

a

b

....

a (22)

b (23)

a (24)

c (25)

a (26)

b (27)

Pseudocode Brute Force Algorithmus

for i=1 to n-m+1 do

Falls pat = text[i...i+m-1] gib i zurück;

Gib -1 zurück

In Java:

  
int bruteforce_search(char[] text, char[] pat){
    int i,j;
    for(i = 0; i < text.length - pat.length+1; i++){
        for(j = 0; j < pat.length && pat[j] == text[i+j]; j++)
            ;
        if(j == pat.length)
            return i;
    }
    return -1;
}

Analyse

Das Terminierungstheorem besagt, dass der Algorithmus bruteforce_search bei endlicher Eingabe nach endlich vielen Schritten terminiert.

Das Theorem der Korrektheit besagt, wenn text die Zeichenkette pat enthält, so gibt bruteforce_search(text,pat) den Startindex des ersten Vorkommens von pat zurück, ansonsten -1.

Das Theorem der Laufzeit besagt, dass der Algorithmus bruteforce_search einen Worst-Case Laufzeit von $\Theta (mn)$ hat. Beweisen lässt sich das durch eine einfache Schleifenanalyse. Die äußere for-Schleife wird maximal (n-m)-mal durchlaufen, die innere for-Schleife wird jedes mal maximal m-mal durchlaufen:

$\Theta ((n-m)*m)=\Theta (mn)$

Dafür hat bruteforce_search nun einen Platzbedarf von $\Theta (1)$. Kann man durch zusätzlichen Platzbedarf die Laufzeit verbessern?

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.