Notizen

Boyer-Moore-Algorithmus

tagsalgorithmen, suchalgorithmen

Der Boyer-Moore-Algorithmus ist ein Textsuchalgorithmus, welcher durch Heuristiken sublineare Laufzeit erzielt.

Idee

  • Der Text wird von links nach rechts durchlaufen
  • An jeder Position wird das Muster von rechts nach links zeichenweise mit dem Text verglichen
  • Sobald eine Ungleichheit eines Zeichens erkannt wird, wird das Muster soweit wie möglich am Text entlang weitergeschoben

Laufzeit

Da es bei fast jeder Positionierung sofort um eine Nichtübereinstimmung kommt, springt das Muster über den Text und die Laufzeit entspricht im Schnitt

Implementierung

Schlechtes Zeichen (bad character) Heuristik

  • Funktion shift(c)
  • Gibt für jedes Zeichen des Alphabets an, wie groß der Abstand zum rechtesten Ende des Musters ist
  • Kommt nicht vor, hat shift die Länge des Musters
  • Kommt mehrmals vor, gibt shift das rechteste Vorkommen an
  • Die shift-Tabelle kann einmalig zu Beginn der Suche in Zeit berechnet werden

Beispiel

  • Muster: ende
  • Alphabet: {a, b, c, d, e, n}
Zeichenabcden
Shift444102
a d e b e n e n d e b c
      |       |   |
e n d e       |   |        shift(b) = 4 Zeichen weiterschieben
        e n d e   |        shift(n) = 2 Zeichen weiterschieben
            e n d e        shift(e) = 0 => Muster abgleichen

Implementierung

// Einfache Funktion die jedem Buchstaben einen 
// eindeutigen Zahlenwert zuweist
int GetIndex(char a) {
 
	if (a == ' ') 
		return 26;
		
	if (a == ',') 
		return 27;
		
	return ((int)a - 65);
}
 
int BoyerMooreSearch(char text[], int textLength, char pattern[], int patternLength) {
 
	// Heuristiktabelle anlegen und initialisieren
 
	int sizeOfAlphabet = 28;
	int *shift = new int[sizeOfAlphabet];
 
	// Maximale Shiftwerte für alle Buchstaben  
	// die nicht Teil des Musters sind
	
	for (int i=0; i<sizeOfAlphabet; i++) 
		shift[i] = patternLength;
 
	// Shiftwerte berechnen
	
	for (int i=0; i<patternLength; i++) 
		shift[getIndex(pattern[i])] = patternLength-i-1;
	
	int count = 0;
	
	int textIndex = patternLength-1;
	int patternIndex = patternLength-1;
	
	while (textIndex < textLength) {
		if (text[textIndex] == pattern[patternIndex]) { 
			if (patternIndex == 0) { 
				// Vorkommen gefunden
				count++; 
				textIndex += patternLength; 
				patternIndex = patternLength-1; 
			} else {  
				textIndex--; 
				patternIndex--;
			}
		}
		
		else {
			// Falls der Shift-Eintrag weniger Zeichen nach rechts gehen 
			// würde als man schon nach links gegangen ist
			// (z.B. man hat schon 3 richtige Buchstaben abgeglichen,
			// jetzt kommt ein falscher mit shiftwert 2)
			if (patternLength-patternIndex > shift[getIndex(text[textIndex])]) { 
				// Shifte um die Anzahl an Buchstaben die man schon gegangen ist
				textIndex = textIndex + patternLength - patternIndex; 
			} else { 
				// Shifte um den Shiftwert
				textIndex = textIndex + shift[getIndex(text[textIndex])];
			}
			// Ein Buchstabe weiter
			patternIndex = patternLength-1;
		}
	}
	return count;
}

Gutes Ende (good suffix) Heuristik

Backlinks