MATCH!

In der Computerei spielt das Auffinden von Teilstrings innerhalb eines Strings eine zentrale Rolle. Ein kleines C-Progrämmchen erledigt diesen Job. Daß es dabei auch die Verwendung von Wildcards erlaubt, versteht sich von selbst...

Fast jede Programmiersprache hält irgendeinen Befehl bereit, mit dessen Hilfe man Substrings finden kann. INSTR, POS, SUBSEG sind einige der bekannteren Vertreter: UNIX stellt für derlei Abfragen die Prozedur fgrep zur Verfügung. In C dagegen gibt es standardmäßig nur die beiden Funktionen index() und rindex(), die auf das erste bzw. letzte Vorkommen eines Zeichens innerhalb einer Zeichenkette prüfen. Mager.

Wilde Karten -neu gemischt

Die Funktion match() ist nicht nur in der Lage, Substrings ausfindig zu machen, sondern sie erlaubt auch die Verwendung von sogenannten Wildcards. Diese Zeichen ersetzen entweder genau ein beliebiges Zeichen (jedoch nicht '\0’), dann nennt man sie Einzelquantoren. oder aber beliebig viele (auch null) beliebige Zeichen - dann heißen sie eben Allquantoren. Sehr sinnvoll erweisen sich diese Wildcards in Verbindung mit der Suche nach bestimmten Dateien, wozu die GEMDOS-Funktion SFIRST (0x4E) die beiden Quantoren '?' und **’ bereitstellt. Ok, kennt jeder. Allerdings wird dabei ein wenig “gemogelt”, weil der Dateiname in zwei Segmente aufgegliedert wird (Name und Extender). Steht nun in einem der Bereiche ein Sternchen, wird er ab dieser Stelle mit Fragezeichen aufgefüllt, egal ob hinter dem Stern noch etwas kommt oder nicht! Für das ST-Directory-System mag’s ja genügen, in anderen Systemen wie UNIX sind da schon etwas diffizilere Abfragen nötig (Beispiel gefällig? Bitte: pDoc?_V0??). Abgesehen von Dateisystemen gibt es aber auch noch Textverarbeitung. Die Praxis hat gezeigt, daß es hin und wieder recht nützlich ist, eine Datei auf das Vorkommen einer Zeichenkette zu untersuchen. Hier läßt sich match() gewinnbringend zum Einsatz bringen. Der Patternstring (also der, in dem drinsteht, was gesucht werden soll) darf eine beliebige Kombination aus normalen Zeichen, All- und Einzelquantoren enthalten und muß nach dem Sourcestring (das ist der andere!) als zweiter Pointer übergeben werden. Der dritte Parameter ist die Adresse eines Stringpointers. Falls das Muster gefunden werden kann, enthält er die Adresse, ab der das letzte Muster gematcht werden konnte. Ein Beispiel: Sourcestring ="holladibolla”, Patternstring==”oll??” gibt außer dem Ergebnis TRUE den Zeiger auf “dibolla” zurück. Das hat folgenden Vorteil: möchte man untersuchen, ob die Suchzeichenfolge nochmal vorkommt, muß man die Funktion match nur noch einmal mit dem um 1 erhöhten Stringzeiger aufrufen und schon wird richtigerweise FALSE zurückgegeben, weil durch die beiden Einzelquantoren noch mindestens zwei Zeichen hinter “oll” folgen müßten. Wäre dagegen beim ersten Aufruf “holladibolla" zurückgegeben worden, was sicherlich ein richtiges Ergebnis gewesen wäre, hätte ein zweiter Aufruf mit “olladibolla” wegen des führenden Allquantors () wieder ein “TRUE” ergeben, was sicherlich nichts weltbewegend Neues gebracht hätte. Übrigens kann man die beiden Quantoren beliebig umdefinieren (s. Demo), falls sie Bestandteil des Sourcestrings sein sollten!

Kochrezept für “Match mit Quantor”

Zunächst einmal müssen die Stringlängen ermittelt werden, damit man auch weiß, wann man spätestens mit der Suche aufzuhören hat. Sollte mindestens einer der Strings leer sein, erübrigt sich natürlich die Suche. In einer Endlosschleife wird dann der String auseinandergenommen. Enthalten beide Strings ein normales Zeichen (also keinen Quantor), wird die Suche erfolglos beendet, wenn sie nicht übereinstimmen. Enthält der Patternstring einen Einzelquantor, muß im Sourcestring noch mindestens ein Zeichen vorhanden sein. Soweit, so hoopy. Lustig wird's erst beim Auftreten eines Allquantors. Angenommen, man sucht im String “Oh du zerfrettelter Grunzwanzling” das Muster “nzl”. Läuft man sequentiell durch den String, findet man zuerst das “nz” von “Grunz”. Das Problem ist, daß kein “1” folgt und also das Muster hier nicht greift. Wohl aber bei “wanzling”. Schlimmer wird’s, wenn Quantoren geschachtelt auftreten (*n?l??*)! Man kann sich beliebig komplexe Suchzeichenfolgen ausdenken (die nur so von Quantoren strotzen), und ebenso fiese Sourcestrings, bei denen es einem vom bloßen Hinsehen schwindlig wird. Mit sequentiellen Algorithmen gerät man hier doch sehr schnell an die Grenzen des Abstraktionsvermögens! Viel einfacher ist in solchen Fällen die Verwendung von rekursiven Prozeduren. Betrachten Sie einmal, was passiert, wenn ein Allquantor im Muster auftaucht: Zunächst wird geprüft, ob es das letzte Zeichen im Muster ist. Falls ja, ist die Suche erfolgreich gewesen. Ansonsten muß das nächste Zeichen im String gesucht werden, das mit dem nächsten Zeichen des Musters (also dem hinter dem Allquantor) übereinstimmt. Ein Sonderfall tritt auf, wenn der String bereits vollständig durchsucht wurde, aber im Muster ein weiterer Allquantor auftaucht. Dieser matcht nämlich per Definition auch null Zeichen, so daß die Suche nicht einfach erfolglos abgebrochen werden darf! Andernfalls darf die Rekursion ihre Fähigkeiten demonstrieren: Falls es möglich ist, den String ab der aktuellen Position zu matchen, war die Suche erfolgreich: sonst wird es rekursiv einfach ab der nächsten Position versucht und zwar solange, bis der String komplett abgeprüft wurde (is>ls). In diesem Falle ist die Suche dann wirklich erfolglos. Das Schöne an der Rekursivität ist, daß sie immer zum richtigen Ergebnis gelangt; man braucht sich überhaupt nicht darum zu kümmern, wieso und weshalb - sie tut's einfach! Herrlich. Mittels dem printf()-Statement zu Beginn der Prozedur kann man die Arbeitsweise des Algorithmus bei Auftreten von Allquantoren nachvollziehen.

MatchQ ist sehr flexibel: Übergibt man ihr als Maske eine in Allquantoren eingebettete Zeichenkette (z.B. blub), verhält sie sich genau wie INSTR oder POS; läßt man den letzten Stern weg, so werden nur solche Strings gematcht, in denen die Maske am Ende auftaucht (wie bei "Lausblub”), und insgesamt kann man damit viel filigranere Dateisuchen veranstalten als mit SFIRST.

Fazit: Match! kann zwar nicht als Ersatz für die Query Language einer Datenbank dienen, erleichtert aber das Suchen von Dateien und Texten nicht unerheblich.

MS

/******************************************************\
*             > > >  M A T C H !  < < <                *
*======================================================*
* Univers.Suchfkt. z.Auffinden v.Substrings ü. Muster  *
* Sprache: MEGAMAX C  Autor: M. Schumacher   15.02.88  *
\******************************************************/

#include <stdio.h>

match(what, how, where, all, one)
		char *twhat, *how, **where, all, one;
{
	char *s, *p;				/*	Stringpointer für what/how */
	int ls=0, lp=0, is=1, ip=1;	/* Stringlängen, Laufvariablen */
	*where=what; /* Falls s gematscht werden kann, dann ab hier */
	s=what; while (*s++) ls++; s=what; /* Stringlängen bestimmen */
	p=how; while (*p++) lp++; p=how;
	if (!(ls*lp)) return(0);	/*	Leerstring übergeben = >FAIL! */
	printf("Vergleiche: >%s< (%d) mit >%s< (%d):\n", s, ls, p, lp);
	while (1)
	{ if (*p == one)
		{	if (is>ls) return(0);
			++is; ++s; ++ip; ++p;
			if ((is>ls) && (ip>lp) ) return(1);
			if (ip>lp) return(0);
			continue;
		}
		if (*p == all)
		{	if (ip == lp) return(1);
			++ip; ++p;
			if (is>ls) continue;
			do
			{ if (match(s, p, where, all, one)) return(1);
			++is; ++s; 
			}while Cis<=ls);
			return();
		}

		if ( (is>ls) || (!(*s++ == *p++ ))) return(0);
		++ip; if ((++ is>ls) && (ip>lp) ) return(1);
	}
}

main()
{
	char str[80], pat[80], *res, all, one;

	printf("Teststring eingeben! "); 
	gets(str);
	printf ("Allquantor	! *%c", 8); all=getchar();
	if (all == '\n') all = '*' else getchar();
	printf("Einzelquantor	: ?%c", 8); one=getchar()!
	if (one == '\n') one='?'; else getchar();
	while (1)
	{ 	printf("\n\nSuche nach; "); gets(pat); res=str; 
		while (match(res, pat, &res, all, one))
		{ printf("TRUE: <%s>\n", res); res++; } 
		puts("FAIL");
	}
}