Datenbank oder Struktur geeignet für die Anpassung von Strings an Regex-Muster

Question

Ich habe eine Reihe von Regex-Mustern. Wenn eine Zeichenfolge eingegeben wird, muss ich feststellen, dass alle Muster mit dieser Zeichenfolge übereinstimmen. Dies ist normalerweise ein O (n) Betrieb:

SELECT regex FROM regexes WHERE 'string' RLIKE regex 

Was ist der schnellste Weg, dies zu tun? Gibt es Datenbankstrukturen oder Speichersysteme, die für eine solche Operation optimiert sind?

Answer 1

Die kurze Antwort ist "Nein" Derzeit gibt es auf keiner DBMS-Plattform eine Indexstruktur, die Teilübereinstimmungen einer Regex wie dieser indexiert.

Die lange Antwort ist, dass eine führende Konstante auf einer Wildcard-Übereinstimmung (z. B. 'foo_') als ein Präfix für Indexübereinstimmungen verwendet werden kann. Viele DBMS-Plattformen optimieren dies und verwenden einen Index (falls verfügbar), um das Präfix aufzulösen. Dies ist jedoch nicht so clever wie eine vollständige Regex, und die Indizierung kann nur verwendet werden, wenn Sie ein konstantes Präfix haben.

Die noch längere Antwort ist, dass es Algorithmen wie RETE gibt, die partielle Übereinstimmungen wie diese optimieren werden. Dies trifft möglicherweise zu, wenn Sie Ihre Übereinstimmungen als Vorwärtsverkettungsregeln und nicht als reguläre Ausdrücke ausdrücken können.

Rete funktioniert durch Berechnen partieller Übereinstimmungen und präsentiert nur Regeln, die von dieser partiellen Übereinstimmung erreicht werden können, also ist es effizienter als O (n) (mehr wie O (log n), aber ich bin mir nicht sicher Zeitkomplexität), um n Regeln gegen eine Tatsache abzustimmen.

Answer 2

Eine Optimierung Sie können ggf. auf Ihren Fall implementieren, wäre Ihre reguläre Ausdrücke zu kategorisieren und sie in Hierarchien, so dass organisieren:

• Sie nur eine Handvoll von den meisten General Regexes testen müssen.

• für alle zutreffenden allgemeinen Regex, dann weiter, um die Zeichenfolge nur für alle Regexes der gleichen Kategorie zu testen.

Zum Beispiel, wenn Sie Ihre Eingabe Strings beliebig komplex alles sein kann und Sie haben Tausende von regulären Ausdrücken, könnte man sich in Kategorien wie organisieren:

• die \d+ Kategorie, die Anzahl Muster testen würde (SSN, Telefonnummern usw.)

• die <.*?> Kategorie, die das Vorhandensein von HTML-Tags testen würde

• die \w+@\w+ Kategorie, die das Vorhandensein von E-Mail Adressen

usw. testen konnte

Wenn ein Wurzelmuster nicht übereinstimmt, dann vermeiden Sie Bereiche von Mustern zu testen ganzen haben, die ohnehin versagen .

Ich weiß nicht, ob das Ihrer genauen Domain entspricht, aber es ist eine mögliche Optimierung.