Schnelle Suche in großen Texten mit C#

Für ein kleines Projekt hatte ich die Anforderung große Texte schnell zu durchsuchen. Nach ein wenig Suche bin ich auf den Boyer-Moore Algorithmus gestoßen welcher mir für das Problem ausreichend zu sein schien.
Eine gute Erklärung zu dem o.g. Algorithmus findet man auf Wikipedia (Suchwort Boyer-Moore). Daher spare ich mir hier eine ausführliche Erläuterung.

Los geht’s

Die erste Klasse die ich für die Implementierung benötigte war eine EventArgs Klasse mit der eine Fundstelle des gesuchten Textes angezeigt werden soll.
Diese Klasse sieht wie folgt aus:

public class TextFoundEventArgs : EventArgs
{
    public int Position { get; set; }
    public int Length { get; set; }
}  

Die Property „Length“ gibt dabei die Länge des gefundenen Textes an und die Property „Position“ die Zeichenposition innerhalb des Suchtextes. Beides kann später genutzt werden um z.B. in einer RichTextBox den gefundenen Text farbig zu markieren.

Die Suche

Als nächstes wird noch eine Klasse benötigt, die die eigentliche Suche durchführt. Diese Klasse sieht wie folgt aus:

// Delegate für den Event
public event TextFoundEvent OnTextFound;

public class BoyerMooreSearch
{
    // Event um die Fundstelle anzuzeigen
    public event TextFoundEvent OnTextFound;

    public void SearchText(string word, string text)
    {
        // Sprungtabelle mit maximaler Wortlänge initialisieren.
        var jumpTable = new int[256];
        for (int index = 0; index < jumpTable.Length; index++)
        {
            jumpTable[index] = word.Length;
        }

        // Sprungtabelle für die Buchstaben des Suchwortes füllen
        for (int index = 0; index < word.Length - 1; index++)
        {
            jumpTable[word[index]] = (word.Length - 1) - index;
        }
            
        var i = 0;
        while (i <= text.Length - word.Length)
        {
            var k = word.Length - 1;
            while (k >= 0 && text[i + k] == word[k])
            {
                k--;
            }

            if (k == -1)
            {
                // Event aufrufen um Fundstelle anzuzeigen.
                OnTextFound?.Invoke(new TextFoundEventArgs { Position = i, Length = word.Length });
            }

            i += jumpTable[text[i + word.Length - 1]];
        }
    }
}

Der ganze Rest oder wie ich es anwende

Nachdem nun alle nötigen Klassen erstellt wurden kann man die Klasse wie folgt nutzen:

var boyerMoore = new BoyerMooreSearch();
boyerMoore.OnTextFound += OnTextFound;

private void OnTextFound(TextFoundEventArgs e)
{             
    richTextBox1.Select(e.Position, e.Length);
    richTextBox1.SelectionColor = Color.Black;
    richTextBox1.SelectionBackColor = Color.Yellow;    
}

Interessant ist der Teil in der Methode „OnTextFound“. Hier werden die Daten aus der Klasse TextFoundEventArgs verwendet um den gefundenen Suchtext in einer RichTextBox farbig zu hinterlegen. Dies vereinfacht die Übersicht gerade in sehr langen Texten enorm.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.