Come trovare un "set di spanning minimo" per una raccolta di espressioni regolari?

Question

CONTESTO:

Ho una piccola raccolta di espressioni regolari (attualmente meno di 100) e voglio ottimizzare il processo di determinazione per una determinata stringa di testo che della mia raccolta corrisponde alla stringa di testo.

Alcune delle RES hanno una relazione di ordinazione, ad esempio se so che la stringa $ T corrisponde /Windows /Io so anche che $ t corrisponde /windows.*2000/i. Quindi, quando ho testato $ T contro la Res nella mia collezione, posso saltare i test /Windows /I se ho già testato $ T contro /windows.*2000/i e ho trovato una corrispondenza (anche se se /windows.*2000/i lo fa non abbina quindi ovviamente io non può Salta il test contro /Windows /I).

Si noti che nessuna delle RES nella mia raccolta è del tutto equivalente (per qualsiasi coppia di RES c'è almeno una stringa di testo che corrisponde a una e lo fa non abbinare l'altro).

STRATEGIA:

Voglio costruire un grafico diretto G con un nodo per ogni RE nella mia collezione e un bordo diretto per ogni coppia di RES con una relazione di ordinazione (a -> b significa "corrispondere a A implica la corrispondenza contro b") e trova A "Set di spanning minimo" di nodi per il grafico (set minimo di nodi S tale che ogni nodo in G si trova su un percorso diretto che ha origine in S).

La parte facile:

Ci sono molti algoritmi disponibili liberamente per lavorare con grafici aciclici diretti. Quindi, una volta che il grafico G è stato costruito per la mia raccolta di RES (che essendo distinti dovrebbe garantire che G sia aciclico) non mi aspetto di avere molte difficoltà a trovare un algoritmo appropriato per trovare un set di spanning minimo per G.

Dove ho bisogno di aiuto:

Vorrei trovare un modo efficiente per trovare tutte le relazioni di ordinazione tra la RES nella mia collezione - e forse anche per garantire che non ci sono due res nella raccolta (avrò bisogno di un modo per verificarlo automaticamente come nuove res aggiunto).

Le mie ricerche Web (essenzialmente casuali) hanno quindi rivelato almeno un'affermazione plausibile secondo cui esiste un modo ragionevole per calcolare la relazione di ordinazione (se presente) tra due RES, ma non hanno ancora rivelato alcuna descrizione di un algoritmo completo.

Qualcuno sa di un'implementazione esistente (per confrontare la RES) che è ragionevolmente efficiente, liberamente disponibile e (idealmente) implementata in uno dei linguaggi di script popolari o C/C ++?

Answer 1

Non sono sicuro di avere flessibilità in termini di libreria di espressione normale che devi usare, ma potresti guardare Re2 il cui, di chi Impostare L'interfaccia può abbinare più regexes contemporaneamente. Si noti che RE2 utilizza principalmente un approccio DFA e non supporta tutte le funzionalità di regex che fanno altre implementazioni, per lo più backtracking.