Mi chiedo come funziona regex, il mio particolare espressione regolare ha un elemento che assomiglia a questo:Java regex l'ottimizzazione di questo caso specifico?
(word1|word2|wordn......)
Il numero delle parole è grande diverse centinaia.
Mi chiedo se il motore regex sta solo testando le parole una per una o se ottimizza la ricerca e in che modo.
Qualsiasi puntatore a una buona documentazione sarà buono.
Se si dispone di diverse centinaia di parole, è necessario fare attenzione all'ordinamento delle parole nella regex. Il motore regex cerca le parole da sinistra a destra.
Se si verifica la parola setValue contro l'alternanza set|setValue, corrisponderà solo alle 3 lettere che comprendono "set" e non all'intera stringa.
Vedere questo link (da www.regular-expressions.info) per la spiegazione completa.
Non penso che il motore regex ottimizzi realmente le alternanze (ad esempio, analizzando i prefissi comuni e costruendo nfa di conseguenza). Pertanto, con così tante parole, non penso che sarà un'ottimizzazione.
Oltre a riordinare le parole, è anche possibile provare ad aggiungere un limite di parola o linea dopo l'alternanza, ad es. (set|setValue)$, ma ho il sospetto che il motore regex farà un sacco di backtracking quindi potrebbe non valerne la pena.
Suppongo che il motore verifichi ancora ogni parola lettera per lettera e tornerà indietro non appena una lettera differisce a destra? – millebii
Voglio un punto di riferimento di questo (handoptimized contro regex ingenuo). –
Sì, tornerà indietro lettera per lettera, ma ci possono essere ancora tonnellate di backtracking con centinaia di parole – Yoni
vedere this link
Questo articolo spiega JavaWorld sottostante meccanismo di java regexp (chiamato NFA per non deterministico Finite Automaton, o NFA). Ci sono anche interi libri sull'argomento. Controlla anche lo Resources Section.
Pubblicare * solo * un collegamento come risposta non è una buona idea L'articolo collegato può essere rimosso/spostato/bitrot e quindi la risposta diventa priva di significato –
In genere hai ragione, ma questo è il collegamento a javaworld, quindi dubito che verrà rimosso e spiega tutto molto bene – AlexR
Thx, sfortuna per me le NFA non ottimizzano quelle espressioni – millebii
Se ti sembra che il motore RE sia il collo di bottiglia di tale ricerca, puoi facilmente costruire un trie e controllare il contenimento.
Molto interessante, potrei provare questo. Qualche implementazione Java che conosci?O potrei usare l'implementazione della mappa hash descritta nel tuo link. – millebii
Per la cronaca puoi trovare un'implementazione Java interessante di TRIE [qui] (https://github.com/rkapsi/simple-patricia-trie#readme) – millebii
[There] (http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page=2) dice: _ Attenzione all'alternanza. Le espressioni regolari come "(X | Y | Z)" hanno la reputazione di essere lente, quindi fai attenzione a loro_ – millebii
** [...] invece di "(abcd | abef)" usa "ab (cd | ef)" [...] "* - Questa è la forma più banale di ottimizzazione e sarei molto sorpreso se il motore regex di Java non lo eseguisse. – aioobe
@aioobe non molto utile, con diverse centinaia di parole come si fa – millebii