Vortrag: String-Matching

Gliederung

Teil I

1. Definitionen
2. Anwendungen von String-Matching
3. Beschreibung von DirectSearch
4. Implementierung von DirectSearch
5. Analyse von DirectSearch

Teil II

1. Bessere Verfahren
2. Beschreibung des Sunday-Algorithmus
3. Implementierung von Quick-Search
4. Analyse von Quick-Search
5. Weitere Optimierungsmöglichkeiten

1.1 Definitionen

• Gegeben sei eine Zeichenfolge s (eng. String) der Länge N und das Muster p (eng. Pattern) der Länge M
• Ein Vergleichsfenster w (eng. Window) ist eine Teilzeichenfolge der Länge M von s
• Gesucht wird die erste Position i für 0 <= i <= N – M in s, für die das Vergleichsfenster mit dem Muster übereinstimmt: w = p

1.2 Anwendungen

• Texteditoren: Suche von Schlüsselwörtern in Text, Variablennamen in Programmen usw.
• Commandlinetools für die Textsuche z.B. grep unter Unix
• Virenscanner: Auffinden von Virensignaturen in Dateien
• Biochemie: Suche nach Basensequenzen in einem Genom

1.3 DirectSearch-Beschreibung

Vergleich zwischen Muster und String, bei welchem das Muster jeweils um 1 Zeichen nach rechts verschoben wird sobald ein Mismatch aufgetreten ist, tritt kein Mismatch auf ist der String gefunden.

Beispiel:

Pattern = „hard“
String  = „Change is hard, but stagnation is fatal!“
01.Schritt hard
02.Schritt  hard
...
11.Schritt           hard → gefunden

1.4 DirectSearch-Implementierung

1
2
3
4
5
6
7
8
9
10

public void directSearch(byte[] s, byte[] p)
{
    sloop: for(int i = 0 ; i < s.length - p.length + 1 ; i++)
    {
        for(int j = 0 ; j < p.length ; j++)
            if(s[i+j] != p[j]) continue sloop;  //Mismatch?
        return i; //Pattern gefunden
    }
    return -1; //Pattern nicht gefunden
}

Anmerkung 2026: Auf der Folie steht als Rückgabetyp void, die Methode liefert aber einen int-Wert zurück.

1.5 Analyse von DirectSearch

• Der Algorithmus durchläuft 2 verschachtelte Schleifen.
• Die Komplexität des Verfahrens liegt demzufolge bei O(N*M) → falls das Muster an jeder Position vollständig verglichen werden muss. (ungünstigster Fall)
• N und M stehen dabei für die maximale Lauflänge der beiden Schleifen.
• Die durchschnittliche Komplexität liegt allerdings nur bei O(N), weil in den meisten Fällen schon sehr früh ein Mismatch zustande kommt (im Schnitt nach dem 1,15-ten Zeichen in deutschsprachigen Texten)

2.1 Bessere Verfahren

• Knuth-Morris-Pratt Algorithmus
• Boyer-Moore Algorithmus
  → beide Verfahren verwenden Informationen aus bereits erfolgten Vergleichen.
  → die Algorithmen sind kurz aber komplex
• Ähnlich effizient ist der nach seinem Entdecker D.M. Sunday benannte Algorithmus in der Quick-Search-Variante.

2.2 Der Sunday-Algorithmus

(Mismatch) (Zeichen rechts vom Vergleichsfenster)

Bsp: Pattern = „Wissen“
     String  = „Phantasie ist wichtiger als Wissen“
     1.Schritt  Wissen

     String  = „Phantasie ist wichtiger als Wissen“
     2.Schritt     Wissen

     String  = „Phantasie ist wichtiger als Wissen“
     3.Schritt            Wissen

Anmerkung 2026: Die Originalfolien mit der ursprünglichen Anordnung stehen oben als PowerPoint-Dateien zum Download.

2.3 QuickSearch-Implementierung

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public static int quickSearch(byte[] s, byte[] p)
{
    int[] shiftTab = new int[256];  //Shift-Tabelle
    for (int i = 0 ; i < 256 ; i++)
        shiftTab[i] = p.length + 1;
        //Initialisierung mit Musterlänge + 1

    for (int i = 0 ; i < p.length ;  i++)
    {
        int tabPos = p[i] & 0xff;  //typeCast byte→int
        shiftTab[tabPos] = p.length - i;
    }

    int i = 0;
    int pdecr = p.length - 1;
    while(i < s.length - p.length + 1)
    {
        ploop: for (int j = 0 ; j < p.length ; j++)
        {
            if(s[i+j] != p[j])
                break ploop;
            if(j == pdecr)
                return i;
        }
        int shiftEntry=s[i + p.length] & 0xff;
        i += shiftTab[shiftEntry];
    }
    return -1;
}

2.4 Analyse von Quick-Search

• Im ungünstigsten Fall hat er ebenfalls eine Komplexität O(N*M)
• Mit Modifikationen ähnlich zum Knuth-Morris-Pratt-Algorithmus kann der Aufwand auf O(N) beschränkt werden.
• Im günstigsten Fall werden nur O(N/M) vergleiche benötigt → wenn das Zeichen nach dem Fenster nie im String vorkommt.

2.5 Weitere Optimierungsmöglichkeiten

• Optimal-Mismatch-Strategie, d.h. man vergleicht erst die Zeichen des Musters mit dem Fenster, welche die geringste Häufigkeit haben.
• Falls die Häufigkeitsverteilung am Anfang unbekannt ist, so kann Sie dynamisch während der Suche ermittelt werden.