regexp dans le problème Java

Question

J'ai trouvé un problème lors du test de mon système NLP. J'ai un java regex "(.*\\.\\s*)*Dendryt.*" et pour la chaîne "v Table of Contents List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . " il n'arrête pas de calculer.

Il est clair que cette complexité regex est très élevée, je vais essayer de le refactoriser. Avez-vous quelques suggestions pour moi pour un futur développement regex ???

Merci.

Answer 1

Vous exécutez catastrophic backtracking en répétant un groupe contenant des quantificateurs répétés. L'explosion combinatoire qui suit va alors (avec suffisamment d'entrée) conduire à un débordement de pile (tada!).

simplifié, votre regex tente de

(.*\.\s*) match de toute succession de caractères y compris des points et des espaces, suivi d'un point, suivi par un ou plusieurs espaces, puis

(...)* répéter cela autant fois.

Dendryt Alors seulement il essaye de faire correspondre "Dendryt".

Comme cela échoue, le moteur revient en arrière, en essayant une permutation différente. Les possibilités sont presque infinies ...

Pour illustrer, voici une capture d'écran du débogueur regex RegexBuddy sur une version simplifiée de vos données:

RegexBuddy Screen Shot http://img714.imageshack.us/img714/3275/screen017.png

Le moteur donne après 1 million de permutations.

Votre regex serait un peu mieux comme ça (ne pas oublier de les backslashs lors de la conversion à une chaîne Java):

(.*)(\.\s*)*+Dendryt 

Dans ce cas, le *+, un soi-disant quantificateurs possessifs , refusera de revenir en arrière une fois qu'il a correspondu. De cette façon, le moteur regex peut échouer beaucoup plus rapidement, mais il est toujours mauvais car (.*) correspond à n'importe quoi, même les points.

([^.]*)(\.\s*)*+Dendryt 

est sûr, sauf si vos données peuvent contenir des points avant le "bit en pointillés". Dans l'ensemble, s'il vous plaît énoncer vos exigences un peu plus clairement, alors une meilleure regex peut être construite.

Answer 2

Essayez ceci:

"[^.]*+(?>\\.\\s*)*+Dendryt.*" 

[^.]*+ dévorant tout avant le premier point, et le + fait la *possessive, de sorte que le regex ne sera jamais revenir en arrière delà de ce point.

(?>\\.\\s*) est un atomic group: il correspond à un point et à tout espace suivant comme s'il s'agissait d'une seule unité. Si le moteur regex doit revenir en arrière à ce point, il passera directement à l'endroit où le groupe a commencé à correspondre.

Mais il ne sera pas revenir en arrière à ce point, car j'ai rendu le quantificateur du groupe possessif, aussi. Je voulais illustrer l'utilisation des groupes atomiques, mais j'aurais pu rendre le \\s* possessif à la place - ou les deux.

Les quantificateurs possessifs et les groupes atomiques désactivent complètement le retour arrière, mais il n'est pas toujours possible de les utiliser. Lorsque vous devez autoriser un retour en arrière, gardez-le au minimum; ne laissez pas les quantificateurs consommer plus qu'ils ne le doivent. Et surtout, comme l'a dit Tim, évitez les quantificateurs imbriqués et les sous-expressions quantifiées qui peuvent correspondre aux mêmes choses. En fait, il est bon d'éviter l'utilisation de .* et .+; cela vous oblige à réfléchir à la mécanique de celui-ci. S'il n'y a pas quelque chose de particulier que vous voulez faire correspondre, pensez à ce que vous voulez ne pas voulez, comme lorsque j'ai utilisé [^.]* à la place du premier .* dans votre regex.