Combinare più espressioni regolari in un automa

Question

Diciamo che ho un elenco di espressioni regolari (letto da una fonte esterna - file, database ecc.). Voglio controllare a quale di queste espressioni regolari corrisponde una stringa.

Posso creare un'iterazione attraverso tutte queste espressioni regolari e farle corrispondere, ma l'elenco potrebbe essere enorme e questa è un'operazione critica.

Posso combinare tutte queste espressioni regolari in una (con | tra di esse), ma il problema è che posso identificare solo la prima espressione regolare con corrispondenza, non tutte.

Un'altra idea potrebbe essere quella di creare un automa per tutte queste espressioni regolari e contrassegnare gli stati finali con, diciamo, gli indici dell'espressione regolare corrispondente. Stavo guardando http://cs.au.dk/~amoeller/automaton/, una libreria che sembra in grado di funzionare con espressioni regolari e automa, ma non è sicuro che possa essere estesa per risolvere il mio problema.

Avete altre idee?

per chiarire alcuni commenti, ho aggiunto un esempio di codice:

import java.util.regex.Matcher; 
import java.util.regex.Pattern; 


public class PatternTest { 
    public static void main(String[] args) { 
     Pattern p = Pattern.compile("(a(?:b|c)a)|((?:a|b)ba)|(ab(?:a|c))");  
     Matcher m = p.matcher("aba"); 
     System.out.println(m.matches()); 
     System.out.println(m.groupCount()); 
     for (int i = 0, n = m.groupCount(); i < n; i++) { 
      System.out.println(m.group(i)); 
     } 
    } 
} 

sarà stampare

true 
3 
aba 
aba 
null 

Come si può vedere solo il primo gruppo è abbinato e non vedo un modo per abbinare gli altri due.

Altri risultati - Utilizzando la libreria dell'automa sopra, il problema si riduce a quanto segue: se si concatenano due o più automi, come è possibile identificare per uno stato finale a quale degli automi originali è corrispondente?

Answer 1

dk.brics.automaton non supporta direttamente questo, ma è possibile generalizzare la rappresentazione di automi (e le operazioni automatiche rilevanti) per distinguere tra diversi tipi di stati di accettazione. Inizia aggiungendo un campo int, ad esempio, alla classe State e utilizza questo campo ogni volta che "accetta" è impostato.

Answer 2

Per una risposta definitiva (se ce n'è uno) avremmo bisogno di qualche informazione in più, come:

1. Tu dici la lista delle espressioni regolari è enorme; Può essere più preciso? Migliaia? Milioni? Miliardi e miliardi?

2. Chi ha scritto queste regex e sanno cosa stanno facendo? Le regex sono state accuratamente testate (per la correttezza delle prestazioni e) prima di essere aggiunte all'elenco?

3. Nel codice di esempio si utilizza il metodo matches(), che richiede la regex per descrivere l'intera stringa. Funziona come se la regex fosse davvero
   \A(?:(a(?:b|c)a)|((?:a|b)ba)|(ab(?:a|c)))\z
   che corrisponde a "aba" ma non "aaba" o "abaa". Se hai usato espressioni rege in altri strumenti o lingue prima di arrivare a Java, questo comportamento potrebbe sorprendervi. Tradizionalmente, una stringa è sempre stata detta per "abbinare" una espressione regolare se l'espressione regolare descrive una sottostringa all'interno della stringa, anche una sottostringa di lunghezza zero. Per ottenere questo comportamento in Java, è necessario utilizzare il metodo find() del Matcher.

4. Esistono alcuni fattori comuni che è possibile estrarre da tutte le espressioni regolari nell'elenco, come la lunghezza minima o massima, sottostringhe comuni o sottoinsiemi di caratteri condivisi? Ad esempio, qualsiasi stringa che corrisponde a uno dei tuoi modelli di esempio deve corrispondere anche a [abc]{3}. Se ci sono, potresti voler creare filtri basati su di essi (magari espressioni regolari, forse non) da eseguire prima che inizi la corrispondenza seria.(Non vorrei suggerire questo se si stesse utilizzando Perl, che è Choc-a-blocco con le ottimizzazioni del genere già, ma Java non è troppo orgoglioso per accettare un piccolo aiuto. ☺)

Ma mi sento abbastanza sicuro consigliandovi di andare con espressioni rege distinte piuttosto che concatenarle tutte in una. Il Frankenregex non funzionerebbe necessariamente meglio e risolvere il problema sarebbe un incubo! È possibile pre-compilare tutti gli oggetti del modello, ed è possibile creare un oggetto Matcher anticipo e riutilizzarlo per tutte le partite, in questo modo:

m.reset(s).usePattern(p); 

Ecco un demo. Non posso dare alcuna garanzia (sei ancora in balia di chiunque abbia scritto le espressioni regex, per prima cosa), ma se una soluzione è possibile, penso che questo sia l'approccio più promettente.

Answer 3

Ho implementato una soluzione di questo tipo basata su dk.brics.automaton, lo potete trovare qui. https://github.com/fulmicoton/multiregexp