Laden...

Boyer-Moore-Horspool Suche (und weitere)

Erstellt von Th69 vor 11 Jahren Letzter Beitrag vor 11 Jahren 5.339 Views
Th69 Themenstarter:in
4.931 Beiträge seit 2008
vor 11 Jahren
Boyer-Moore-Horspool Suche (und weitere)

Beschreibung:

Nach einem PN-Austausch mit herbivore habe ich entdeckt, daß beim Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch noch keine Lösung für string-search Algorithmus á la Boyer-Moore gepostet wurde. Daraufhin habe ich heute meine alten C Sourcen dazu nach C# umgeschrieben.

Der Boyer-Moore-Algorithmus ist ein String-Matching-Suchalgorithmus, welcher besonders bei langen Texten und/oder Pattern zum Einsatz kommt, um die naive Suche zu beschleunigen, indem eine sog. Skip- sowie Shift-Tabelle erzeugt wird, um während der Suche viele Stellen zu ermitteln, an denen der Suchstring nicht beginnen kann und die deshalb übersprungen werden können (je länger der Eingabestring ist, desto mehr kann i.A. übersprungen werden - mit Beachtung von evtl. Suffix- und Präfixübereinstimmungen im Suchpattern).

Statt dem Boyer-Moore-Algorithmus ist die Verbesserung nach Horspool jedoch das einfachere und bessere Suchverfahren (da es nur noch eine Skip-Tabelle benötigt):


// Boyer-Moore-Horspool
static public void BMHSearch(string text, string pattern, Action<int> onHit)
{
	int n = text.Length;
	int m = pattern.Length;
	int m1 = m - 1;

	int[] skip = CalculateSkip(pattern);

	int s = m1;
	while(s < n)
	{
		int q = m1;
		while(q >= 0 && s < n)
		{
			int s2 = s;
			while(q >= 0 && pattern[q] == text[s2])
			{
				q--;
				s2--;
			}
			if(q >= 0)
			{
				s += skip[text[s]];
				q = m1;
			}
		}

		if(q < 0)
		{
			onHit(s-m+1);
			s++;
		}
	}
}

static int[] CalculateSkip(string pattern)
{
	int[] skipP = new int[MaxChars];
	int m = pattern.Length;

	for(int i = 0; i < MaxChars; i++)
		skipP[i] = m;

	for(int i = m-1, j = 0; i>0; j++, i--)
		skipP[pattern[j]] = i;

	return skipP;
}

Benutzen kann man diesen Code dann z.B. so, um eine Liste aller Positionen (Treffer) zu erhalten:


void FindHits(string text, string pattern)
{
    positions.Clear();
    BMHSearch(text, pattern, SearchHit);
}

private void SearchHit(int position)
{
    positions.Add(position);
}

private List<int> positions = new List<int>();

Desweiteren habe ich ein WinForms-Testprojekt erstellt (Anhang), in dem außerdem noch "Naive Search", "DFA (Deterministic Finite Automaton)" sowie auch das kompliziertere "Boyer-Moore" enthalten sind.

Der Code ist jetzt nicht unbedingt einfach zu verstehen (da ich weitestgehend die Original Variablen weiter benutzt habe), ich hoffe aber, der Code ist trotzdem nützlich.
Ergänzend muß ich noch sagen, daß sich diese Algorithmen erst bei sehr großen Texten lohnen, da die Vorverarbeitung einen großen Teil der Zeit in Anspruch nimmt (im C Code hatte ich nur den dort üblichen 8-Bit Datentyp (ASCII) benutzt, hier selbstverständlich den .NET Datentyp 'char', d.h. die Arrays sind größer und dementsprechend ergibt sich eine etwas längere Verarbeitungszeit).

Boyer-Moore, Boyer-Moore-Horspool, DFA, Suche, Suchalgorithmus, Suchalgorithmen

P
7 Beiträge seit 2012
vor 11 Jahren

Ist die Horspool Erweiterung schneller als BM mit Extended-Bad-Character und der Good-Suffix Regel?

Th69 Themenstarter:in
4.931 Beiträge seit 2008
vor 11 Jahren

Hallo,

ja, BMH ist schneller als BM, da (wie geschrieben) nur eine Tabelle bei der Vorverarbeitung erstellt werden muß. Und anstatt von vorne das Pattern mit dem Text zu vergleichen, wird rückwärts verglichen - dadurch wird auch die Hauptsuchschleife kürzer (und demnach etwas schneller). Schau dir einfach mal den Code dazu (aus dem Anhang) an: Search.cs.

P
7 Beiträge seit 2012
vor 11 Jahren

Nur um paar Sachen klar zustellen:

Ja BMH ist schneller als BM in der Vorverarbeitung (eine einfachere Version der Bad-Character Regel ohne Good-Suffix) aber so was fällt bei großen Texten und kleinen Pattern kaum ins Gewicht.

BM bleibt aber mit Good-Suffix und Extended-Bad-Character Regel im Worst-Case schneller. Da aber man meistens nur relativ kleine Texte mit ausreichend großen Alphabeten nimmt, reicht BMH mit der schnelleren Vorverarbeitung aus.