Eine Sammlung von Regexen effizient durchsuchen

Question

Wenn ich eine unbekannte Menge an regulären Ausdrücken habe (Null oder mehr und hoffentlich weniger als ein paar Tausend), was ist eine effiziente Möglichkeit, nach einer Zeichenfolge zu suchen?

Welche Arten von Containern, Algorithmen und/oder Datenstrukturen sollte ich verwenden? Ist das anders, wenn ich die einzige übereinstimmende Regex finden möchte, als wenn ich von allen Regex-Treffern möchte? Unterscheiden sich diese von nur wollen wissen, wie viele abgestimmt?

Lassen Sie mich das auf eine andere Art sagen, nehmen wir an, ich habe einen Benutzer, der willkürliche Zeichenfolgen eingibt, und ich habe einige Behälter von Regexes. Ich kann den Container so gestalten, wie ich es möchte, und die Suche nach jedem beliebigen Weg durchführen. Was soll ich tun, wenn ich eine Liste aller Regexes haben möchte, die mit den Benutzereingaben aus dieser Sammlung übereinstimmen? Wie würde ich das tun? Was, wenn ich nur wissen möchte, wie viele Matches existieren? Was, wenn ich nur die Einzigartigkeit eines Spiels versichern wollte?

Answer 1

Wenn Sie eine Vorberechnung für Ihre regulären Ausdrücke durchführen können, bevor Sie Strings mit ihnen abgleichen, können Sie die Vereinigung aller Elemente in ein DFA konvertieren, das gleichzeitig eine Zeichenfolge mit allen Zeichenfolgen abgleicht.

Siehe: https://en.wikipedia.org/wiki/Deterministic_finite_automaton

Dieser Ansatz sehr oft für lexikalische Analyse (tokenization) in Parser und Compiler verwendet wird. Der Vorteil eines DFA ist, dass es die gleiche Geschwindigkeit (schnell) hat, egal wie viele Regexes Sie hineinlegen oder wie kompliziert sie waren.

Es ist nicht so einfach, aber es gibt Werkzeuge herum. Wenn Sie in Java arbeiten, habe ich ein Open-Source-Projekt, das Sie möglicherweise verwenden können: http://mtimmerm.github.io/dfalex/. Um Ihre anderen Fragen zu beantworten, können Sie die Menge aller passenden Regexes daraus entnehmen, wenn Sie möchten.

Wenn Sie daran interessiert, wie es selbst zu tun, der Prozess besteht im Allgemeinen aus Ihrer regulären Ausdrücken in einen NFA Umwandlung (https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton) unter Verwendung von Thompson Konstruktion (https://en.wikipedia.org/wiki/Thompson%27s_construction) und dann die NFA in einen DFA-Umwandlungsteilmenge Konstruktion unter Verwendung von (https://en.wikipedia.org/wiki/Powerset_construction), und dann minimiert in der Regel die DFA mit Hopcroft-Algorithmus (https://en.wikipedia.org/wiki/DFA_minimization)

Es gibt viel Platz für Optimierung und Finesse.

Viel Glück!

P.S. Ich sollte ein paar Dinge beachten: 1) Sie können DFAs im Allgemeinen nicht aus Regexes machen, die Rückverweise haben. 2) Es ist theoretisch möglich, dass das DFA exponentiell groß ist. Dies geschieht fast nie zufällig, aber wenn Ihre Regexes von potentiell bösartigen Personen betreten werden, müssen Sie etwas gegen diese Möglichkeit unternehmen.

Answer 2

Ein PHP-Beispiel:

<?php 
$regex_array = array(
    "/regex_1/" => 0, 
    "/regex_2/" => 0, 
    "/regex_3/" => 0 // and so on and so forth 
); 

$strings_array = array(
    "input_string_1", 
    "input_string_2", 
    "input_string_3" // and so on and so forth 
); 

foreach ($regex_array as $key => $value) 
    foreach ($strings_array as $current_string) 
    if (preg_match($key, $current_string)) 
     $regex_array[$key]++; 
?> 

Here ist der runnig Code.

Answer 3

Ich werde meine eigene Antwort nicht als die Antwort markieren, es sei denn, jemand schlägt es in ein paar Tagen.

---

Bisher ist die einzige Idee, die ich etwas wert gehabt haben ist die reguläre Ausdrücke in eine von zwei Pfählen im Inneren des Behälters zu setzen, wenn es hinzugefügt wird.

In einen Stapel gehört jeder Regex mit einem Platzhalter, einer Zeichenklasse oder irgendetwas anderem, was dazu führt, dass er von der herkömmlichen Zeichenkette abweicht. Ich werde dies die RegexPile nennen.

In den anderen Stapel gehen alle Regexes, die Strings oder Trivial in String umwandelbar sind. Da Strings leicht zu finden sind und Algorithmen gut verstanden werden, kann ich sagen, dass dieser Stapel Container sein wird und geordnet wird und sortiert wird, und das Finden von Strings darin ist mit einer binären Suche trivial. Ich werde dies die SortedStringArray nennen.

Naiv, kann ich suchen linear RegexPile und tun eine binäre Suche auf SortedStringArray. Dies erlaubt mir zumindest einige Vergleiche zu überspringen und kostet wenig Zeit und Raum, aber auch wenig wirkliche Optimierung.

Es ist rechnerisch ähnlich, aber wenn ich so etwas tue, denke ich, ich werde einen Thread für jede Regex (oder jede kleine Gruppe von Regexes) in RegexPile starten. Mein Gedanke ist, dass jeder gegebene Regex einen unbegrenzten Betrag annehmen kann, weil Regexes das tun können. Wenn dann Threads zu lange dauern, kann ich aufgrund eines Timeouts fehlschlagen und alle Threads vorzeitig beenden. Ich denke auch, dass die Mehrheit an dem ersten Zeichen scheitern wird, was bedeutet, dass die meisten dieser Fäden einfach verschwinden werden, sobald das erste Zeichen angekreuzt ist. Mit den billigen Copy-on-Write-Threads, die die meisten Systeme heutzutage bieten, sollte dieses Thread-Laichen so günstig sein, dass viele Threads schließen werden, bevor ich sie alle ablaichere und nur die, die ziemlich ähnlich sind, werden für jede Zeit verweilen. Dann mache ich die Binärdatei in einem anderen Thread für SortedStringArray.