Wie finde ich ein „minimales Spannungssatz“ für eine Sammlung regulärer Ausdrücke?

Question

KONTEXT:

Ich habe eine kleine (derzeit weniger als 100), aber wachsende Sammlung regulärer Ausdrücke, und ich möchte den Prozess der Bestimmung für eine bestimmte Textzeichenfolge optimieren. Welche der RES in meiner Sammlung übereinstimmen mit der Textzeichenfolge.

Einige der RES haben eine Bestellbeziehung - zum Beispiel, wenn ich weiß, dass die Zeichenfolge $ T übereinstimmt /Windows /Ich, dann weiß ich auch, dass $ t übereinstimmt /windows.*2000/i. Wenn ich also $ T gegen die RES in meiner Sammlung testen kann, kann ich Tests /Windows /I überspringen, wenn ich bereits $ t gegen /windows.*2000/i getestet habe und ein Match gefunden habe (obwohl /windows.*2000/i es tut nicht Match dann natürlich ich ich kann nicht Überspringen Sie den Test gegen /Windows /i).

Beachten Sie, dass keiner der REs in meiner Sammlung völlig gleichwertig ist (für ein Paar von RES gibt es mindestens eine Textzeichenfolge, die mit einer übereinstimmt und tut nicht übereinstimmen den anderen).

STRATEGIE:

Ich möchte ein angegebenes Diagramm G mit einem Knoten für jede RE in meiner Sammlung und eine gerichtete Kante für jedes RES -Paar mit einer Bestellbeziehung (a -> b bedeutet "Übereinstimmung gegen ein impliziertes Match gegen B") und a "Minimal Spanning Set" von Knoten für den Diagramm (minimaler Satz von Knoten s, so dass jeder Knoten in g auf einem gerichteten Pfad liegt, der in s stammt).

Der einfache Teil:

Es gibt viele frei verfügbare Algorithmen für die Arbeit mit gerichteten acyclischen Graphen. Sobald das Diagramm G für meine Sammlung von RES erstellt wurde (was eindeutig ist, sollte garantieren, dass G acyclisch ist), erwarte ich keine großen Schwierigkeiten, einen geeigneten Algorithmus zu finden, um einen minimalen Spannungssatz für G.

Wo ich Hilfe brauche:

Ich würde gerne einen effizienten Weg finden, um alle Bestellverhältnisse zwischen den RES in meiner Sammlung zu finden - und vielleicht auch sicherzustellen hinzugefügt).

Meine (im Wesentlichen zufällige) Web -Suche haben somit mindestens eine plausible Behauptung aufgetaucht, dass eine vernünftige Möglichkeit, die (falls vorhanden) Bestellbeziehung zwischen zwei RES zu berechnen, tatsächlich existiert, aber noch keine Beschreibungen eines vollständigen Algorithmus aufgenommen hat.

Kennt jemand eine vorhandene Implementierung (zum Vergleich von Res), die einigermaßen effizient, frei verfügbar und (idealerweise) entweder in einer der beliebten Skriptsprachen oder C/C ++ implementiert werden?

Answer 1

Ich bin mir nicht sicher, ob Sie Flexibilität in Bezug auf die reguläre Ausdrucksbibliothek haben, die Sie verwenden müssen, aber Sie könnten sich ansehen Re2 Deren Satz Die Schnittstelle kann mehrere Regexes gleichzeitig übereinstimmen. Beachten Sie, dass RE2 hauptsächlich einen DFA -Ansatz verwendet und nicht alle Regex -Funktionen unterstützt, die andere, meist rückdurchschnittliche Implementierungen tun.