Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Boyer-Moore-Horspool Suche (und weitere)
Th69
myCSharp.de - Experte

Avatar #avatar-2578.jpg


Dabei seit:
Beiträge: 4137

Themenstarter:

Boyer-Moore-Horspool Suche (und weitere)

beantworten | zitieren | melden

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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Th69 am .
Attachments
private Nachricht | Beiträge des Benutzers
Patrickssj6
myCSharp.de - Member



Dabei seit:
Beiträge: 7
Herkunft: NRW

beantworten | zitieren | melden

Ist die Horspool Erweiterung schneller als BM mit Extended-Bad-Character und der Good-Suffix Regel?
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Patrickssj6 am .
private Nachricht | Beiträge des Benutzers
Th69
myCSharp.de - Experte

Avatar #avatar-2578.jpg


Dabei seit:
Beiträge: 4137

Themenstarter:

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
Patrickssj6
myCSharp.de - Member



Dabei seit:
Beiträge: 7
Herkunft: NRW

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers