http://matthias-hielscher.de/blog/464/String-Suchalgorithmen_in_C.html
Dez
29

String-Suchalgorithmen in C#

Für eine Software (ich stelle sie irgendwann hier vor) benötige ich einen Suchalgorithmuns, der Strings bzw. Texte durchsucht. Nicht immer findet sich ohne Weiteres Source, den man 1:1 in seine Anwendung kopieren und verwenden kann. Aufwändiges Übersetzen und Debuggen ist daher notwendig.

Im Folgenden finden sich 2 bekannte Suchalgorithmen:
  • Knuth-Morris-Pratt Search Algorithm
  • Rabin-Karp Search Algorithm

Ich selbst setze sie modifiziert ein, um die Performance in meinem speziellen Fall zu steigern. Hier werden jedoch die nach C# übersetzten Standardalgorithmen gezeigt. Beide suchen nach einer exakten Übereinstimmung des Suchwortes in einem Text und liefern bei einem Fund die erste Position im Text zurück. Wird keine Übereinstimmung festgestellt, beträgt der Rückgabewert -1.

C#-Code:
/* Knuth-Morris-Pratt Search Algorithm (C#)
 * 
 * Parameters: source   - text to search
 *             value    - keyword
 *             
 * Return Value: Position of the keyword within the text
 *               -1 if keyword is not included
 *               
 * Translator: Matthias Hielscher
 *
 * Licence: Creative Commons BY-SA
 */
private int KnuthMorrisPrattSearchAlgorithm(string source, string value)
{
	int m = 0;
	int i = 0;
	int[] t = new int[value.Length];

	while (((m + i) < source.Length) && (i < value.Length))
	{
		if (source[m + i] == value[i])
		{
			i++;
		}
		else
		{
			m += i - t[i];
			if (i > 0)
			{
				i = t[i];
			}
			i++;
		}
	}
	return (i == value.Length) ? m : -1;
}

// usage (example)
private bool IsKeywordMatching(string source, string value)
{
	return KnuthMorrisPrattSearchAlgorithm(source, value) != -1;
}

C#-Code:
/* Rabin-Karp Search Algorithm (C#)
 * 
 * Parameters: source   - text to search
 *             value    - keyword
 *             alphLen  - number of characters of the alphabet (e.g. 256 if ASCII)
 *             modPrime - a prime number (the higher, the quicker, but too high is bad)
 *             
 * Return Value: Position of the keyword within the text
 *               -1 if keyword is not included
 *               
 * Translators: Matthias Hielscher, Frederic Kerber
 *
 * Licence: Creative Commons BY-SA
 */
private int RabinKarpSearchAlgorithm(string source, string value, int alphLen, int prime)
{
	int n = source.Length;
	int m = value.Length;
	int h = (int)(Math.Pow(alphLen, m - 1.0) % prime);

	int p = 0;
	int t0 = 0;

	if (n < m)
	{
		return -1;
	}

	for (int i = 0; i < m; i++)
	{
		p = (int)((alphLen * p + value[i]) % prime);
		t0 = (int)((alphLen * t0 + source[i]) % prime);
	}

	int ts = t0;

	for (int s = 0; s <= n - m; s++)
	{
		// calculate hash t_s
		if (p == ts)
		{
			if (value == source.Substring(s, m))
			{
				return s;
			}
		}

		if (s < n - m - 1)
		{
			ts = (int)((alphLen * (ts - (source[s]) * h) + (source[s + m])) % prime);

			if (ts < 0)
			{
				ts += prime;
			}
		}
	}

	return -1;
}

// usage (example)
private bool IsKeywordMatching(string source, string value)
{
	return RabinKarpSearchAlgorithm(source, value, 256, 127) != -1;
}

Dieses Werk bzw. Inhalt ist unter einer Creative Commons-Lizenz lizenziert.

Bleibe auf dem Laufenden!

Wenn du den RSS-Feed abonnierst, wirst du über neue Blogeinträge benachrichtigt.

Kommentare

  • R2C2
    29.12.2009, 10:37
  • Schön. Wenn ich sowas mal brauche, weiß ich, wo ich nachgucken kann. \:\-\)

    BTW: Der Ternäroperator (bei den Beispielen) ist hier unnötig. Das ist doch schon bool...
    Und die string-Parameter könnten n const vertragen. Oder ist das in C# anders. Hab schon ewig kein C# mehr gemacht...

    mfg

    Christian
  • Matze
    (registriert)
    29.12.2009, 12:40
  • Hallo Christian,

    stimmt danke, ich habe es in den Beispielen geändert. "const string source" geht so als Parameter in C# nicht. Ob es anders irgendwie möglich ist, weiß ich nicht.

    Grüße, Matze
  • Daniel
    29.12.2009, 15:46
  • Unter welcher Lizenz stehen diese beiden Codestücke?

    Gruß,
    Daniel
  • Matze
    (registriert)
    29.12.2009, 20:27
  • Hi Daniel,

    dass man eine Lizenz auch bei Standardalgorithmen angeben kann, wusste ich nicht. Ich habe nun die Creative Commons gewählt, die auch die kommerzielle Nutzung zulässt.

    Grüße, Matze

Einen Kommentar schreiben

 
 
  • : *
  • :
  • : *
* Pflichtfelder