Database o struttura adatta per associare stringhe a motivi regolari.

Question

Ho un numero di motivi di espressioni regolari. Quando viene immessa una stringa, devo trovare tutti i pattern che corrispondono a questa stringa. Questo è normalmente un'operazione O (n):

SELECT regex FROM regexes WHERE 'string' RLIKE regex 

Qual è il modo più veloce per fare questo? Ci sono strutture di database o sistemi di archiviazione che sono ottimizzati per fare una tale operazione?

Answer 1

La risposta breve è "No". Non esiste una struttura di indice attualmente disponibile su qualsiasi piattaforma DBMS che indicherà corrispondenze parziali di una regex come questa.

La risposta lunga è che una costante iniziale su una corrispondenza con caratteri jolly (ad esempio 'foo_') può essere utilizzata come prefisso per le corrispondenze indice. Molte piattaforme DBMS lo ottimizzeranno e utilizzeranno un indice (se disponibile) per risolvere il prefisso. Tuttavia, questo non è affatto intelligente come una regex completa e l'indicizzazione può essere utilizzata solo se si dispone di un prefisso costante.

La risposta ancora più lunga è che ci sono algoritmi come RETE che ottimizzeranno corrispondenze parziali come questa. Questo potrebbe essere applicabile se è possibile esprimere le proprie corrispondenze come regole di produzione per il collegamento in avanti piuttosto che per le espressioni regolari.

Rete funziona calcolando corrispondenze parziali e solo presentando regole che possono essere raggiunte da questa corrispondenza parziale, quindi è più efficiente di O (n) (più come O (log n) ma non sono sicuro dell'esatto complessità temporale) per far corrispondere le regole a un fatto.

Answer 2

Uno ottimizzazione è possibile implementare, se applicabile al vostro caso, sarebbe quello di classificare le espressioni regolari e organizzarli in gerarchie in modo che:

• si hanno solo per testare una manciata di più generale regex.

• per qualsiasi regex generica corrispondente, quindi procedere a testare la stringa contro tutte le espressioni regolari della stessa categoria.

Per esempio, se le stringhe di input possono essere qualsiasi cosa arbitrariamente complessa e si dispone di migliaia di espressioni regolari, si potrebbe organizzarli in categorie come:

• categoria \d+, che avrebbe testare modelli numerici (SSN, numeri di telefono, ecc)

• categoria <.*?>, che prova la presenza di tag HTML

• la categoria \w+@\w+, che potrebbe testare la presenza di indirizzi

ecc email

Se qualsiasi modello di root non corrisponde, quindi si evita di dover mettere alla prova tutta la gamme di modelli che fallirebbero in ogni caso .

Non so se questo corrisponderebbe al tuo dominio esatto, ma è una possibile ottimizzazione.