Nadel im Heuhaufen: Ein raffiniertes Tutorial für groß angelegte Textsuchalgorithmen

Beim Begriff „Textsuche“ denkt man in der Regel an eine große Textmenge, die so indexiert ist, dass ein oder mehrere Suchbegriffe schnell nachgeschlagen werden können, wenn sie von einem Nutzer eingegeben werden. Dies ist ein klassisches Problem für Informatiker, für das es viele Lösungen gibt.

Aber wie wäre es mit einem umgekehrten Szenario? Was ist, wenn vorab eine Gruppe von Suchphrasen für die Indizierung zur Verfügung steht und erst zur Laufzeit ein großer Textkörper für die Suche präsentiert wird? Diese Fragen sollen in diesem Trie-Datenstruktur-Tutorial beantwortet werden.

Anwendungen

Eine reale Anwendung für dieses Szenario besteht darin, eine Reihe medizinischer Thesen mit einer Liste von Erkrankungen abzugleichen und herauszufinden, welche Thesen welche Erkrankungen behandeln. Ein weiteres Beispiel ist das Durchsuchen einer großen Sammlung von Präzedenzfällen und das Extrahieren der Gesetze, auf die sie sich beziehen.

Direkte Annäherung

Der grundlegendste Ansatz besteht darin, die Suchphrasen zu durchlaufen und den Text nach jeder Phrase einzeln zu durchsuchen. Dieser Ansatz lässt sich nicht gut skalieren. Die Suche nach einem String in einem anderen hat die Komplexität O(n) . Wiederholt man das für m Suchphrasen, führt das zu dem schrecklichen O(m * n) .

Der (wahrscheinlich einzige) Vorteil eines direkten Ansatzes ist, dass er einfach zu implementieren ist, wie im folgenden C#-Snippet deutlich wird:

 String[] search_phrases = File.ReadAllLines ("terms.txt"); String text_body = File.ReadAllText("body.txt"); int count = 0; foreach (String phrase in search_phrases) if (text_body.IndexOf (phrase) >= 0) ++count;

Wenn ich diesen Code auf meiner Entwicklungsmaschine [1] mit einem Testmuster [2] vergleiche, erhalte ich eine Laufzeit von 1 Stunde 14 Minuten – weit mehr als die Zeit, die Sie brauchen, um sich eine Tasse Kaffee zu schnappen, aufzustehen und sich zu strecken oder irgendeine andere Ausrede Entwickler verwenden, um Arbeit zu überspringen.

Ein besserer Ansatz - The Trie

Das vorherige Szenario kann auf verschiedene Weise verbessert werden. Beispielsweise kann der Suchprozess partitioniert und auf mehrere Prozessoren/Kerne parallelisiert werden. Aber die durch diesen Ansatz erzielte Verringerung der Laufzeit (Gesamtlaufzeit von 20 Minuten unter der Annahme einer perfekten Aufteilung auf 4 Prozessoren/Kerne) rechtfertigt nicht die zusätzliche Komplexität beim Codieren/Debuggen.

Die bestmögliche Lösung wäre eine, die den Textkörper nur einmal durchläuft. Dies erfordert, dass Suchphrasen in einer Struktur indiziert werden, die parallel zum Textkörper in einem Durchgang linear durchquert werden kann, wobei eine Endkomplexität von O(n) erreicht wird.

Eine Datenstruktur, die sich gerade für dieses Szenario besonders gut eignet, ist trie . Diese vielseitige Datenstruktur wird normalerweise übersehen und ist nicht so berühmt wie andere baumbezogene Strukturen, wenn es um Suchprobleme geht.

Das vorherige Tutorial von Toptal zu Trys bietet eine hervorragende Einführung in deren Strukturierung und Verwendung. Kurz gesagt, ein Trie ist ein spezieller Baum, der eine Folge von Werten so speichern kann, dass die Verfolgung des Pfads von der Wurzel zu einem beliebigen Knoten eine gültige Teilmenge dieser Folge ergibt.

Wenn wir also alle Suchphrasen zu einem Trie kombinieren können, bei dem jeder Knoten ein Wort enthält, haben wir die Phrasen in einer Struktur, in der die einfache Verfolgung von der Wurzel nach unten über einen beliebigen Pfad eine gültige Suchphrase ergibt.

Der Vorteil eines Trie ist, dass er die Suchzeit erheblich verkürzt. Um es für die Zwecke dieses Trie-Tutorials leichter verständlich zu machen, stellen wir uns einen binären Baum vor. Das Durchlaufen eines Binärbaums hat die Komplexität von O(log 2 n) , da sich jeder Knoten in zwei verzweigt und die verbleibende Durchquerung halbiert. Als solcher hat ein ternärer Baum die Traversierungskomplexität von O(log 3 n) . In einem Trie wird die Anzahl der untergeordneten Knoten jedoch von der Sequenz bestimmt, die er darstellt, und im Fall von lesbarem/aussagekräftigem Text ist die Anzahl der untergeordneten Knoten normalerweise hoch.

Textsuchalgorithmus

Nehmen wir als einfaches Beispiel die folgenden Suchbegriffe an:

• "gleiche Familie"
• „andere Familie“
• „getrennte Existenz“
• „Mitglieder der Liga“

Denken Sie daran, dass wir unsere Suchbegriffe im Voraus kennen. Also beginnen wir damit, einen Index in Form eines Tries zu erstellen:

Später präsentiert der Benutzer unserer Software eine Datei mit folgendem Text:

Die europäischen Sprachen sind Mitglieder derselben Familie. Ihre getrennte Existenz ist ein Mythos.

Der Rest ist ganz einfach. Unser Algorithmus hat zwei Indikatoren (Zeiger, wenn Sie möchten), einen, der an der Wurzel oder dem „Start“-Knoten in unserer Trie-Struktur beginnt, und der andere am ersten Wort im Textkörper. Die beiden Indikatoren bewegen sich Wort für Wort zusammen. Der Textindikator bewegt sich einfach vorwärts, während der Trie-Indikator den Trie in der Tiefe durchquert und dabei einer Spur übereinstimmender Wörter folgt.

Der Trie-Indikator kehrt in zwei Fällen zum Start zurück: Wenn er das Ende einer Verzweigung erreicht, was bedeutet, dass ein Suchausdruck gefunden wurde, oder wenn er auf ein nicht passendes Wort stößt, in diesem Fall wurde keine Übereinstimmung gefunden.

Eine Ausnahme von der Bewegung des Textindikators ist, wenn eine Teilübereinstimmung gefunden wird, dh nach einer Reihe von Übereinstimmungen wird eine Nichtübereinstimmung angetroffen, bevor die Verzweigung endet. In diesem Fall wird der Textindikator nicht weiterbewegt, da das letzte Wort der Beginn einer neuen Verzweigung sein könnte.

Wenden wir diesen Algorithmus auf unser Trie-Datenstrukturbeispiel an und sehen, wie es geht:

Wie wir sehen können, findet das System erfolgreich die beiden übereinstimmenden Ausdrücke „gleiche Familie“ und „getrennte Existenz“ .

Beispiel aus der realen Welt

Bei einem kürzlich durchgeführten Projekt wurde ich mit dem folgenden Problem konfrontiert: Eine Kundin hat eine große Anzahl von Artikeln und Doktorarbeiten, die sich auf ihr Arbeitsgebiet beziehen, und hat ihre eigene Liste mit Phrasen erstellt, die bestimmte Titel und Regeln darstellen, die sich auf dasselbe Gebiet beziehen Arbeit.

Ihr Dilemma war folgendes: Angesichts ihrer Phrasenliste, wie verknüpft sie die Artikel/Thesen mit diesen Phrasen? Das Endziel ist es, zufällig eine Gruppe von Phrasen auszuwählen und sofort eine Liste von Artikeln / Thesen zu haben, die diese bestimmten Phrasen erwähnen, die zum Greifen bereit sind.

Wie bereits erwähnt, gibt es zwei Teile, um dieses Problem zu lösen: Indizieren der Phrasen in einem Trie und die eigentliche Suche. Die folgenden Abschnitte bieten eine einfache Implementierung in C#. Bitte beachten Sie, dass Dateihandhabung, Codierungsprobleme, Textbereinigung und ähnliche Probleme in diesen Snippets nicht behandelt werden, da sie den Rahmen dieses Artikels sprengen.

Indizierung

Die Indizierungsoperation durchläuft einfach die Phrasen eine nach der anderen und fügt sie in den Trie ein, ein Wort pro Knoten/Ebene. Knoten werden mit der folgenden Klasse dargestellt:

 class Node { int PhraseId = -1; Dictionary<String, Node> Children = new Dictionary<String, Node>(); public Node() { } public Node(int id) { PhraseId = id; } }

Jede Phrase wird durch eine ID dargestellt, die so einfach wie eine inkrementelle Zahl sein kann, und an die folgende Indizierungsfunktion übergeben (Variablenstamm ist der eigentliche Stamm des Versuchs):

 void addPhrase(ref Node root, String phrase, int phraseId) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // break phrase into words String[] words = phrase.Split (); // start traversal at root for (int i = 0; i < words.Length; ++i) { // if the current word does not exist as a child // to current node, add it if (node.Children.ContainsKey(words[i]) == false) node.Children.Add(words[i], new Node()); // move traversal pointer to current word node = node.Children[words[i]]; // if current word is the last one, mark it with // phrase Id if (i == words.Length - 1) node.PhraseId = phraseId; } }

Suchen

Der Suchprozess ist eine direkte Implementierung des Trie-Algorithmus, der im obigen Tutorial besprochen wurde:

 void findPhrases(ref Node root, String textBody) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // a list of found ids List<int> foundPhrases = new List<int>(); // break text body into words String[] words = textBody.Split (); // starting traversal at trie root and first // word in text body for (int i = 0; i < words.Length;) { // if current node has current word as a child // move both node and words pointer forward if (node.Children.ContainsKey(words[i])) { // move trie pointer forward node = node.Children[words[i]]; // move words pointer forward ++i; } else { // current node does not have current // word in its children // if there is a phrase Id, then the previous // sequence of words matched a phrase, add Id to // found list if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); if (node == root) { // if trie pointer is already at root, increment // words pointer ++i; } else { // if not, leave words pointer at current word // and return trie pointer to root node = root; } } } // one case remains, word pointer as reached the end // and the loop is over but the trie pointer is pointing to // a phrase Id if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); }

Leistung

Der hier vorgestellte Code ist aus dem aktuellen Projekt extrahiert und wurde für die Zwecke dieses Dokuments vereinfacht. Das erneute Ausführen dieses Codes auf derselben Maschine [1] und gegen dasselbe Testmuster [2] führte zu einer Laufzeit von 2,5 Sekunden für den Aufbau des Tries und 0,3 Sekunden für die Suche. So viel zur Pause, oder?

Variationen

Es ist wichtig anzuerkennen, dass der in diesem Trie-Tutorial beschriebene Algorithmus in bestimmten Grenzfällen fehlschlagen kann und daher bereits mit vordefinierten Suchbegriffen entwickelt wurde.

Wenn beispielsweise der Anfang eines Suchbegriffs mit einem Teil eines anderen Suchbegriffs identisch ist, wie in:

• „ zum Teilen und Genießen mit Freunden“
• „Ich habe zwei Tickets , die ich mit jemandem teilen möchte“

und der Textkörper enthält einen Satz, der bewirkt, dass der Trie-Zeiger auf dem falschen Pfad beginnt, wie zum Beispiel:

Ich habe zwei Tickets, die ich mit Freunden teilen und genießen kann.

dann wird der Algorithmus keinen Begriff finden, da der Trie-Indikator nicht zum Startknoten zurückkehrt, bis der Textindikator bereits den Anfang des übereinstimmenden Begriffs im Textkörper passiert hat.

Es ist wichtig zu überlegen, ob ein solcher Randfall für Ihre Anwendung möglich ist, bevor Sie den Algorithmus implementieren. Wenn dies der Fall ist, kann der Algorithmus mit zusätzlichen Trie-Indikatoren modifiziert werden, um alle Übereinstimmungen zu einem bestimmten Zeitpunkt zu verfolgen, anstatt jeweils nur eine Übereinstimmung.

Fazit

Die Textsuche ist ein tiefes Gebiet der Informatik; ein Feld voller Probleme und Lösungen gleichermaßen. Die Art von Daten, mit denen ich es zu tun hatte (23 MB Text sind im wirklichen Leben eine Menge Bücher), mag wie ein seltenes Ereignis oder ein spezielles Problem erscheinen, aber Entwickler, die mit linguistischer Forschung, Archivierung oder jeder anderen Art von Datenmanipulation arbeiten , stoßen regelmäßig auf viel größere Datenmengen.

Wie im obigen Tutorial zur Trie-Datenstruktur deutlich wird, ist es von großer Bedeutung, den richtigen Algorithmus für das vorliegende Problem sorgfältig auszuwählen. In diesem speziellen Fall verkürzte der Trie-Ansatz die Laufzeit um erstaunliche 99,93 % von über einer Stunde auf weniger als 3 Sekunden.

Dies ist keineswegs der einzige wirksame Ansatz, aber er ist einfach genug und funktioniert. Ich hoffe, Sie fanden diesen Algorithmus interessant und wünsche Ihnen viel Glück bei Ihren Codierungsversuchen.

[1] Die für diesen Test verwendete Maschine hat die folgenden Spezifikationen:

• Intel i7 4700HQ
• 16 GB Arbeitsspeicher

Die Tests wurden unter Windows 8.1 mit .NET 4.5.1 und auch Kubuntu 14.04 mit der neuesten Mono-Version durchgeführt und die Ergebnisse waren sehr ähnlich.

[2] Die Testprobe besteht aus 280.000 Suchphrasen mit einer Gesamtgröße von 23,5 MB und einem Textkörper von 1,5 MB.