Ich suche nach einer effizienten Datenstruktur, um String / Pattern Matching auf einer wirklich großen Menge von Strings durchzuführen. Ich habe von Versuchen, Suffix-Bäumen und Suffix-Arrays erfahren. Ich konnte jedoch bisher keine fertige Implementierung in C / C ++ finden (und die Implementierung scheint für mich schwierig und fehleranfällig zu sein). Aber ich bin mir immer noch nicht sicher, ob Suffix-Arrays wirklich das sind, was ich suche ... Ich habe libdivsufsort und esaxx ausprobiert, konnte aber nicht herausfinden, wie ich sie für meine Bedürfnisse verwenden kann:
Ich möchte eine vordefinierte Menge von Zeichenfolgen verwenden, mit Platzhaltern (oder sogar regulären Ausdrücken), um einer Benutzereingabe zu entsprechen. Ich habe eine riesige Liste von vordefinierten Strings, d. H.
"WAS IST *?" "Was ist XYZ?" "WIE VIEL *?" ...
Jetzt möchte ich die am besten passende Zeichenfolge finden (wenn es eine gibt, die überhaupt passt). I.e. Benutzereingabe: & gt; WAS IST XYZ? Sollte "WAS IST XYZ?" statt "WAS IST *?", sondern "WAS IST ETWAS?" sollte "WAS IST *?" (Angenommen, * ist ein Platzhalter für eine beliebige Anzahl von Zeichen).
Der Aufbau der Struktur ist nicht zeitkritisch (und die Struktur muss nicht superraumeffizient sein), aber die Suche sollte nicht zu lange dauern. Wie kann das leicht gemacht werden? Jedes Framework / Bibliothek oder Codebeispiel ist willkommen
Danke
Hier ist eine Lösung, die, glaube ich, gut funktionieren sollte, wenn Sie sehr viele Muster haben. Für nur 10k kann es übertrieben sein, und die Implementierung bedeutet relativ viel Arbeit, aber Sie könnten trotzdem interessiert sein.
Die Grundidee besteht darin, einen invertierten Index zu erstellen, der Teilzeichenfolgen der Mustermuster-IDs zuordnet. Zuerst erhält jedes Muster eine ID:
%Vor%Und dann erstellen wir einen invertierten Index. Im einfachsten Fall teilen wir die Muster in Token auf und ordnen jedes Token der Liste der Muster-IDs zu, in der es auftritt. Wir können flexibel sein, was wir als Token definieren, aber eine Methode ist anzunehmen dass jedes durch Leerzeichen getrennte Wort ein Token ist. Also hier ist der Index:
%Vor%Wenn Sie dann eine Eingabezeichenfolge vom Benutzer erhalten, teilen Sie diese in Token auf und suchen sie im Index nach. Sie kombinieren alle Muster-IDs, die Sie aus dem Index erhalten. Beispiel:
%Vor% Sie rufen die Muster-IDs für jedes Token ab und speichern sie in einer temporären Datenstruktur, die die Häufigkeit jeder ID zählt, z. B. einen Hashwert (z. B. std::unordered_map<id_type,std::size_t> ).
Sie sortieren dann nach Häufigkeit, um herauszufinden, dass Regel 1 zweimal gefunden wurde und Regel 2 einmal gefunden wurde.
Sie wenden dann die gefundenen Regeln in der Reihenfolge der Häufigkeit auf den Eingabetext an. Hier verwenden Sie eine Bibliothek für reguläre Ausdrücke oder etwas ähnliches, um Übereinstimmungen zu generieren. Die häufigste Regel hat die meisten Tokens mit dem Eingabetext gemeinsam, so dass sie wahrscheinlich gut zusammenpassen.
Der Gesamtvorteil des Ansatzes besteht darin, dass Sie nicht alle Regeln auf die Eingabe anwenden müssen, sondern nur diejenigen, die mindestens ein Token mit der Eingabe gemeinsam haben, und sogar diejenigen, die Sie verwenden es in der Reihenfolge, wie viele Token jede Regel mit der Eingabe teilt, und sobald Sie eine passende Regel gefunden haben, könnten Sie wahrscheinlich den Rest des Matching-Verfahrens abbrechen (oder nicht - abhängig davon, ob Sie wollen alle passende Regeln in jedem Fall, oder nur eine, die eine sehr gute Übereinstimmung ist).
Verbesserung Obiges führt die Regel-Vorauswahl anhand von Tokens durch. Stattdessen könnten Sie alle Regeln wie folgt verketten:
%Vor%Dann konstruieren Sie ein Suffix-Array dieser verketteten Zeichenfolge.
Wenn Sie eine Eingabezeichenfolge eingeben, stimmen Sie sie mit dem Suffix-Array ab, um alle Teilstring-Übereinstimmungen zu identifizieren, einschließlich Übereinstimmungen, die kleiner als ein Token oder über mehrere Token verteilt sind. Im obigen Beispiel gehe ich davon aus, dass die Platzhaltersymbole * und $ im Suffix-Array enthalten sind, obwohl natürlich kein Teil einer Eingabezeichenfolge ihnen entsprechen wird. Sie können sie gut aus dem Suffix-Array ausschließen oder sie durch ein Dummy-Zeichen ersetzen.
Sobald Sie die Übereinstimmungen ermittelt haben, sortieren Sie sie nach Länge. Sie müssen auch die Übereinstimmungspositionen in der verketteten Zeichenfolge den Regel-IDs zuordnen. Dies ist ohne weiteres möglich, indem ein Array von Startpositionen von Regeln relativ zu der verketteten Kette aufrechterhalten wird; es gibt auch hochoptimierte Methoden, die auf indizierten Bitvektoren basieren (ich kann das bei Bedarf weiter ausführen).
Sobald Sie die übereinstimmenden Regel-IDs haben, tun Sie das gleiche wie im umgekehrten Index-Fall: Wenden Sie die passenden Regeln an, indem Sie den regulären Regex-Abgleich (oder Ähnliches) verwenden.
Dieser Ansatz ist wiederum relativ kompliziert und nur dann sinnvoll, wenn Sie über sehr viele Regeln verfügen. Wenn die Möglichkeit besteht, dass eine tokenbasierte (oder substringbasierte) Suche die Anzahl der Kandidatenregeln erheblich reduziert. Aus den Beispielregeln, die Sie gegeben haben, gehe ich in letzterem Fall aus, aber wenn die Anzahl der Regeln, mit denen Sie es zu tun haben (in der Größenordnung von 10k), diesen Ansatz rechtfertigt, bin ich mir nicht sicher. Es kann sinnvoller sein, wenn die Gesamtzahl der Regeln in den 100 Millionen oder Millionen liegt.
Angesichts Ihres Kommentars, dass die Muster zur Laufzeit nicht aktualisiert werden müssen, bin ich mir nicht sicher, ob Sie überhaupt eine Laufzeitstruktur benötigen.
Ich würde empfehlen, re2c oder ragel
Vielleicht möchten Sie sich flex ansehen. Aus dem Handbuch:
flex ist ein Werkzeug zum Erzeugen von Scannern. Ein Scanner ist ein Programm, das lexikalische Muster im Text erkennt. Das Flex-Programm liest die angegebenen Eingabedateien oder die Standardeingabe, wenn keine Dateinamen angegeben sind, für eine Beschreibung eines Scanners, der generiert werden soll. Die Beschreibung hat die Form von Paaren regulärer Ausdrücke und C-Code, die Regeln genannt werden. flex erzeugt als Ausgabe eine C-Quelldatei, standardmäßig lex.yy.c, die eine Routine yylex () definiert. Diese Datei kann kompiliert und mit der Flex-Laufzeitbibliothek verknüpft werden, um eine ausführbare Datei zu erstellen. Wenn die ausführbare Datei ausgeführt wird, analysiert sie ihre Eingabe auf das Auftreten der regulären Ausdrücke. Wenn es einen findet, führt es den entsprechenden C-Code aus.
Auch das:
Das Hauptziel von flex besteht darin, leistungsstarke Scanner zu entwickeln. Es wurde für den Umgang mit großen Regelwerken optimiert.
Dieser Scanner entspricht beispielsweise den drei Mustern in Ihrem Post:
%Vor%Flex funktioniert durch Erzeugen eines diskreten endlichen Automaten (DFA). Ein DFA überprüft jedes Eingabezeichen genau einmal. Es gibt kein Backtracking, auch wenn Wildcards verwendet werden. Die Laufzeit ist O (N), wobei N die Anzahl der eingegebenen Zeichen ist. (Mehr Muster erzeugen größere DFA-Tabellen, die mehr Cache-Misses verursachen, also gibt es einige Nachteile für mehr Muster. Aber das gilt für jedes passende System, das ich mir vorstellen kann.)
Sie müssen jedoch Ihre Muster in der richtigen Reihenfolge auflisten, um sie korrekt abzugleichen. Flex kann Ihnen sagen, ob ein Problem vorliegt. Wenn Sie beispielsweise die Reihenfolge der WHAT-IS-XYZ- und WHAT-IS-Muster im obigen Scanner umkehren, sagt flex Ihnen Folgendes:
%Vor%Wenn Sie die Anforderungen von flex erfüllen können, sollte flex Ihnen einen sehr schnellen Scanner bieten.
Haben Sie Ternary Search Tree ausprobiert? Hier ist eine C ++ - Implementierung: Ссылка
Ich habe keine Erfahrung, wie langsam es ist, einen ternären Baum zu bauen, aber ich weiß, dass die Suche sehr schnell ist.
[Bearbeiten]
Für den passenden Platzhalter innerhalb der Struktur in partialMatchSearch: (Disclaimer: Dies ist nur ein Vorschlag und nicht in irgendeiner Weise getestet)
Sie könnten dem Baum * Symbole und am Anfang der Funktion partialMatchSearch eine if-Klausel hinzufügen:
%Vor%Mit anderen Worten, rekursiv rufen Sie partialMatchSearch mit demselben Knoten auf, aber die Zeichenfolge ist auf das nächste Zeichen gesetzt.
Wenn Platz kein Problem ist, könntest du Folgendes tun, von oben auf meinem Kopf.
Erstellen Sie einen Baum, der Kinder der möglichen Zeichen an dieser Stelle in der Baumstruktur hat, wo die aktuelle Ebene der Index in die Zeichenfolge ist. Die erste Ebene des Baums ist die Indexstufe 0 oder vielmehr der Arrayindex 0 in der Zeichenfolge.
Jede Ebene wäre ein Index in die Zeichenfolge, sodass der Stammknoten den Index 0 und die untergeordneten Elemente den Index 1 hätte. Jeder Knoten würde an dieser Stelle in der Zeichenfolge N Kinder enthalten, die der Anzahl der möglichen Zeichen entsprechen.
Also, sagen wir, du hättest die Wurzel mit der möglichen Menge ["a", "b", "c"], es hätte drei Kinder. Dann sagen Sie, Sie wollten eine mögliche Übereinstimmung für die Zeichenfolge "ab" finden, die Sie für das Kind, das die Route von "a" hat, zurückgeben und von dort aus gehen würden.
Wenn Sie das Ende der Zeichenfolge erreichen, bevor Sie zu einem Blattknoten gelangen, ist die Liste der möglichen Zeichenfolgen die gesamte Unterstruktur aller untergeordneten Elemente Ihres aktuellen Knotens.
Hoffen Sie, dass das einen Sinn ergeben hat, aber es würde aussehen wie ein huffman Baum, aber jedes Blatt würde eine mögliche Zeichenfolge zur Auswahl haben.
Ich würde Kernighans und Pikes Ratschlag nehmen und einen vernünftigen Algorithmus wählen und ihn dann brutal dazu zwingen.
Alle Ihre Beispiele suchen nach dem "längsten Präfix", was für mich eher einen einfachen Trie- als einen Suffix-Baum bedeutet. Wenn Sie nur ~ 10k gespeicherte Strings benötigen, sollten Sie in der Lage sein, einen Char-Trie in höchstens ein paar Stunden zu implementieren, indem Sie verschachtelte STL-Maps verwenden.
Wenn die Speicherkapazität nicht knapp ist oder die Leistung wirklich kritisch ist, sollte dies in Ordnung sein.
Das ist nicht die Frage, die Sie stellen. Du wolltest etwas, das vorgegart ist. Aber ...
Wie komplex muss das sein? Wenn ich versuchen würde, das zu tun, was du verlangst, würde ich etwas mehr Raum intensiv, aber viel weniger zeitaufwendig versuchen.
Ich würde (und habe) mit einem Baum mit dem Index 0 des Alphabets beginnen.
Dann wäre jeder Kindknoten ein Wort (das Wörterbuch).
Dann wäre jeder Kindknoten ein potentieller String-Segment-Vergleich, zum Beispiel, dass "Runde" fast nie DIREKT dem "Quadrat" folgt. Sie können sagen, "Setzen Sie den runden Stift in das quadratische Loch," aber das Wort, das "rund" folgt, ist "peg". Die Segmenttreffer für "Runde" wären also "Runde Pflock", "Runde Tasse", "Runde Kugel". Ich würde Artikel auch streichen, weil sie nichts zu dem Satz bedeuten (normalerweise). Der obige Absatz würde bedeuten: "Jeder Kindknoten ist ein Wort".
Ich würde jedoch eine Heuristik hinzufügen, da selbst ein erweiterter B-Baum langsam werden kann, wenn Sie so viele Daten haben. Ich habe gesehen, dass sie sich bei der Suche nach sehr großen Datensätzen auf eine Minute oder mehr verlangsamen.
Das setzt voraus, dass Sie nicht wirklich eine Datenbank verwenden wollten, die wahrscheinlich die schnellste wäre, wenn Sie nicht in ASM programmieren wollten.
Tags und Links c++ trie pattern-matching suffix-tree suffix-array